# 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

Tue Feb 14 | Mid-term exam (in class) |

Thu Mar 30 | Extra-long class |

Thu Apr 6 | Final exam (in class) |

# Office Hours

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.

# Assignments

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.

# 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