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 NPcompleteness 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: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
