This is an advanced course about the design and analysis of algorithms. The main topics covered in this course are:
- Randomized algorithms and probabilistic analysis
- Amortized analysis
- Coping with NP-hard problems
- Exponential-time algorithms
- Fixed-parameter tractable algorithms
- Approximation algorithms
|Tue Feb 14||Mid-term exam (in class)|
|Thu Mar 30||Extra-long class|
|Thu Apr 6||Final exam (in class)|
|Alina Shaikhet||Tuesday 10:00–11:30|
|Pat Morin||Thursday 10:30–11:30 (or by appointment)|
Alina also has an extra two hours of office hours on the days assignments are due.
Notice: Alina will have no office hours Tuesday February 28, but will have office hours from 10:00–13:30 on Wednesday March 1.
All assignments should be put in the assignment dropbox labelled COMP4804 in HP 3115.
- Assignment 2 is due Wednesday March 1st. This assignment has been updated; some parts of Question 3 were accidentally included in Question 2.
- Assignment 1 is due Wednesday January 25th.
- Assignment 1 sample solutions.
There is no formal textbook for this course. I will add reading material here soon.
The notes here are created by me when preparing for class. I do appreciate it if you point out any errors you find in them.
- Thu Jan 5: Review of basic probability
- Tue Jan 10: Closest pair and linear programming
- Thu Jan 12 and Tue Jan 17: Fingerprinting
- Thu Jan 19: Binary space partition trees
- Reference: Basic probablity worksheet
- Tue Jan 24: Conditional probability, dependence, and Markov's Inequality
- Thu Jan 26: Randomized min-cut algorithms
- Tue Jan 31: Chernoff's Bounds
- Thu Feb 2: Chernoff's bounding method
- Tue Feb 7: Growing a random spanning tree
- Thu Feb 9: Mid-term review study questions (Up to Page 23), important facts, sample midterm