CS4102, Algorithms
Beginning of Course Memo (Summer 2014)

Class Web site:   http://collab.itc.virginia.edu

Instructor:     Prof. Tom Horton                     Email:  horton.uva@gmail.com
                        Office: Rice 402.  Phone:   982-2217

Office hours: MTWThF noon-1pm, and by appointment

Teaching Assistants: TBD.

Class time and location:  MTWThF 1-3:15 pm, THN D222

Prerequisite: CS2150 with grade of C- or higher.  (CS2102 is a pre-req for that.) CS2150 or a course that covers the equivalent data structures material is an absolute prerequisite.

Description from the Undergraduate Record:  Introduces the analysis of algorithms and the effects of data structures on them. Algorithms selected from areas such as sorting, searching, shortest paths, greedy algorithms, backtracking, divide- and-conquer, and dynamic programming.  Data structures include heaps and search, splay, and spanning trees. Analysis techniques include asymptotic worst-case, expected time, amortized analysis, and reductions between problems.

Course Objectives:  Upon successful completion of this course, students will:

1. Comprehend fundamental ideas in algorithm analysis, including: time and space complexity; identifying and counting basic operations; order classes and asymptotic growth; lower bounds; optimal algorithms.
2. Apply these fundamental ideas to analyze and evaluate important problems and algorithms in computing, including search, sorting, graph problems, and optimization problems.
3. Apply appropriate mathematical techniques in evaluation and analysis, including limits, logarithms, exponents, summations, recurrence relations, lower-bounds proofs and other proofs.
4. Comprehend, apply and evaluate the use of algorithm design techniques such as divide and conquer, the greedy approach, dynamic programming, and exhaustive or brute-force solutions.
5. Comprehend the fundamental ideas related to the problem classes NP and NP-complete, including their definitions, their theoretical implications, Cook's theorem, etc. Be exposed to the design of polynomial reductions used to prove membership in NP-complete.

Textbooks Required and Readings:

Required text: Introduction to Algorithms (3^rd edition) by Cormen, Leiserson, Rivest, and Stein, McGraw-Hill.  3^rd edition.

References:

Data Structures & Algorithm Analysis in C++, by Mark Allen Weiss. The CS2150 text.

Algorithms, by Richard Johnsonbaugh and Marcus Schaefer.

A few other readings will be assigned, either through handouts, on the web, or PDFs on-line.

Grading Information and Criteria:

• Exam 1, 22%.  Wednesday, May 28 (first hour of class)
• Exam 2, 22%.  Thursday, June 5 (first hour of class)
• Exam 3, 22%.  Saturday, June 14 (1-3pm)
• Homework sets, programs, and experiments. 34%.  See details below.
• Class participation. Up to a 5% penalty on the final grade total. See below.

Class participation. There will be a number of class participation activities that count towards this. They may include out-of-class activities (on-line surveys, not-for-grade quizzes) or participation in in-class activities. These will be announced in advance. Legitimate absences from class will not count against you if you inform me. 100% participation is not required.

Homework etc.   There will be 6 homework problem sets. Students may work alone or in pairs. Papers will be due at the start of class; those not due the day before an exam may be submitted 24 hours late but with a 10% penalty. Students working alone are allowed to talk to one other person or pair, but otherwise collaboration is not allowed.

Deadlines:  Drop on SIS before midnight on May 29.  Withdrawal deadline: June 6.  See summer school website for full details.

Expectations: I may post topics that I expect you to understand along with a set of problems that represent what I would expect you to be able to do. Sometimes I will announce what I expect you to do before coming to lecture (read something, work a problem, etc.) and the class meeting will reflect this. I may ask you to read pages in the textbook as background before lecture so that I don't have to lecture on basic material or things that are review from earlier courses. One goal this term is to make the course less lecture-oriented and instead have students be more active in our class meetings.

When in class: We’re meeting together in class so you can learn something from me, so it is important that you pay attention. Use of electronic devices (laptops etc.) during class can be used for class purposes or used in a way that does not detract from learning – or not! I may call upon students etc. who I think may not be paying enough attention in order to make sure learning is happening. Don’t be offended, please.

About Short Summer Sessions: A four-week summer session is ultra-compressed. A week of class in a regular term is the same as 1.33 days in the summer term, and there’s no weekend in between. You should be spending many hours every day outside of class on HW and reading. (The “usual” ratio is at least 2-to-1, out-of-class to in-class.) If you work or are taking other classes, be very careful! My expectation is that you’ll only be taking my class or that you’re capable of a very high workload for 4 weeks.

Probable Outline of Topics:

• Basics of algorithm analysis and design.  Asymptotic growth rate. Mathematical techniques. (Chap. 1, 2 and 3)
• Divide and Conquer, recurrence relations. (Chap. 4)  
• Sorting, selection, lower bounds proofs, order statistics (Chap. 6-9)
• Dynamic programming. (Chap. 15)
• Greedy algorithms.  (Chap. 16)
• Graph algorithms: spanning trees, shortest paths, graph searching (parts of Chap. 22-24)
• Algorithms and intellectual property.  (Perhaps!)
• NP-complete problems (Chap. 34)
• Possibly other topics, if we have time.

More details will be provided on the Collab site. The set of topics is subject to change.

Honor Policy: The UVa Honor Policy will be in effect in this class. Each assignment will describe allowed collaborations, and deviations from these will be considered Honors violations. Unless otherwise noted, exams and individual assignments will be considered pledged that you have neither given nor received help. An academic irregularity on any exam may result in failure of the course.

The School of Engineering and Applied Science relies upon and cherishes its community of trust.

We firmly endorse, uphold, and embrace the University’s Honor principle that students will not lie, cheat, or steal, and we expect all students to take responsibility for the System and the privileges that it provides. We recognize that even one Honor infraction can destroy an exemplary reputation that has taken years to build. Acting in a manner consistent with the principles of Honor will benefit every member of the community both while enrolled in the Engineering School and in the future.

If you have questions about your Honor System or would like to report suspicions of an Honor offense, please see the contacts at this site: http://www.virginia.edu/honor/contact