Exams

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 PDF JPG
Exam 2 April 7 None PDF JPG
Exam 3 May 8 None PDF  


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:
    1. Countable and Uncountable Sets (18 points, Mike Rosulek)
    2. Operations on Strings and Languages (16 points, Brian Patterson)
    3. Deterministic Finite Automata (26 points, Brian Patterson)
    4. Regular Expressions (16 points, Soma Chaudhuri)
    5. Non-deterministic Finite Automata (24 points, Mike Rosulek)
    6. 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:
    1. True or False Questions (20 points, Soma Chaudhuri)
    2. Constructing NFAs by Modifying Existing NFAs (18 points, Brian Patterson)
    3. Pumping Lemma for Regular Languages (20 points, Mike Rosulek)
    4. Closure Properties for Regular Languages (20 points, Mike Rosulek)
    5. Context-free Grammars and CNF (22 points, Brian Patterson)
    6. 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:
    1. True or False Questions (20 points, Soma Chaudhuri)
    2. Pumping Lemma for Context-Free Languages (16 points, Mike Rosulek)
    3. Pushdown Automata (24 points, Mike Rosulek)
    4. Turing Machines (24 points, Brian Patterson)
    5. Acceptable and Decidable Languages (18 points, Soma Chaudhuri)
    6. 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