$\new­com­mand{\R}{\mathbb{R}}\De­clar­e­Math­Op­er­a­tor{\E}{\mathbf{E}}\De­clar­e­Math­Op­er­a­tor{\deg}{deg}$

Course Out­line

This is an ad­vanced course about the de­sign and analy­sis of al­go­rithms. The main top­ics cov­ered in this course are:

• Ran­dom­ized al­go­rithms and prob­a­bilis­tic analy­sis
• Amor­tized analy­sis
• Cop­ing with NP-hard prob­lems
  • Ex­po­nen­tial-time al­go­rithms
  • Fixed-pa­ra­me­ter tractable al­go­rithms
  • Ap­prox­i­ma­tion al­go­rithms

Im­por­tant Dates

No­tice/New: Final exam Part I is on Tues­day April 4th, not the date orig­i­nally posted.

Tue Feb 14	Mid-term exam (in class)
Thu Mar 9	No class
Tue Apr 4	Final exam part I/As­sign­ment 4
Thu Apr 6	Final exam part II

Of­fice Hours

No­tice: Alina has extra of­fice hours Wednes­day March 22 from 10:00-12:00.

Alina Shaikhet	Tues­day 10:00–11:30
Pat Morin	Thurs­day 10:30–11:30 (or by ap­point­ment)

Alina also has an extra two hours of of­fice hours on the days as­sign­ments are due.

As­sign­ments

All as­sign­ments should be put in the as­sign­ment drop­box la­belled COM­P4804 in HP 3115.

• As­sign­ment 3 is due Wednes­day March 22nd.
• As­sign­ment 2 is due Wednes­day March 1st.
• As­sign­ment 1 is due Wednes­day Jan­u­ary 25th.
• As­sign­ment 1 sam­ple so­lu­tions.

Grad­ing Scheme

As­sign­ments	40%
Mid-term exam	20%
Final exam	40%

Text­books

There is no for­mal text­book for this course. I will add read­ing ma­te­r­ial here soon.

Lec­ture top­ics

The notes here are cre­ated by me when prepar­ing for class. I do ap­pre­ci­ate it if you point out any er­rors you find in them.

• Thu Jan 5: Re­view of basic prob­a­bil­ity
• Tue Jan 10: Clos­est pair and lin­ear pro­gram­ming
• Thu Jan 12 and Tue Jan 17: Fin­ger­print­ing
• Thu Jan 19: Bi­nary space par­ti­tion trees
• Ref­er­ence: Basic prob­a­blity work­sheet
• Tue Jan 24: Con­di­tional prob­a­bil­ity, de­pen­dence, and Markov's In­equal­ity
• Thu Jan 26: Ran­dom­ized min-cut al­go­rithms
• Tue Jan 31: Cher­noff's Bounds
• Thu Feb 2: Cher­noff's bound­ing method
• Tue Feb 7: Grow­ing a ran­dom span­ning tree
• Thu Feb 9: Mid-term re­view study ques­tions (Up to Page 23), im­por­tant facts, sam­ple midterm
• Tue Feb 14: Mid-term exam
• Thu Feb 16: Guest lec­ture on graph pla­narity
• Tue Feb 28: Amor­tized analy­sis using the po­ten­tial method
• Thu Mar 2: Splay trees
• Tue Mar 7: Guest lec­ture on Cheby­shev's In­equal­ity and me­dian find­ing
• Thu Mar 9: Erik De­maine on Amor­tized Analy­sis
• Tue Mar 14: Ap­prox­i­ma­tion al­go­rithms for the trav­el­ling sales­man prob­lem
• Thu Mar 16: Ap­prox­i­ma­tion al­go­rithms for in­de­pen­dent sets of squares and disks
• Tue Mar 21: Fixed-pa­ra­me­ter tractable al­go­rithms
• Thu Mar 23: Map la­belling with a fixed font
• Tue Mar 28: Stack­ing blocks