Course Outline
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
Important Dates
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/Assignment 4 |
| Thu Apr 6 | Final exam part II |
Office Hours
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.
Assignments
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.
Grading Scheme
| Assignments | 40% |
| Mid-term exam | 20% |
| Final exam | 40% |
Textbooks
There is no formal textbook for this course. I will add reading material here soon.
Lecture topics
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
- Tue Mar 28: Stacking blocks
