COMP272: Theory of Computation: Spring 1997

  • Syllabus
    FINAL EXAM GRADES -- Posted May 23, 1997

  • NEW Grades so far (Quiz1 + Exam1 + Quiz2 + Exam2)
  • Answers for Quiz2
  • Announcement: The review session will take place on Saturday, 17 May, from 3-4 PM in Room 2406.

    Lecture Notes

  • Introduction and overview
  • Set, relations, and functions (a review)
  • Languages and regular expressions
  • Empty Sets vs. Empty Strings (extra handout)
  • A First Example of A DFA
  • Finite Automata
  • The Fundamental Theorem
  • Properties of Regular Languages
  • The Pumping Theorem For Regular Languages
  • A Second Pumping Theorem For Regular Languages
  • Context-Free Languages: An Introduction
  • Pushdown Automata
  • More on Context-Free Languages
  • Introduction to Turing Machines
  • Combinations of Turing Machines
  • Extensions of Turing Machines
  • Universal Turing Machines
  • Uncomputability
  • Some Unsolvable Problems

    HomeWork Assignments

  • HomeWork 1: Due February 20, 1997 and Solutions
  • HomeWork 2: Due February 27, 1997 and Solutions
  • Homework 3: Due March 6, 1997. Problems 2.1.3 (a), (c), 2.2.2 (b) and 2.45 (a), (b), (d) from textbook. Solutions
  • HomeWork 4: Due March 20, 1997 Solution: Part 1 and Part 2
  • Homework 5: Due April 10, 1997. Problems 3.1.8 (a), (b), (c), (f), 3.2.1 and 3.2.2 from textbook. Solutions (corrected version)
  • Homework 6: Due April 17, 1997. Problems 3.3.2 (a), (b), 3.5.1 (a), (b) and 3,5.2 (a), (b), (c) from textbook. Solutions
  • Homework 7: Due May 8, 1997. Problems 4.1.3, 4.1.5, 4.2.3, 4.3.2, and 4.4.7(a) from textbook. Solutions

    Old Exams from Fall 1996

  • Quiz1
  • Midterm
  • Quiz2
  • Exam2