
CS1511: Introduction to Theory of Computation
Lectures
Day 
Tuesday & Thursday 
Time 
1:00pm  2:15pm 
Place 
5313 SENSQ 
Textbook
Introduction to the Theory of Computation, Second Edition, Michael Sipser, CENGAGE Learning Course Technology, 2006, [ISBN13 9780534950972]
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 makeup 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) & ContextFree 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

 