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.
  4. Other uses of randomness (Cleve)
    Randomness for exponential-time problems: Satisfiability and counting.
    Randomization to save space usage.
  5. Quantum algorithms (Cleve)
    Algorithms with entanglement. Deutsch's algorithm. Grover search.
  6. Amortized analysis (Buss)
    Introduction. Splay trees.
  7. Approximation algorithms (Buss)
    Measures of approximation. Examples: Vertex Cover.
    Approximation schemes.
  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 (tentative)
1PDFTues., May 23 Randomized algorithms; probabilistic analysis
2PDFWed., June 6 On-line algorithms (plus)
3TBATBATBA
4TBATBATBA
5TBATBATBA