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
Notice/New: Final exam Part I is on Tuesday April 4th, not the date originally posted.
|Tue Feb 14||Mid-term exam (in class)|
|Thu Mar 9||No class|
|Tue Apr 4||Final exam part I|
|Thu Apr 6||Final exam part II|
Notice: Alina has extra office hours Wednesday March 22 from 10:00-12:00.
|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.
All assignments should be put in the assignment dropbox labelled COMP4804 in HP 3115.
- Assignment 3 is due Wednesday March 22nd.
- Assignment 2 is due Wednesday March 1st.
- 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
- Tue Feb 14: Mid-term exam
- Thu Feb 16: Guest lecture on graph planarity
- Tue Feb 28: Amortized analysis using the potential method
- Thu Mar 2: Splay trees
- Tue Mar 7: Guest lecture on Chebyshev's Inequality and median finding
- Thu Mar 9: Erik Demaine on Amortized Analysis
- Tue Mar 14: Approximation algorithms for the travelling salesman problem
- Thu Mar 16: Approximation algorithms for independent sets of squares and disks
- Tue Mar 21: Fixed-parameter tractable algorithms
- Thu Mar 23: Map labelling with a fixed font