CS 466: Algorithm Design & Analysis
Important information also available
in PDF format.
Rather unusually, we have two instructors.
Each instructor will deliver about half of the lectures, on a schedule
that respects his other obligations.
If the listed hours don't suit you, either make an appointment, or
simply drop by. (Email suffix: cs.uwaterloo.ca.)
||jfbuss||DC 3353||Mondays 2:40–3:30
||cleve||DC 2117||Wednesdays 2:40–3:30
|| 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,
- [MU] Mitzenmacher and Upfal Probability and Computing,
- [MR]Motwani and Raghavan, Randomized Algorithms,
- [W] Weiss, Data Structures and Algorithm Analysis, 4th
edition, Pearson, 2014.
- Course Piazza
- Notes/exercises on finite
fields. A self-study module on finite
fields. More than you need for this course, but interesting nonetheless.
We will determine the precise extent of each module, and the
interleaving between them, as we go.
- Algorithms using randomness (Cleve)
Paradigms: foiling an adversary; abundance of witnesses. Examples:
sorting and searching; primality; polynomials; matrices.
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
____, Competitive Analysis: 6.046 Recitation Notes, November 3,
2006. Available at
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
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.
- "Fixed parameter" algorithms (Buss)
Introduction. Paradigms: bounded search; problem kernels.
Example problems/algorithms: graphs, string matching; program
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.
|1||PDF||Tues., May 23
||Randomized algorithms; probabilistic analysis
|2||PDF||Wed., June 6
||On-line algorithms (plus)