Recommended References
The following material, and other reference material that you might find, cannot replace the lecture notes. They are provided to supplement these notes, in case a different explanation of information would be helpful — but none of them is required.
A Readable Introduction to Lots of the Course Material
- Michael Sipser, Introduction to the Theory of Computation, Third Edition, CENGAGE Learning, 2013: [ Library Access ]
Parts one and two of this text include the material about automata and computability theory found in CPSC 351 (but does not included that course’s material about discrete probability theory) so that it could, almost, be used as a textbook for that course. Part three is a (reasonably easily) readable introduction to complexity that includes a significant part of the material that will be discussed in CPSC 511/611.
In the past, this book has been too expensive to be used as a textbook. It appears that a much less expensive international edition is now available.
More Recent — and More Advanced — References
None of the following books seems to be suitable as a textbook for an undergraduate course. However, they may be of interest to students in CPSC 511 who wish to learn more about computational complexity theory after completing this course. CPSC 611 students may find them to be useful when choosing a topic for a course project and beginning project work.
Each is freely available to University of Calgary student, as an ebook available from the University of Calgary library.
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009: [ Ebook ]
- Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2012: [ Ebook ]
- Avi Wigderson, Mathematics and Computation: A Theory Revolutionizing Technology and Science, Princeton University Press, 2019: [ Ebook ]
