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 this other material is required.
Review: Discrete Mathematics
- S. S. Epp, Discrete Mathematics with Applications, Brooks/Cole — CENGAGE Learning
- K. H. Rosen, Discrete Mathematics and Its Applications, McGraw-Hill
The first of these books has been used as a textbook or recommended reference for MATH 271 for several years, while the second has been used in CPSC 251, so that students might be have access to one or the other, depending on the prerequisite they completed. Neither is required for this course, but each includes all the material in discrete mathematics — as well as most of the material about probability and statistics — that will be used in this course.
Probability and Statistics
- D. Stirzaker, Probability and Random Variables: A Beginner’s Guide, Cambridge University Press
Each of the recommended references for discrete mathematics includes a chapter on probability theory, which includes most of the material about this that will be discussed in CPSC 351.
The other book, listed above, is a readable introduction to “discrete probability theory” that includes everything about this subject, found in CPSC 351, that is not included in the textbooks on discrete mathematics — and a little more, as well. It is also freely available as an ebook, through the University of Calgary library, and this sentence is a link to that ebook.
Automata and Computability Theory
- M. Sipser, Introduction to the Theory of Computation, CENGAGE Learning
- J. E. Hopcroft, R. Motwani, and J. D. Ullman, Automata Theory, Languages, and Computation, Pearson Education
Both of the above references can be used as a supplement for the rest of the material in CPSC 351 — but they cover this material differently. Sipser’s text is easiest to read and is a very good reference for finite automata and regular languages — but I do not recommend it very highly as a reference for “computability”. Hopcoft, Motwani, and Ullman’s text is at a somewhat higher reading level and is, generally, a good reference for all the material about automata and computability included in this course.
