Fundamentals of Algorithm Design and Analysis: CPSC500
2017 Winter Term 1


The fundamentals covered in this class continue to prove invaluable in designing algorithms for a broad range of applications in network routing, computer systems, computational biology, and more. We'll also look at new variants of classical problems, and algorithms for these variants.

You will hone your algorithm design skills using techniques such as divide and conquer, induction and reduction, augmentation, linear programming and duality, dynamic programming, randomization and derandomization, as well as data structures that are useful for graphs and strings.. You will also have lots of opportunity to hone your ability to reason about the correctness and efficiency of algorithms.

You should be familiar with introductory topics in the design and analysis of algorithms, or able to learn these on your own. A good treatment of introductory material is Chapters 1 through 6 of Kleinberg and Tardos' "Algorithm Design". You should also have some level of comfort with the theory of NP-completeness and how it is used to show that certain combimatorial optimization problems are intractable. See Chapter 8 of Kleinberg and Tardos' text, at least through section 8.4. Chapters 3 and 4 of Mertens and Moore's text also has great coverage of this topic.



Place and Time
09:00-10: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 11-1
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
McGraw-Hill 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 9-10: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 Wrap-Up; Stochastic Games
In-class exercise relating to the Simplex algorithm
Mon, Oct 16 New Topic: String Algorithms
Exact Matching and the Knuth-Morris-Pratt 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 NP-hard Problems
See Kleinberg and Tardos Chapter 11
Mon Nov 6 Approximation Algorithms for NP-hard Problems, Continued
Wed, Nov 8 Approximation Algorithms for NP-hard 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 Introduction to Randomized Algorithms Part II
See slides by David Williamson for more on Max Sat
Homework 3
Wed, Nov 22 Introduction to Randomized Algorithms Part III
Mon, Nov 27
Wed, Nov 29
... ...
Fri, Dec 8 Project presentations, 12:30-4:30pm
Mon, Dec 11 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.