Sources

Textbooks (recommended, not required)

• D. C. Kozen. The Design and Analysis of Algorithms. Springer-Verlag, 1991.
• J. Kleinberg and E. Tardos. Introduction to Analysis of Algorithms. Addison-Wesley, 2005.
• M. R. Garey and D. S. Johnson. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979.

These titles are on reserve in the Engineering library, Carpenter Hall.

Handouts

All handouts other than homework and exams will be available on the web in pdf, html, or plain text format. There is a link in the navigation bar above. Check often for new postings.

For viewing pdf files, we recommend Adobe Reader, available free of charge from Adobe.

Homework and Exams

There will be biweekly homework sets consisting of 3-5 problems, due by 4pm on the due date. You may collaborate on the homework in groups of up to four. If you collaborate, submit one copy of your solutions with the names of all collaborators. Acknowledge all sources, including others in the class from whom you obtained ideas.

Solutions must be nicely formatted (LaTeX is strongly recommended) and submitted as a pdf file to CMS. There will be a point deduction of 10% per day for unexcused late homework. Assignments and solutions will be posted in CMS. Solutions are typically posted a few days after the due date, after which no late submissions will be accepted.

There will be two 72-hour takehome exams, open book and notes. No collaboration is allowed on the exams. Sign out the exam with the Course Administrator. Submit your solutions in person to the Course Administrator during business hours or a pdf file to CMS within 72 hours after signing it out. Exam solutions may be handwritten, but please write legibly.

Approximate weights: Homework 50%, exams 25% each.

Due dates (subject to change):

• HW1: 2/3
• HW2: 2/15
• HW3: 2/27
• HW4: 3/9
• Prelim: any 72-hour period from 3/9 to 4pm 3/30 except Spring break 3/17–26
• HW5: 4/11
• HW6: 4/23
• HW7: 5/4
• Final exam: any 72-hour period from 5/4 to 4pm 5/14.

Regarding the homework:

• We encourage you to work in small groups. It is more fun for you because you have others to bounce ideas off and you learn more, and it is more fun for us because we have less to grade.
• You do not have to form CMS groups to work in groups. Only one person in a group needs to submit the homework. We will transfer the grades to the collaborators.
• The preferred interpretation of collaboration on the homework is not "Dick does problem 1 and Jane does problem 2," but rather "Dick and Jane do problem 1 and Dick and Jane do problem 2."
• Whenever you give an algorithm, include a correctness argument if appropriate. Super formal proofs are not necessary, a good convincing argument will do.
• Give an analysis of the complexity of your algorithm if that is the point of the question. Again, there is no need to be overly formal.
• Please keep your solutions short and to the point. Brevity is the soul of good computer science.
• Your proofs should be crystal clear. We should not have to figure out why or how leaps of logic are true, even if they are. If you do not understand a step, it is better to be honest than to try to fake your way through. Use figures if they help the exposition. Avoid pseudo-code—a high-level explanation of an algorithm is better. If you must use pseudo-code, comment liberally.

Approximate Syllabus

The course is organized around a few fundamental themes. The exact coverage is subject to change. Topics below will be covered as time permits; we will probably not have time to cover everything.

• Greedy algorithms: spanning trees, Steiner trees, matroids, arborescences, and multicast cost-sharing. (Kozen Lec 1-2, Kleinberg-Tardos Ch 4)
• Advanced data structures: advanced heaps, self-organizing data-structures. (Kozen 8-13)
• Network flows: maximum flows and minimum cuts, the preflow-push algorithm, minimum-cost flows, multicommodity flows, and applications to matching, scheduling, network routing and vision. (Kleinberg- Tardos Ch 7, Kozen Lec 14, 16-20)
• Dynamic programming: basic dynamic programming technique, dynamic programming on trees, tree decomposition, and algorithms for graphs with bounded tree width. (Kleinberg- Tardos Ch 5)
• NP-completeness (Kozen Lec 21-25, Garey and Johnson, Kleinberg-Tardos Ch 8)
• Approximation algorithms: greedy algorithms, local search, on-line algorithms, primal-dual algorithms, linear programming. (Kleinberg-Tardos Ch 11)
• Randomized algorithms: basic techniques from discrete probability, and applications to optimization, distributed computation, and packet routing. (Kleinberg-Tardos Ch 13)
• Lower bounds for constant depth circuits: random partial valuations, Håstad switching lemma (Handout)
• Algorithms in algebra and number theory: Integer arithmetic, Csanky's algorithm, Chistov's algorithm, matrix rank, linear equations and polynomial gcds, FFT, Luby's algorithm, primality testing (Kozen Lec 30-40)