CPSC 351: Theoretical Foundations of Computer Science II
About This Course
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.
You will not be learning about “cutting-edge technology” in this course, and it will sometimes be difficult to point to applications of topics and skills in the workplace. As in CPSC 251, the focus is more on “foundational” knowledge and skills that you will need, in order to be ready for a later study of technology and applications like these. You certainly will have an an opportunity to study these things in courses after this one.
In particular, you will learn a little about material in areas called “automata theory” and “computability theory” that will help you to understand the limits of computation in this course. The study of discrete mathematics — specifically, discrete probability theory — that was started in CPSC 251 will also be continued here.
In Fall 2024, one section is available:
- L01, lectures 12:30–1:45pm, Tuesdays and Thursdays — a blended course: Lectures are web-based and synchronous. Tutorials and all class tests are in-person.
This is also a flipped course: Students will be expected to complete a reading assignment (or watch a video) before attending each lecture. The lecture time will be used to solve a problem that is related to the assigned reading and makes use of material introduced in it.
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 Fall 2024.
Course Outline
This sentence is a link to the outline for this course. `
Lectures and Tutorials
- Introduction and Mathematics Review
- Finite Automata and Regular Languages
- Turing Machines and Their Languages and Functions
- Computability
- Discrete Probability for Computer Science
- Conclusion of the Course
Online References
It should not be necessary to use additional references in order to do weil in this course. However, two freely available online references, covering course material, are as follows.
- D. C. Kozen, Automata and Computability
- D. Stirzaker, Probability and Random Variables: A Beginner’s Guide
Several other references that might also be useful, but that are not freely (and legally) available as ebooks, can be read about by following the link for “Recommended References”, below.
Additional Course Material
- More about Course Administration
- Recommended References
- Information about Assignments
- Information about Tests
