Algorithms (F2008)

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)

Instructor: Suresh Venkatasubramanian (suresh AT cs DOT utah DOT edu), Room 3442, MEB
Office Hours: Tue 1-3pm
TA: Harsh Bhatia (harsh DOT bhatia AT utah DOT edu), WEB 3626
Office hours: Thu 1:30-3:30pm

Textbook: Algorithm Design, by Jon Kleinberg and Eva Tardos.