and

COS 550: Theoretical Computer Science

Fall 2024

This course is an introduction to the theory of computation. Some big questions: What is a computer? How may we model computers and computation? What are the theoretical and practical limits of computation? What do we know about what can, and cannot, and may or may not be computable and eﬃciently computable? Some more details, from the course catalog: Fundamentals of formal languages and the mathematical theory of computation; ﬁnite-state automata, nondeterminism, regular expressions, and Kleene’s Theorem; context-free grammars, pushdown automata, the correspondence theorem and the pumping lemma; computability, Turing machines, and the halting problem.

Prerequisites: COS 301; programming maturity.

COS 550 is the graduate version of this course, which shares most class meetings and coursework with the undergraduate version (COS 451) but that includes additional coursework and is assessed to a higher standard.

Goals and Learning Objectives

Goals

Student Learning Outcomes

Contact Information

Online Resources

Grading Scheme

Policies

Programming

Schedule

Textbook and Readings

Exercises, Homeworks, Tests, and Notes

Homework and Project Submissions

Keys to Success

Goals

Student Learning Outcomes

Contact Information

Online Resources

Grading Scheme

Policies

Programming

Schedule

Textbook and Readings

Exercises, Homeworks, Tests, and Notes

Homework and Project Submissions

Keys to Success

- Some sections below point to material in separate documents that are found on the class Web site, linked from the online version of this document.
- The most recent version of this document may be found at http://chaw.eip10.org/cos451/.
- Please use the PDF version of this document for printing and reference: cos451.pdf
- Brightspace site (access limited): https://courses.maine.edu/d2l/home/360915.