Spring 2018

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 Kleenes Theorem; context-free grammars, pushdown automata, the correspondence theorem and the pumping lemma; computability, Turing machines, and the halting problem.

Prerequisite: COS 250.

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 Submissions

Goals

Student Learning Outcomes

Contact Information

Online Resources

Grading Scheme

Policies

Programming

Schedule

Textbook and Readings

Exercises, Homeworks, Tests, and Notes

Homework Submissions

- Please read the newsgroup for timely announcements.
- Class newsgroup: Local group umaine.cos451 on NNTP server creak.um.umaine.edu. Web interface to get started: http://chaw.eip10.org/news/.
- The most recent version of this document may be found at http://chaw.eip10.org/cos451/.
- 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.
- Please use the PDF version of this document for printing and reference: cos451.pdf