Theoretical Computer Science

CPSC 351: Theoretical Foundations of Computer Science II

General Course Information

Computer Science 351 is a second-year undergraduate course in the mathematical foundations of computer science, and an introduction to theoretical computer science, offered by the Department of Computer Science at the University of Calgary. It is a required course for students majoring in Computer Science.

This course will have a D2L course site which will be used for course communication and reporting of grades. All material, supplied to students for course work, will be made available on the D2L site. The page that you are reading now (and other pages linked to it) includes a subset of this material that can also be accessed by people outside this course. They pages are certainly “under construction” at this point, and they describe the course as it will be offered in Winter 2023.

Course Outline

The CPSC 351 outline is now available, and this sentence is a link to it.

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.

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 wll as probability and statistics — that will be used in this course.

Probability and Statistics

D. Stirzaker, Elementary Probability, Cambridge University Press

Each of the books that is listed above, for review of discrete mathematics, includes a chapter on probability theory. This chapter introduces (almost) everything about this subject that will be included in CPSC 351.

The other book, that is listed above, is a well regarded textbook on probability and statistics that goes well beyond the material included in CPSC 351. It is also freely available as an ebook, through the University of Calgary, 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
D. C. Kozen, Automata and Computability, Springer

Each 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. Kozen’s book might also be difficult for some students to read, but covers all the material that will be needed reasonably well.

Kozen’s text is much less expensive than the others, so students wishing to have a supplemental reference will find it to be an affordable choice.

Additional Information

Additional information about learning goals and course administration is included in the first lecture for this course.