Please note that some material may be restricted to users that are connected to the UBC network. Students registered for the course that would like to access the material from outside the UBC network should first connect to the UBC VPN.
Textbook
We will use the book by Dasgupta, Papadimitirou and Vazirani that is available online — at no $ cost — in an almost-final form. (A local copy of the book by Dasgupta et al. is available here.) On occasion, we will supplement these notes with more material (typically available as PDF files).
Other books
Some of the basic discussion regarding logic, proofs, etc. can be found in standard textbooks on discrete mathematics (e.g., Rosen’s, Epp’s, Bogart-Drysdale-Stein’s). For topics specific to algorithms, the book by Cormen, Leiserson, Rivest and Stein is a good reference, as are notes prepared by Jeff Erickson (at the University of Illinois) that are both free and available online.
Preliminaries
Some of the material will be considered preliminaries because most students would have covered such topics in high school and introductory mathematics courses.
There are several textbooks on discrete mathematics that cover the material comprehensively. Students may want to refer, on occasion, to any one of the following suggested books. (Nominally, any edition should be suitable and you can consult copies held by the UBC Library.)
- Discrete Mathematics for Computer Scientists, 1st edition, Clifford Stein, Scott Drysdale and Kenneth Bogart, Addison Wesley.
- Discrete Mathematics and Its Applications, 6th edition, Kenneth H. Rosen, McGraw Hill.
- Discrete Mathematics, Douglas E. Ensley and J. Winston Crawley, John Wiley and Sons.
- Discrete Mathematics with Applications, 3rd edition, Susanna S. Epp, Brooks/Cole.
Alternatives to a printed book are a set of course notes on discrete structures from Rafael Pass and Wei-Lung Tseng at Cornell University or a book on Mathematics for Computer Science by Eric Lehman, Tom Leighton and Albert Meyer at MIT.
Familiarity with certain data structures (lists, stacks, queues, binary trees and binary search trees) will be assumed. Other data structures will be introduced when appropriate, sometimes exclusively through readings. Pat Morin’s Open Data Structures is a good reference for material on data structures and their implementation.