CS1511: Introduction to Theory of Computation
Lectures
| Day |
Tuesday & Thursday |
| Time |
4:00pm - 5:15pm |
| Place |
5129 SENSQ |
Textbook
Introduction to the Theory of Computation, Second Edition,
Michael Sipser,
Thompson Course Technology, 2006,
[ISBN 0-534-95097-3]
Instructors
| Instructor |
Professor Bob Daley |
| Office Hours |
Tuesday & Thursday: 2:30pm - 3:30pm & 5:30pm - 6:30pm |
| Office |
5401 Sennott Square |
| Phone |
412.624.8415 |
| Email |
daley@cs.pitt.edu |
| Grader |
Kelli Ireland |
| Office Hours |
Monday & Wednesday: 9:00am - 12:00pm |
| Office |
5426 Sennott Square |
| Phone |
412.624.8840 |
| Email |
kireland@cs.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 each class. 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.
-
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 5 |
Regular Languages (Review) & Context-Free Languages & Turing Machines |
1.1 - 1.4; 2.1 - 2.3; 3.1 - 3.3 |
| Feb 12 |
Exam I |
Chapters 1, 2 & 3 |
| Feb 10 - Mar 19 |
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 24 - Apr 16 |
Computational Complexity |
7.3 - 7.5; 8.1 - 8.3 |
| Apr 23, 10:00am - 11:50am |
Exam III |
Chapters 7 & 8 |
Example Tests
|
