CSCI 313: Theory of Computation (Fall 2020)

CSCI 313: Theory of Computation

General Information

Professor: Simon D. Levy
Lecture: MWF 5:30-6:30 pm Parmly 405
Office: Parmly 407B
Office Hours: MWF 2:00-5:30, and by appointment

Textbook: Michael Sipser, Introduction to the Theory of Computation, third edition, Thompson Course Technology, 2005

This book is expensive, but there is a free version for students available online. Make sure to get the third edition!

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 non-theoretician, 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.


    • Two in-class 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 93-100 A; 90-92 A-; 87-89 B+; 83-86 B; 80-82 B-; 77-79 C+; 73-76 C; 70-72 C-; 67-69 D+; 63-66 D; 60-62 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.


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 test-taking 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 period.  Because of the COVID-19 situation, we will skip the usual classroom-based exams.   Instead, you will receive a PDF copy of the exam by email at the start of the exam period, 2:00pm Saturday 14 November.  You will have until the end of the exam period, 12:00 noon Friday 20 November, to complete the exam.  You can print out the PDF, write your answers on it, and email me a scan or photograph of the complete exam;  or you can email me a text document with your answers — whichever your prefer. 

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 private github repository as a PDF, on 11:59 PM of the due date. No late work, hand-written 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.





24 Aug
Week 1
Course Outline Math review Chapter 1: Finite Automata
31 Aug
Week 2
Nondeterminism Regular Expressions

DueAssignment #1

Regular Expressions
07 Sep
Week 3
Regular Expressions Equivalence of Regular Expressions and DFAs Equivalence of Regular Expressions and DFAs
14 Sep
Week 4
Nonregular languages /
Pumping LemmaDueAssignment #2
Pumping Lemma Chapter 1 Review
21 Sep
Week 5
Exam 1 Exam 1 review Chapter 2:
Context-free grammars and languages
28 Sep
Week 6

Chomsky Normal Form

Pushdown Automata


Equivalence of CFG’s and PDA’s



05 Oct
Week 7
Non-context-free languages / CFL Pumping Lemma

DueAssignment #3

Chapter 3: The Church-Turing Thesis
TM that decides 02n
Chapter 2 recap
12 Oct
Week 8
Exam 2  

TM that decides connected graphs.

Turing machine variants
19 Oct
Week 9
Chapter 4: Decidability

Decidability of Regular
and CF Languages

DueAssignment #4

Decidability of Regular
and CF Languages
26 Oct
Week 10

Halting problem

Halting problem

DueAssignment #5

Halting problem
02 Nov
Week 11
Chapter 7: Time complexity

The class P

Examples of
problems in P
O (n3) parsing
09 Nov
Week 12
The class NP

The Limits of Quantum Computing

Simpsons: P=NP,   ???

DueAssignment #6

Review for final exam