CMSI 385

Introduction to the Theory of Computation

Fall 2018

This page is maintained as an archival record of the course shown above, and as such, some links on this page may no longer be valid nor accessible. They are kept here as a record of the resources that were available at the time of the course offering.

In recognition of Dr. Philip Dorin’s seminal run of teaching this course for nearly 47 years, here is a link to his original syllabus for this course. My own final syllabus isn’t much different in substance, but just mostly reformatted to resemble my other classes.


Please see this Brightspace announcement for instructions on accessing the other assignments for this course.

Video Links and Takeaway Notes

Finite state automata (9 parts)

Closure and nondeterminism (9 parts)

The pumping lemma (10 parts)

Minimizing finite state machines (9 parts)

Context-free languages (8 parts)

Context-free languages and compilers (9 parts)

Pushdown machines/automata (9 parts)

Context-free grammars and nondeterministic pushdown machines (9 parts)

More lemmas; the CYK algorithm (10 parts)

Undecidability and context-free languages (8 parts)

The bullseye (10 parts)

Turing machines (10 parts)

The halting problem (7 parts)

Decidability (8 parts)