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.

Readings:

M. Saks, A. Wigderson, "Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees", Foundations of Computer Science (27th Annual Symposium), IEEE, 1986, pp. 29–38. DOI: 10.1109/SFCS.1986.44. Also available via Wigderson's home page. - Other uses of randomness (Cleve)

Randomness for exponential-time problems: Satisfiability and counting. - Quantum algorithms (Cleve)

Algorithms with entanglement. Deutsch's algorithm. Grover search.Readings (four to choose from):

Ronald de Wolf (chapters 1 & 2)

Umesh Vazirani (lecture 1)

David Mermin (lectures 1 & 2)

Richard Cleve (lectures 1 & 2) - Amortized analysis (Buss)

Introduction. Splay trees.Readings:

Weiss, Chapter 11: sections 11.1, 11.2, 11.5. - Approximation algorithms (Buss)

Measures of approximation. Examples: Vertex Cover, Set Cover, TSP▵

Approximation schemes.Readings:

CLRS: Chapter 35.

KT: Chapter 11, sections tba. - "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.~~

Number | Link | Due date | Topic |
---|---|---|---|

1 | Tues., May 23 | Randomized algorithms; probabilistic analysis | |

2 | Wed., June 6 | On-line algorithms (plus) | |

3 | Mon., June 19 | Algorithms for satisfiability. Communication complexity | |

4 | Mon., July 10 | Quantum algorithms. Amortized analysis. | |

5 | Mon., July 24 | Approximation algorithms and analysis. Fixed-parameter analysis. |