Place and Time
09:0010:30 MW
101 DMP
Instructor
Anne Condon
Office: X551 CS
Email: condon at cs.ubc.ca
Office Hours: After class or by appointment
Teaching Assistant
Coulter Beeson
Email: cdbees at cs.ubc.ca
Office Hours: Mon 111
Location: Demco Learning Centre
Piazza Course Website
CPSC 500 on Piazza
Use this to communicate with other students, Coulter and Anne
Resources
Algorithm Design
by Jon Kleinberg and Eva Tardos
Pearson, 2014
The Nature of Computation
by Christopher Moore and Stephen Mertens
Full text online in the UBC Library
Algorithms, Etc.
Lecture Notes by Jeff Erikson
Algorithms
by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani
McGrawHill Education, 2006
Algorithms on Strings, Trees, and Sequences
by Dan Gusfield, Cambridge University Press

Course Schedule
Date 
Resources 
Wed, Sep 6 
Course Overview; Stable Matching
Reading:
Lecture Slides by Kevin Waybe
Survey paper on the Hospitals/Residents Problem by David F. Manlove
Practice Homework 1



Mon, Sep 11 
A Hardness Result for Stable Matchings with Ties
A slightly more general proof can be found in
Hard Variants of Stable Marriage by Manlove et al.

Wed, Sep 13 
Hardness Result Completed; A Variant of Stable Matching
Network Flow, see Kleinberg and Tardos, Chapter 7



Mon, Sep 18 
Network Flow, Continued, see Kleinberg and Tardos, Chapter 7
and also Jeff Erickson's online notes

Wed, Sep 20 
Network Flow, Completed
Homework 1 (due Oct 4)
Project information (deadline for choosing topic is Oct 13)



Mon, Sep 25 
Anne will be away, so class will be cancelled. Use the time to get
started on selecting a project topic, and work on your homework.

Wed, Sep 27 
Anne will be away, so class will be cancelled.
TA Coulter Beeson will have office hours during class time, from 910:30am.

Mon, Oct 2 
Introduction to Linear Programming and its Applications, see the text by
Dasgupta et al.

Wed, Oct 4 
Three Applications of Linear Programming and Duality
Practice Homework 2

Mon, Oct 9 
Thankgiving Holiday

Wed, Oct 11 
Linear Programming WrapUp; Stochastic Games
Inclass exercise relating to the Simplex algorithm

Mon, Oct 16 
New Topic: String Algorithms
Exact Matching and the KnuthMorrisPratt Algorithm
See Gusfield's text, Chapter 2.3
Other good treatments of the algorithm are by
Charras and Lecroq and
Epstein.

Wed, Oct 18 
Introduction to Suffix Trees and their Applications
See Gusfield's text, Chapter 5
Other good treatments are by
Kay and
Gusfield.
This
visualization of Ukkonen's algorithm is also helpful.

Mon, Oct 23 
More on Ukkonen's Algorithm for Suffix Tree Construction

Wed, Oct 25 
Ukkonen's Algorithm Efficiency, and More Applications
Homework 2 (due Nov 8)

Mon, Oct 30 
Inexact Matching, Sequence Alignment

Wed, Nov 1 
Approximation Algorithms for NPhard Problems
See Kleinberg and Tardos Chapter 11

Mon Nov 6 
Approximation Algorithms for NPhard Problems, Continued

Wed, Nov 8 
Approximation Algorithms for NPhard Problems, Continued
Practice Homework 3

Mon, Nov 13 
Remembrance Day Holiday

Wed, Nov 15 
Introduction to Randomized Algorithms
See Kleinberg and Tardos, Chapter 13, also lecture notes
by Nick Harvey
and
Anna Karlin

Mon, Nov 20 
Randomized Algorithms Part II
See
slides by David Williamson for more on Max Sat
Homework 3

Wed, Nov 22 
Randomized Algorithms Part III

Mon, Nov 27 
Randomized Algorithms Part IV

Wed, Nov 29 
Limits to Approximation of NPhard Problems

... 
...

Fri, Dec 8 
Project presentations, 12:304:00pm, 8th Floor Boardroom (Room X836 ICCS/CS)
Take Home Final Exam will be ready. You can decide when you are ready to take
it, up until Tue Dec 19. You will have 48 hours to work on the exam once you
get it.
And here is a
practice final.

