Algorithms (F2008)

Homeworks:

• We will have between 6-7 homeworks, of which you may drop one.
• Homeworks must be submitted electronically or on paper by 5pm the day the assignment is due. Paper assignments will be submitted to the TA.

Exams:

• There will be one midterm and one final. Both will be take-home exams.

Grading:

• The rough weighting will be 50% homeworks, 20% midterm, and 30% final.

Late policy:

• All homeworks submitted after the due date will be subject to a 10% penalty per day following the due date (not counting weekends). After a week, no credit will be given. You get one bye, which allows you to submit one assignment upto a week late with no penalty.

Office hours:

• My office hours will be Tuesday 1-3pm, or by appointment.
• Harsh Bhatia’s office hours will be announced shortly.

This is a lecture outline for the class. When appropriate, I will reference chapters and sections from the textbook (KT 3 refers to Chapter 3). This outline is subject to minor changes, but I expect that the top level topics will be covered in the corresponding order.

1. Introduction. Administrivia. Pancake Sorting and genome rearrangement, as an example of the idea of abstractions and algorithms.
2. Analysing recurrence relations (see Quicklinks)
3. [KT 5] Divide & Conquer/Recursion: Mergesort, closest pair, integer multiplication
4. [KT 5] Divide & Conquer/Recursion: FFTs
5. [KT 6] Dynamic Programming: Interval scheduling, curve fitting, subset-sum.
6. [KT 6] Dynamic Programming: Shortest Paths
7. [KT 4] Greedy Algorithms: Optimality principles, examples
8. [KT 4] Greedy Algorithms: MSTs

---

9. [KT 7] Network Flows: Max flows, Ford-Fulkerson and min-cuts
10. [KT 7] Network Flows: Faster algorithms
11. Network Flows: Variations on a theme
12. [KT 7] Network flows: Applications

---

13. [KT 8] NP-hardness: P vs NP. “Trust, but verify”. The Cook-Levin theorem & CIRCUIT-SAT
14. [KT 8] NP-hardness: Recap, 3SAT is NP-Complete. Reduction from Independent Set to Vertex Cover
15. [KT 8] CLIQUE, Independent Set, Set Cover, and others

---

16. [KT 11] Approximation Algorithms: Definitions, Vertex Cover.
17. Approximation Algorithms: Vertex Cover 2-approx, Interval scheduling, Set Cover
18. [KT 11] Approximation Algorithms: Dynamic programming and PTASs (Knapsack, and a cameo by TSP)

---

19. Randomized Algorithms: Hashing
20. [KT 13] Randomized Algorithms: Min cut
21. Randomized algorithms: Algebraic fingerprinting
22. [KT 13] Randomized Algorithms: Chernoff Bounds
23. Randomized Algorithms: More examples

---

24. [KT 12] Heuristic methods
25. Zero Knowledge
26. Quantum Computing
27. Wrap up.

Dates for homeworks/exams: to be announced soon.

The study of algorithms is, at one level, the study of techniques driven by rigorous formal analysis: divide and conquer, greedy algorithms, recursion, O() notation and the like. At another level, algorithms are about abstraction: what is the core computational structure underlying a problem, and how might we unlock it ?

In this course, we will study algorithms at the level of techniques, and at the level of structure. Formalization, a key step in the practice of using algorithms, will play an important role in this class. Specific topics to be covered include:

• Algorithmic paradigms like divide and conquer, greedy algorithms, and dynamic programming
• Flow algorithms
• Randomization
• NP Completeness, and reductions
• Approximation algorithms (and a brief intro to linear programming)
• Miscellaneous topics

Some of these topics (the last three most notably) can command an entire course of their own; our coverage will emphasize the basics, covering a few of the most common ideas in play.

The textbook will be Algorithm Design, by Jon Kleinberg and Eva Tardos (it’s linked in the sidebar to the right)