Graduate Algorithms

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. The history of algorithms, computability, and efficiency. The difference between a problem and an algorithm. Administrivia.
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: Sequence alignment
7. [KT 4] Greedy Algorithms: Optimality principles, examples
8. [KT 4] Greedy Algorithms: MSTs
9. [KT 8] NP-hardness: P vs NP. “Trust, but verify”. The Cook-Levin theorem & CIRCUIT-SAT
10. [KT 8] NP-hardness: Recap, 3SAT is NP-Complete. Reduction from Independent Set to Vertex Cover
11. [KT 8] CLIQUE, Independent Set, Set Cover, classification of types of NP-hard problems.

---

12. [KT 11] Approximation Algorithms: Definitions, Vertex Cover.
13. Approximation Algorithms: Vertex Cover 2-approx, Interval scheduling, Set Cover
14. [KT 11] Approximation Algorithms: Dynamic programming and PTASs (Knapsack, and a cameo by TSP)
15. [KT 11] Approximation Algorithms: LPs and Rounding.

---

16. [KT 7] Network Flows: Max flows and Ford-Fulkerson
17. [KT 7] Network Flows: Max flows and min cut
18. Network Flows: Min-cost max flows
19. [KT 7] Network flows: Applications

---

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

---

24. War Story: Sorting out the genome
25. [KT 12] Heuristic methods
26. Parallel Algorithms
27. Quantum Computing
28. A whirlwind tour of what we didn’t cover.
29. Wrap up.

Critical dates for homeworks/exams: these are tentative, but as requested, I’m giving them out here. Hopefully, changes to these dates will be minor.

1. HW 1. OUT 9/10, IN 9/24
2. HW 2. OUT 9/24, IN 10/5 (fall break starts the following day)
3. HW 3. OUT 10/22, IN 10/29
4. HW 4. OUT 10/29, IN 11/12
5. HW 5. OUT 11/12, IN 11/26
6. HW 6. OUT 11/26, IN 12/05

Midterm: Oct 17 (most likely a take-home handed out in class, to be turned in on Oct 19)

Final: TBA (there are some date constraints with students in the class). According to university guidelines, the final exam should be scheduled on Monday Dec 10 in class and I’ll likely do that. It’ll still be a take-home.

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:

• NP-Completeness and reductions.
• Greedy algorithms (and matroids) and dynamic programming
• Linear programming
• Approximation algorithms.
• Randomization

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 class textbook is Algorithm Design, by Jon Kleinberg and Éva Tardos.There will be 5-6 homeworks, and a final exam (and probably one midterm). The homeworks will be mostly pen-and-paper assignments.