**THEORY OF COMPUTING
Com S 331**

**Exams**

All Com S 331 exams will be closed-book and closed-notes. Scratch papers will be distributed. Calculators are NOT allowed.

Exam |
Date |
Sample Exam | Solution | Grade Histogram |
---|---|---|---|---|

Exam 1 | Feb 24 | Spring 2000: PDF | JPG | |

Exam 2 | April 7 | None | JPG | |

Exam 3 | May 8 | None |

**Exam #1**

- Schedule - As per the usual class period:
**8:00-8:50 am**in Science 102 on Monday February 24. - Topics
**Alphabets, Strings and Languages**(Kozen 2)- Strings and Languages
- Operations on Strings and Languages

**Basic Proof Techniques**(Lewis & Papadimitriou 1.4 - 1.5)- Inductive Definitions and Proofs
- Pigeon-Hole Principle
- Dovetailing
- Diagonalization

**Finite Automata and Regular Languages**(Kozen 3 - 4)- Deterministic Finite Automata
- Regular Languages
- Closure by Union, Intersection, Complement
- Product Construction

**Non-deterministic Finite Automata**(Kozen 5 - 6)- Non-determinism
- Equivalence of NFA's and DFA's
- Subset Construction
- Epsilon Transitions
- Closure by Concatenation, Kleene Star

**Patterns and Regular Expressions**(Kozen 7 - 8)- Pattern Matching
- Regular Expressions
- Construct NFA from Regular Expression

- Each problem will be graded by the same instructor or TA like homeworks.
- Here are the graders:
- Countable and Uncountable Sets (18 points, Mike Rosulek)
- Operations on Strings and Languages (16 points, Brian Patterson)
- Deterministic Finite Automata (26 points, Brian Patterson)
- Regular Expressions (16 points, Soma Chaudhuri)
- Non-deterministic Finite Automata (24 points, Mike Rosulek)
- Closure Properties (EC 20 points, Soma Chaudhuri)

- A total of 100 points were possible (plus 20 extra credit points).
- Grades for the exam are on the grades page. A histogram and solution key can be found above.

**Exam #2**

- Schedule -
**NOT**as per the usual class period:**7:45-8:55 am**in Science 102 on Monday April 7. - Topics (
*The new topics are stated below. Topics from Exam 1 are also relevant since the material is cumulative.*)**Regular Expressions**(Kozen 8 - 9)- Regular Expressions
- Converting NFAs to Regular Expressions
- The Dynamic Programing Algorithm

**Proving Languages Non-Regular**(Kozen 10 - 12)- Closure by Homomorphisms and Inverse Homomorphisms
- Pumping Lemma for Regular Languages
- Using the Pumping Lemma to Prove Non-regularity
- Using Closure Properties to Prove Non-regularity

**Proving Languages Regular**- Using Closure Properties
- Constructing NFAs by Modifying Existing NFAs

**Context-Free Languages and Grammars**(Kozen 19 - 20)- Definitions
- Examples
- Proving Grammas Correct by Induction

**Restricted Context-Free Grammars**(Kozen 21)- Chomsky and Greibach Normal Forms
- Eliminating Epsilon and Unit Productions
- Converting to Chomsky Normal Form
- Derivations and Derivation Trees
- Ambiguous Grammars
- Linear, Left-Linear and Right-Linear Grammars

- Each problem will be graded by the same instructor or TA like homeworks.
- Here are the graders:
- True or False Questions (20 points, Soma Chaudhuri)
- Constructing NFAs by Modifying Existing NFAs (18 points, Brian Patterson)
- Pumping Lemma for Regular Languages (20 points, Mike Rosulek)
- Closure Properties for Regular Languages (20 points, Mike Rosulek)
- Context-free Grammars and CNF (22 points, Brian Patterson)
- Ambigious and Linear Grammars (20 points, Soma Chaudhuri)

- A total of 120 points were possible but the test was only out of 100 (20 points were extra credit).

**Exam #3**

- Schedule - As per our finals assignment:
**7:30-9:30 am**in Science 102 on Thursday May 8. - Topics (
*The new topics are stated below. Topics from Exam 1 and 2 are also relevant since the material is cumulative.*)**Proving Languages Non-Context-Free**(Kozen 22 & 27)- Pumping Lemma for Context-Free Languages
- Using the Pumping Lemma to Prove Non-context-freedom
- Closure Properities of Context-Free Languages

**Pushdown Automata**(Kozen 23)- Definitions
- Examples
- Deterministic Pushdown Automata

**Turing Machines**(Kozen 28 - 29)- Definitions
- Examples
- Level I - Formal Descriptions
- Level II - Implementation-level Descriptions
- Acceptor and Decider Turing Machines
- Acceptable and Decidable Languages
- Proving Languages Acceptable and Decidable

**Undecidability**(Kozen 31 - 32 and Sipser 4)- Level III - High-level TM Descriptions
- Universal Turing Machine
- The Halting Problem
- Proving Undecidability Using Diagonalization
- Proving Undecidability Using Machine Constructions

- Each problem will be graded by the same instructor or TA like homeworks.
- Here are the graders:
- True or False Questions (20 points, Soma Chaudhuri)
- Pumping Lemma for Context-Free Languages (16 points, Mike Rosulek)
- Pushdown Automata (24 points, Mike Rosulek)
- Turing Machines (24 points, Brian Patterson)
- Acceptable and Decidable Languages (18 points, Soma Chaudhuri)
- Undecidability (18 points, Brian Patterson)

- A total of 120 points were possible but the test was only out of 100 (20 points were extra credit).

Iowa State University - Computer Science Department - Top of this page