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.
Homework 3 due Jan 30 in class.
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.
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 )
8. Jan 27 [Makeup class ICCS X836] ( * Matt Dirks )
9. Jan 30 ( Hao Yang )
10. Feb 1 ( Nuray Dindar )
11. Feb 3 [Makeup class ICCS X836] ( Jillian Slind )
No class Feb 6
No class Feb 8
12. Feb 13 ( Shuang Yu )
Midterm Feb 15
No class Feb 20
No class Feb 22
13. Feb 27 ( JingXian Li )
14. Feb 29 ( Ying Yu and Chuan Zhu )
15. Mar 2 [Makeup class ICCS X836] ( Shu Yang and Lan Wei )
16. Mar 5 ( Melissa Smith )
17. Mar 7 ( Shailendra Agarwal )
18. Mar 9 [Makeup class ICCS X836] ( Shuo Shen )
No class Mar 12
No class Mar 14
19. Mar 19 ( Suman Mukherjee )
20. Mar 21 ( Baipeng Han and Xin Chen )
21. Mar 26 ( Abhishek Baranwal )
22. Mar 28 ( Martin Lesmana )
23. Apr 2 ( Daria Bondareva )
24. Apr 4 ( Khamza Davletov and Sarwar Alam )