Introduction
Welcome to CS46: Theory of Computation! In this course will will look at various theoretical models of computation and examine the computational power of these models. For each modele we consider problems that can and cannot be solved, and develop a rigorous method of classifying how difficult certain problems are to compute. While the course emphasis is on theory, there are many applications of the topics discussed. Regular expressions, compilers, CPU job scheduling, and many other real-world problems have some underlying computational model rooted in the theory of computation.
Announcements
- Homework 11 is posted. Problem solutions are due Friday 4 May by 5pm.
Class info
Room: Science Center 264Time: TR 9:55am–11:10am
Text: Elements of the Theory of Computation 2nd Ed. by Lewis and Papadimitriou
Professor: Andrew Danner
Office: Science Center 253
Phone: (610) 328-8665
Office hours: MW 9:30-11a, F 1:30-2:30p, or by appointment
Schedule
| WEEK | DAY | ANNOUNCEMENTS | TOPIC & READING | HOMEWORK |
| 1 | Jan 23 | Math preliminaries Languages |
HW #1 | |
| Jan 25 | ||||
| 2 | Jan 30 | Finite automata regular languages |
HW #2 | |
| Feb 01 | Drop/Add ends (Feb 02) | |||
| 3 | Feb 06 | HW #3 | ||
| Feb 08 | ||||
| 4 | Feb 13 | Pushdown automata Context free languages Determistic CFLs |
HW #4 | |
| Feb 15 | ||||
| 5 | Feb 20 | HW #5 | ||
| Feb 22 | ||||
| 6 | Feb 27 | Deterministic CFLs | HW #6 | |
| Mar 01 | Turing Machine Intro | |||
| 7 | Mar 06 | Turing machine computation |
||
| Mar 08 | No Class | |||
Mar 13 |
Spring Vacation |
|||
Mar 15 |
||||
| 8 | Mar 20 | Turing machine extensions | ||
Mar 22 |
Midterm exam |
|||
| 9 | Mar 27 | Turing machine extensions (continued) | HW #7 | |
| Mar 29 | Last day to declare CR/NC or withdraw with a "W" (Mar 30) |
Non-determinism and Turing Machines |
||
| 10 | Apr 03 | Unsolvable problems | HW #8 | |
| Apr 05 | ||||
| 11 | Apr 10 | HW #9 | ||
| Apr 12 | Computational complexity NP-complete problems |
|||
| 12 | Apr 17 | HW #10 | ||
| Apr 19 | ||||
| 13 | Apr 24 | HW #11 | ||
| Apr 26 | Complexity hierarchies Wrapup |
|||
| 14 | May 01 | |||
| May 03 | ||||
May 10 |
Final exam 9am-Noon. Room TBA |
|||
Grading
Grades will be weighted as follows:| 40% | Homework assignments |
| 10% | Class Participation and Discussion |
| 20% | Midterm exam |
| 30% | Final Exam |
Homework policy
Each week, reading and several problems will be assigned. You should work on all of the problems but hand in clearly written solutions to a subset (usually four) of the problems at the beginning of the Thursday session. Sometimes I will specify certain problems that must be part of what you hand in. All students should be prepared to discuss the reading and solutions to any of the problems. Always do all parts of a problem unless I specify otherwise.
It is best if you start the assignments early, and at least read the problems and make sure you understand what the problem is asking soon after the problems are assigned. If you do not understand a problem, ask for clarification. I often find that the solution to problems in this course only come if the problems sit in your brain for several hours, even if you are not constantly thinking about the problem during that time.
Late assignments will not be accepted except in extreme situations and only if you contact me well before the deadline. Even if you do not fully complete an assignment, you may submit what you have done to receive partial credit.
Academic Integrity
Academic honesty is required in all work you submit to be graded. You may not submit work done by someone else. You may not examine or use work done by others to complete your own work. You may discuss assignments with others in the class to be sure you understand the problem. In addition, you are allowed to work with others to help learn the course material. I do not object to you talking about the problems, but the assumption is that you arrive at each solution independently, unless noted otherwise.
"It is the opinion of the faculty that for an intentional first offense, failure in the course is normally appropriate. Suspension for a semester or deprivation of the degree in that year may also be appropriate when warranted by the seriousness of the offense." - Swarthmore College Bulletin (2006-2007), p. 53
Please see me if there are any questions about what is permissible.