The course is intended for graduate students who have taken at least one upper division algorithms course. We will review some of the basics of algorithm analysis, but students without this background may find the pace a little quick.
We will look at problems coming from many areas of computer science to motivate our exploration of algorithm design and analysis techniques. The techniques include divide-and-conquer, dynamic programming, randomization, amortized analysis, and reduction. The types of problems we'll consider come from the following areas:
Graphs Matching, planarity, ...
Geometry Convex Hull, Voronoi Diagrams, ...
Strings Matching, compression, ...
On-line Page replacement, k-server, ...
Approximation Bin-packing, traveling salesman, scheduling, NP-hardness, hardness of approximation, ...
Linear Programming Network flows, duality, zero-sum games, ...
Cryptography RSA, zero-knowledge proofs, ...
We will have problem sets roughly every week. Problem set solutions count 40% of the final grade. I accept one late solution set (up to one week past the due date) per person per term. No more. Each problem set will have some straightforward problems and at least one challenging problem. You shouldn't feel that you must get all the problems, but you should at least think about them. You may work together discussing problems and course material, but you should write up and hand in your own solutions. Do not write up your solutions while looking at a reference or working with another person. If you do, you risk plagiarizing someone else's write-up (see the ``plagiarism'' section of the UBC calendar). If you do work with someone or use some outside source, you must acknowledge them in your write-up.
There will be one midterm, contributing 20% to the final grade, and one final exam, contributing 30% to the final grade. The remaining 10% of the final grade depends on class participation. Class participation includes typesetting your notes for one lecture so that they may be distributed to the rest of the class. You are the ``scribe'' for those lectures. Please sign up to scribe for a lecture as soon as possible.
Homework 1 due Jan 16 in class. solutions
Homework 2 due Jan 23 in class. solutions
Homework 3 due Jan 30 in class. solutions
Optional practice problems involving dynamic programming
(from Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
(second edition):
Problems 15-2, 15-3, 15-4, 15-5, 15-6.
Homework 4 due Feb 13 in class. solutions
Homework 5 due March 21 in class. solutions
Homework 6 due March 28 in class. solutions
Homework 7 due April 4 in class. solutions
An asterisk (*) means the notes are the final version.
1. Jan 4 ( * Wei Sun ) Stable Marriage and the Proposal Algorithm.
2. Jan 9 ( * C. Albert Thompson ) Average case analysis of the Proposal Algorithm.
3. Jan 11 ( * Huan Li ) Coupon collector. Markov's inequality.
4. Jan 16 ( * Naresh Kumar ) Random sampling to solve k-select.
5. Jan 18 ( * Simona Radu ) Analysis of k-select using Chebyshev's Inequality.
6. Jan 23 ( * Tatsuro Oya ) Adversary lower bound on k-select. Greedy scheduling.
7. Jan 25 ( * Emalayan Vairavanathan ) Dijkstra's algorithm. Dynamic programming scheduling.
8. Jan 27 [Makeup class ICCS X836] ( * Matt Dirks ) Bellman-Ford algorithm. All pairs shortest paths.
9. Jan 30 ( * Hao Yang ) Johnson's reweighting algorithm. A* search meets graph theory.
10. Feb 1 ( * Nuray Dindar ) Edit distance, LIS, LCS.
11. Feb 3 [Makeup class ICCS X836] ( * Jillian Slind ) Using LIS to solve LCS. Optimal triangulation of a convex polygon.
No class Feb 6
No class Feb 8
12. Feb 13 ( * Shuang Yu ) String matching using FSM, KMP-FSM.
Midterm Feb 15
No class Feb 20
No class Feb 22
13. Feb 27 ( * JingXian Li ) Boyer-Moore string matching.
14. Feb 29 ( * Chuan Zhu ) Linear programming.
15. Mar 2 [Makeup class ICCS X836] ( * Lan Wei ) Network Flow.
16. Mar 5 ( * Melissa Smith ) Bipartite Matching, Pennant Race, Open-Pit Mining.
17. Mar 7 ( * Shailendra Agarwal ) Linear programming duality.
18. Mar 9 [Makeup class ICCS X836] ( * Shuo Shen ) Two-player games. Online algorithms.
No class Mar 12
No class Mar 14
19. Mar 19 ( * Ying Xu ) LRU is k-competitive.
20. Mar 21 ( * Baipeng Han ) Randomized Marking Mouse. NP.
21. Mar 26 ( * Shu Yang ) NP completeness
22. Mar 28 ( * Sarwar Alam ) Approximation of Vertex Cover.
23. Apr 2 ( * Tatsuro Oya ) Approximation of scheduling, TSP, and clustering.
24. Apr 4 ( * Khamza Davletov )