CMSC 415: Theory of computation

Fall 2018

Prof. Blaheta

Welcome to CMSC 415! Computation theory is an exploration of the question of what it even means for something to be computable. Some of the earliest results that can now be identified as computer science—at the time seen as mathematical or philosophical facts—are in the area of theory of computation. Other areas of theory are questions that remain open after more than a half-century of work. In this course, we will ask some of these questions and develop an appreciation and understanding of the answers that the early computer scientists produced for them.

The textbook for this course is Michael Sipser, Introduction to the theory of computation. Either 2nd or 3rd edition is fine. (2e: ISBN 978-0-534-95097-2; 3e: ISBN 978-1133-18779-0)

This course meets TR at 9:30am, in Ruffner 352.

Resources

Homework

For 23 Aug, good review: 0.3, 0.11, 1.3, 1.4c, 1.6 a/c/d/e/h and the same ones for 1.18, 1.16, 1.20
For 4 Sep: 1.48 "...of the substrings 01 and 10...", 1.49ab "...1^ky | y in {0,1)*...", 1.53 "...Show that ADD is not regular", 1.54 "Consider the language F...";
For 6 Sep: Revisit 1.54; 2.1 "Recall the CFG G4...", 2.4 bce "Give context-free grammars...",
For 11 Sep: 2.13 "Let G ... be the following grammar....", 2.14 "Convert the following CFG...", 2.21 "...twice as many a's as b's", 2.23 "Show that D is...", 2.27 "... G is ambiguous ...".
For 13 Sep: Carry over 2.23, 2.27 (above); and, 2.9 "... ai bj ck ...", 2.20 "Let A / B = ...".
For 18 Sep: Carry over 2.23 and 2.20 (above); and, 2.10 "... recognizes the language A in Exercise 2.9", and look back at 2.20 and 2.21 (and other problems from Chapter 2) and see if PDAs give us a better angle on solving those problems.
For 20 Sep: Finish the proof of 2.20 and continue thinking about PDAs; and: 2.30ad "Use the pumping lemma... ", 2.31 "Let B be the language of all palindromes...", 2.32 "Let Σ = {1,2,3,4} ...", 2.33 "Show that F={ aibj | ...".
For 25 Sep: Carry over 2.30ad, 2.31, 2.32, 2.33.
For 27 Sep: 3.1acd "...configurations that M2 enters...", 3.2bcde "...configurations that M1 enters...", 3.8b "Give implementation-level...", 3.9a "...Show that 2-PDAs...".
For 2 Oct: 3.12 "... left reset ...", 3.13 "... stay put instead of left ...", and read the lambda calculus handout.
For 9 Oct: Reflect further on the lambda calculus handout, which we'll finish working through. Also still read Section 3.3.
For 23 Oct: 4.3 "Let ALL_DFA = ...", 4.4 "Let Aε_CFG = ...", 4.10 "Let INFINITE_PDA ..." (not DFA, which is 4.9), 4.16 "Prove that EQ_DFA is ..."
For 23 Oct: Carry over 4.10, 4.16.
For 30 Oct: Read rest of Ch 4 and Sec 5.1, prepare to explain "halting problem" proof re A_TM (sec 4.2), also real halting problem proof re HALT_TM. Then, 5.1 "... EQ_CFG ...", 5.9 "Let T = {<M> | M is ..."
For 1 Nov: Finish proofs from Tuesday, read about PCP and sec 7.1, and: 7.6 "... P is closed under ...", 7.7 "... NP is closed under ...", 7.9 "A triangle ..."
For 6 Nov: Look up big-omega etc; carry over problems 7.6, 7.7, 7.9, and: 7.21/22 "Let DOUBLE-SAT = ...", 7.14/15 "... P is closed under the star operation ..." (Also, vote)

Presentations

13 Nov: Simhran and Tyler, probabilistic algorithms
15 Nov: Joe, Radu, and Steven, space complexity
27 Nov: Joe, Radu, and Tyler, parallel algorithms
29 Nov: Simhran and Steven, approximation algorithms

Classroom stuff

21 Aug: board
23 Aug: board,
28 Aug: left, middle, right, side, back-left, back-right
30 Aug: pigeonhole-1, pigeonhole-2, board,
4 Sep: left, middle, right, side,
6 Sep: left, middle, side,
11 Sep: left, middle, right,
13 Sep: left, right, side,
18 Sep: left, right,
20 Sep: back, front, side,
25 Sep: left, middle, right, side, back,
27 Sep: back, left, right,
2 Oct: left, right,
4 Oct: middle, right, far-right, left,
9 Oct: left, middle, right,
23 Oct: left, right, side, back,
25 Oct: front, back,
30 Oct: left, right,
1 Nov: left, middle, right,
6 Nov: left, right, side,
8 Nov: left, right,
13 Nov: left, front, side,
15 Nov: left, front, side, back-left, back-right,