CS1511: Introduction to Theory of Computation


Sunny Winterscape

Lectures


Day Tuesday & Thursday
Time 1:00pm - 2:15pm
Place 5313 SENSQ

Homework Assignments


Lecture Notes


Textbook

  • Introduction to the Theory of Computation, Second Edition,
    Michael Sipser,
    CENGAGE Learning Course Technology, 2006,
    [ISBN-13 978-0-534-95097-2]

  • Instructors

    Instructor Professor Bob Daley
    Office Hours Tuesday & Thursday: 2:30pm - 3:30pm & 5:15pm - 6:15pm
    Office 5401 Sennott Square
    Phone 412.624.8415
    Email daley@cs.pitt.edu

    Grader Nathan Ong
    Office Hours Monday, Wednesday & Friday: 5:00pm - 6:00pm
    Office TBD
    Phone TBD
    Email nro5@pitt.edu

    Course Prerequisite

  • CS 1502: Formal Methods in Computer Science

  • Requirements

    Homework & Class Participation 10%
    Exams (3) 30% each

    Regulations

    • Class attendance is required and will be recorded
    • Homework assignments will be given out each Thursday. They are due at the beginning of the Thursday class of the following week. No late homework will be accepted.
    • Collaboration is NOT allowed. Any form of cheating, copying, or collaboration on homework or exams will result in a failing grade for the course. This includes submitting homework that is based on solutions found on the web or other places.
    • No make-up exams will be offered. In cases where a bona fide medical excuse exists (with a signed doctor's note), the remaining two exams will be averaged to determine the exam grade. Prior notification must be given and the doctor's note must be presented at the next class.

    Schedule

    Dates Topics Readings
    Jan 6 - Feb 10 Regular Languages (Review) & Context-Free Languages & Turing Machines 1.1 - 1.4; 2.1 - 2.3; 3.1 - 3.3
    Feb 19 Exam I Chapters 1, 2 & 3
    Feb 12 - Mar 17 Decidability & Reducibility & Recursion Theorem 4.1 - 4.2; 5.1 - 5.3; 6.1; 7.1 - 7.2
    Mar 26 Exam II Chapters 4, 5 & 6
    Mar 19 - Apr 16 Computational Complexity 7.3 - 7.5; 8.1 - 8.3
    Saturday, April 25, 12:00pm - 1:50pm Exam III Chapters 7 & 8

    Example Tests

    Fall Term 2002 Exam I Exam II Exam III
    Spring Term 2003 Exam I Exam II Exam III
    Spring Term 2004 Exam I Exam II Exam III