Rather unusually, we have two instructors. Each instructor will deliver about half of the lectures, on a schedule that respects his other obligations.
|Jonathan Buss||jfbuss||DC 3353||Mondays 2:40–3:30|
|Richard Cleve||cleve||DC 2117||Wednesdays 2:40–3:30|
|Venkata Bommireddi||vabommir||Thu 2:00–3:00, DC 2305|
|Tiancong Wang||t258wang||Tue 11:00–12:00, DC 2582C|
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)
The online paradigm; competetive ratios. Basic examples. Cache management: lower bounds for deterministic algorithms; randomized algorithms.
____, 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).
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.
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)
Weiss, Chapter 11: sections 11.1, 11.2, 11.5.
CLRS: Chapter 35.
KT: Chapter 11, sections tba.
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.
|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.|