This course is over. Here is the
list of final marks.
Course outline
This is an advanced course on the design and analysis of computer
algorithms. The four main areas covered in the course are:
- Randomized algorithms and probabilistic analysis
- Amortized analysis
- P versus NP
- Coping with NP-hard problems, including
- Exponential-time algorithms
- Fixed-parameter tractable algorithms
- Approximation algorithms
Assignments
Assignments will be posted here as they are ready. Assignments should
be submitted in the assignment drop box in Room 3115HP.
A good place to post questions about assignments and course material is the COMP 4804 Forum. I will be monitoring this forum and will try to answer questions. You may get help from other students there as well.
Course notes
The following books are useful references. Most of the material in
the course is taken from Cormen et al.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and
Clifford Stein. Introduction to Algorithms. 3rd edition,
McGraw-Hill, 2009.
- Sheldon M. Ross. Probability Models for Computer Science.
Harcourt/Academic Press, 2002.
In addition, the following images are scanned from my personal
course notes. They are quite terse and probably only useful as a
reminder of what was talked about in class.
| Date |
Topics |
References |
|
Steve Seiden's incredible Theoretical
Computer Science Cheat Sheet! |
|
The
top 10 algorithms of all time! |
|
Introductory lecture |
| Jan 7 |
Basic probability
C Code for sorting algorithms
|
App C of CLRS |
| Jan 12 |
Analysis of insertion sort |
| Jan 14 |
Analysis of random binary search trees
(quicksort) using indicator variables |
Sec 7.4 of CLRS |
| N/A |
Analysis of random binary search trees,
quicksort and find using records |
| Jan 14 |
Binary space partition trees |
| Jan 19 |
Universal hashing
C code for hashing |
Ch 11 of CLRS
pages 25-26 here |
| Jan 21 |
The Karp-Rabin string matching
algorithm
with an extension to
don't cares
C code for Karp-Rabin |
Sec 32.2 of CLRS |
| Print |
Basic probability worksheet |
| Jan 26 |
Conditional probability and independence,
Markov's inequality |
App C of CLRS |
| Jan 28 |
A Monte-Carlo Min-Cut algorithm |
| Feb 2 |
Chernoff's bounds
pi.c, guesser.c,
rbs.c |
App C.5 and Ch 12.4 of CLRS |
| Feb 4 |
Proofs of Markov's and Chernoff's bounds |
App C.5 of CLRS and here |
| Feb 8 |
Michiel Smid's notes on amortized analysis |
Ch 17 of CLRS |
| Feb 11 |
Amortized analysis of 2-4 Trees |
| Study |
Midterm exams from
2003,
2004,
2005,
2006,
and 2010
(solutions) |
| Feb 25 |
Midterm exam |
| Mar 2 |
Polynomial time, P, NP, NP-hardness, NP-completeness |
Ch 34 in CLRS |
| Mar 4 |
Branch-and-bound for TSP
|
|
| Mar 9 |
TSP Approximation Algorithms
C code for brute-force, branch-and-bound, MST heuristic, and Christofides' heuristic
| Sec 35.2 of CLRS |
| Mar 11 |
Approximation and Fixed-Parameter Tractable Algorithms
for VERTEX-COVER |
| Mar 15 |
Algorithms for and hardness-of-approximation of clustering |
Sec 8.5 here |
| Mar 18 |
Approximations for MIS of squares and unit disks |
| Mar 23 |
Map labelling with fixed-font labels |
| Mar 25 |
Map labelling with fixed-font labels |
this paper |
| Mar 30 |
A brief history of algorithms |
notes |
| Mar 32 |
Exam Review
Final exam 2006
Master list of questions |
|
Office hours
My office hours are Tuesdays from 14:00-16:00 in room 5177HP. Any
other meeting time will have to be arranged by email. The TAs have office hours
in room 1175 HP at the following times:
| Dan Chen |
Thursdays | 14:00-16:00 |
| John Howat |
Wednesdays | 14:00-16:00 |
Grading scheme
Grades will be assigned using the following grading scheme.
| Assignment 1 | 10% |
| Assignment 2 | 10% |
| Midterm exam | 20% |
| Assignment 3 | 10% |
| Assignment 4 | 10% |
| Final exam | 40% |
| Total | 100% |
I may, at my discretion, increase the grades of certain students to
raise the class average or change the distribution. This will never
cause a student's grade to go down, nor will it change the relative
rankings of students so, e.g., it is not possible for a student who
earned an 80% to receive a lower grade than a student who earned a
75%.
Important dates
The following is a (tentative) schedule for assignments and
exams.
| Jan. 26 | Assignment 1 due |
| Feb. 9 and 11 | Guest lecturer, office hours cancelled |
| Feb. 23 | Assignment 2 due |
| Feb. 25 | Midterm exam |
| Mar. 15 | Assignment 3 due |
| Apr. 6 | Assignment 4 due |
| TBA | Final exam |
Policy regarding unoriginal work
Students are encouraged to collaborate on assignments, but at the
level of discussion only. That is, they may work together to solve
problems, but when writing down the solutions they should do so on
their own. No student should show another student his or her written
solutions.
Any student who is caught submitting work that they did not do
themselves will have the relevant material sent to the dean, who will
decide on the appropriate action.
Students with Special Needs
Students with special needs should obtain documentation from the
Paul-Menton Center and notify me as soon as possible.