# 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 |

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