CSCI 313: Theory of Computation
General Information
Professor: Simon D. Levy Lecture: MWF 9:45 – 10:45 Reid 211 Office: Parmly 407B Email: simon.d.levy@gmail.com Office Hours: MWF 10:4511:45, MW 3:454:45, and by appointment 
Textbook: Michael Sipser, Introduction to the Theory of Computation, third edition, Thompson Course Technology, 2005
This book is expensive, but far superior to any of the alternatives. You are welcome to use a previous edition, but make sure to check with me to be sure that the exercises match the ones I have assigned.
Brief Overview
This course deals with the mathematical theory of computing. This involves an increasingly powerful series of abstract models of computing “machines”. Working hand in hand with these models is an increasingly powerful series of formal languages. The connection between the models and their corresponding languages is investigated. A widely accepted notion of what it means to say that a problem or function is computable is developed and the limitations of computing are explored. Also, an idea of “practical computability” as opposed to theoretical computability is studied. While the course is theoretical by nature, it is important and profitable to note that many techniques that can be used in everyday computer science are covered along the way. An attempt will be made to emphasize applications to areas ranging from hardware design to compiler construction.
At many schools, the theory course is the one that students hate and have the most difficulty with, because it involves a lot of math. This is extremely unfortunate, because the material is genuinely interesting and connects directly with nearly everything else you have done or will do as a computer scientist. I am far more interested in making sure that you understand the material than I am in putting you through a “boot camp” where you sink or swim based on your mathematical background or ability to solve tricky problems. What this means is that you can do well in this class if you do the reading, attend the lectures, start the assignments early, and participate fully. As a nontheoretician, I sometimes find that students who are doing those things will correct me when I make a mistake in class: in other words, this class works best when we all learn together.
Grading
 Two inclass or exams: total 30%
 Comprehensive final exam: 20%
 Homework assignments: 50%
These percentages are flexible. If you have a really hard time on a homework assignment, I’ll probably just drop that grade. If you do well on everything but one exam, I’ll reduce the impact of that exam on your final grade.
The grading scale will be 93100 A; 9092 A; 8789 B+; 8386 B; 8082 B; 7779 C+; 7376 C; 7072 C; 6769 D+; 6366 D; 6062 D; below 60 F.
Honor System
All exams will be done without books or notes and without assistance from other people. You may NOT work with another person on the homework assignments. Start each assignment well before it is due so that if you have trouble with it, you can get help from me during office hours.
Accommodations
Washington and Lee University makes reasonable academic accommodations for qualified students with disabilities. All undergraduate accommodations must be approved through the Office of the Dean of the College. Students requesting accommodations for this course should present an official accommodation letter within the first two weeks of the (fall or winter) term and schedule a meeting outside of class time to discuss accommodations. It is the student’s responsibility to present this paperwork in a timely fashion and to follow up about accommodation arrangements. Accommodations for testtaking should be arranged with the professor at least a week before the date of the test or exam.
Final Exam
The final exam for this course will be given during the final exam week. You can take this exam during any of the regularly scheduled exam periods that week. You must supply an exam envelope to the instructor or the department administrative assistant no later than noon on the last day of class. You must specify a provisional day and time on the envelope, which you are free to change on the clipboard provided outside the door of Parmly 407 any time that week. Email or phone requests to reschedule will not be accepted.
The exam will be given in Parmly 405, and you should arrive promptly before the appointed time. If you are more than 15 minutes late, you will have to reschedule your exam. If you are more than 15 minutes late to the last exam period on Friday morning, you will receive a grade of 0 on your exam.
Students who have approved academic accommodations must make arrangements to use those accommodations directly with the instructor no later than the last day of class. Students approved for extra time will receive that time at the tail end of the morning exam period or before the beginning of the afternoon exam period (for example, ending at 1:30 PM for a morning exam or beginning at 12:30 PM for an afternoon exam). Students approved for a lowdistraction testing location should reserve that space during the last week of classes, following instructions distributed by Dean Price (sophomores, juniors or seniors) or Director of Disability Resources Lauren Kozak (firstyears).
Homework Assignments
Perhaps the most important aspect of the course is the homework assignments you do. Note that this counts for a substantial part of your course grade. Homeworks will be due in your Sakai dropbox folder as a PDF, on 11:59 PM of the due date. No late work, handwritten work, or Word/PowerPoint documents will be accepted, and you will lose 10% immediately if your name does not appear on the document when it is printed out.Serious problems (health / family / personal emergencies) that interfere with attendance / homework should be handled through the Office of the Dean.
Though you don’t have to use LaTex to create your PDFs, I encourage LaTex as a useful skill. The first assignment has a complete LaTex example, including graphics.
Schedule
Monday 
Wednesday 
Friday 

02 Sep Week 0 
Course Outline  
09 Sep Week 1 
Math review  Chapter 1 Finite Automata 
Finite Automata 
16 Sep Week 2 
Nondeterminism  Regular Expressions
Due: Assignment #1 
Regular Expressions 
23 Sep Week 3 
Regular Expressions  Equivalence of Regular Expressions and DFAs  Equivalence of Regular Expressions and DFAs 
30 Sep Week 4 
Nonregular languages / Pumping LemmaDue: Assignment #2 
Pumping Lemma  Chapter 1 Review 
07 Oct Week 5 
Exam 1  Exam 1 review  Reading day; no class 
14 Oct Week 6 
Chapter 2: Contextfree grammars and languages Ambiguity 
Pushdown Automata

Equivalence of CFG’s and PDA’s 
21 Oct Week 7 
Noncontextfree languages / CFL Pumping Lemma
Due: Assignment #3 
Chapter 2 recap  Exam 2 
28 Oct Week 8 
Chapter 3: The ChurchTuring Thesis A TM that decides 0^{2n} 
A TM that decides connected graphs.  Turing machine variants 
04 Nov Week 9 
Chapter 4: Decidability
Decidability of Regular Due: Assignment #4 
Decidability of Regular and CF Languages 
Undecidability 
11 Nov Week 10 
Halting problem  Halting problem
Due: Assignment #5 
Halting problem 
18 Nov Week 11 
Chapter 7: Time complexity
The class P 
Examples of problems in P 
O (n^{3}) parsing 
02 Dec Week 12 
The class NP  Simpsons: P=NP, ???
Due: Assignment #6 
Review for final exam 