Spring 2017

Rather unusually, we have two instructors. Each instructor will deliver about half of the lectures, on a schedule that respects his other obligations.

Office | Hours | ||
---|---|---|---|

Jonathan Buss | jfbuss | DC 3353 | Mondays 2:40–3:30 |

Richard Cleve | cleve | DC 2117 | Wednesdays 2:40–3:30 |

Office | Hours | ||
---|---|---|---|

Venkata Bommireddi | vabommir | Thu 2:00–3:00, DC 2305 | |

Tiancong Wang | t258wang | Tue 11:00–12:00, DC 2582C |

- On reserve in the DC library:
- [CLRS] Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 3rd edition. MIT Press, 2009.
- [KT] Kleinberg and Tardos, Algorithm Design, Addison-Wesley, 2005.
- [MU] Mitzenmacher and Upfal Probability and Computing, Cambridge, 2005.
- [MR]Motwani and Raghavan, Randomized Algorithms, Cambridge, 1995.
- [W] Weiss, Data Structures and Algorithm Analysis, 4th edition, Pearson, 2014.

- Course Piazza page
- Notes/exercises on finite fields. A self-study module on finite fields. More than you need for this course, but interesting nonetheless.
- …

- Algorithms using randomness (Cleve)

Paradigms: foiling an adversary; abundance of witnesses. Examples: sorting and searching; primality; polynomials; matrices.Readings:

MR, Secs. 7.2 & 7.3 (polynomial identities, Schwartz-Zippel lemma)

MR, Prob. 7.8 (perfect matching)

MU, Sec. 1.4 (min-cut via Karger's algorithm) - On-line algorithms (Buss)
The online paradigm; competetive ratios. Basic examples. Cache management: lower bounds for deterministic algorithms; randomized algorithms.

Readings:

____, Competitive Analysis: 6.046 Recitation Notes, November 3, 2006. Available at https://people.csail.mit.edu/sukhaj/6.046/rec9.pdf

CLRS, 5.4.4 (114–117).

Weiss, 10.1.3 (459–467).

KT, 13.8 (750–758). - Computing with decision trees (Cleve)

The decision-tree model. Kinds of decision trees. Upper and lower bounds for deterministic and for randomized algorithms.

- Other uses of randomness (Cleve)

Randomness for exponential-time problems: Satisfiability and counting.

Randomization to save space usage. - Quantum algorithms (Cleve)

Algorithms with entanglement. Deutsch's algorithm. Grover search. - Amortized analysis (Buss)

Introduction. Splay trees. - Approximation algorithms (Buss)

Measures of approximation. Examples: Vertex Cover.

Approximation schemes. - "Fixed parameter" algorithms (Buss)

Introduction. Paradigms: bounded search; problem kernels.

Example problems/algorithms: graphs, string matching; program compilation.

The treewidth measure of graphs. Algorithms for bounded treewidth.

Each of the five assignments will correspond to a few connected lectures by one of the instructors. We aren't sure how eight modules correspond to five assignments, but we'll let you know once we find out.