CS 466: Algorithm Design & Analysis
Spring 2017

Official Outline

Important information also available in PDF format.

Instructors

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

EmailOfficeHours
Jonathan Buss jfbussDC 3353Mondays 2:40–3:30
Richard Cleve cleveDC 2117Wednesdays 2:40–3:30
If the listed hours don't suit you, either make an appointment, or simply drop by. (Email suffix: cs.uwaterloo.ca.)

Teaching Assistants

EmailOfficeHours
Venkata Bommireddi vabommirThu 2:00–3:00, DC 2305
Tiancong Wangt258wangTue 11:00–12:00, DC 2582C

Resource links

Lecture Modules

We will determine the precise extent of each module, and the interleaving between them, as we go.
  1. 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)

  2. 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).

  3. 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.

  4. Other uses of randomness (Cleve)
    Randomness for exponential-time problems: Satisfiability and counting.
  5. 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)

  6. Amortized analysis (Buss)
    Introduction. Splay trees.

    Readings:
    Weiss, Chapter 11: sections 11.1, 11.2, 11.5.

  7. Approximation algorithms (Buss)
    Measures of approximation. Examples: Vertex Cover, Set Cover, TSP▵
    Approximation schemes.

    Readings:
    CLRS: Chapter 35.
    KT: Chapter 11, sections tba.

  8. "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.

Assignments

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 PDF Tues., May 23 Randomized algorithms; probabilistic analysis
2 PDFWed., June 6 On-line algorithms (plus)
3 PDF Mon., June 19 Algorithms for satisfiability. Communication complexity
4 PDF Mon., July 10Quantum algorithms. Amortized analysis.
5 PDFMon., July 24 Approximation algorithms and analysis. Fixed-parameter analysis.