CS273: Intro to Theory of Computation
Fall 2006 Prof. Fleck and Parthasarathy
There will be two midterms and a final exam, at the following times/places:
The skills list describes the topics to be covered. There is also a practice final based on the final from last term.
Clarification to specs: LBA's may be on the exam as an example of a Turing machine variant. We will not ask you to produce the definition of an LBA. But we might remind you of the definition and ask you to produce reasoning like that in Lemma 5.8 or Theorem 5.9. Reductions by computation histories will not be on the final.
Here is the model solution for the second midterm, except for a couple hand-drawn parts. Here are notes on the differences from the main exam, for those of you who took the conflict/make-up version.
The maximum possible score was 60. Actual scores ranged from 20 to 58. Approximate letter grade cutoffs:
Histogram of scores
The skills list describes the topics to be covered.
Second midterm from last spring with solutions. Our midterm will be similar except that some of the short answer questions aren't appropriate (due to differences in topic coverage) and we will also be covering the pumping lemma for regular languages and very easy facts about Turing machines.
The models solutions come in two files: most of the problems and two sub-problems
First midterm from last spring with solutions. Our midterm will be about the same level of difficulty. But we have a slightly different topic order and a slightly earlier first midterm, so DFA minimization and pumping lemma proofs won't be on our exam.