CS46 -- Theory of Computation
Spring 2012

Schedule | Grading | Exam policy | Lab policy | Homework policy


Welcome to CS46. Computer technology changes rapidly, but the underlying model of computation predates modern computers and has changed little in the past 50 years. In this course we will explore theoretical models of computation, including:

This course is intended as a broad introduction to the theory of computing, providing a glimpse into the mathematical beauty of computation and a foundation for further study in theoretical computer science.

To enroll in this course you must have completed CS35. Discrete Mathematics (MATH 29) is strongly recommended.

Class information

       Room: Science Center 181
       Class: T/Th 9:55-11:10am
       Lab: M 1:00-2:30, Science Center 256
       Make-up lab: M 6:30-8:00, Science Center 256
       Professor: Charlie Garrod
       Office: Science Center 255
       Phone: 6071
       Office hours: Tuesdays 1:30 - 4 or by appointment, or you can stop by whenever my door is open.
       Required textbook: Introduction to the Theory of Computation, 2nd edition, by Michael Sisper.


Grades will be weighted as follows:

40%Homework and lab assignments
10%Class and lab participation
25%Two midterms
25%Final exam

Exam policy

Exams will be given at the beginning of class or lab on the days posted in the Announcements section of the Schedule, or will be handed out that day as a take-home exam. Please look over these dates carefully and contact the professor in advance if you cannot be in class for an exam.

If you are not present at the start of class on the day of an exam, but make it to class before the end, then you may take the exam. Otherwise you will receive a zero for that exam.

Lab policy

Lab attendance in CS46 is required. Lab sessions will sometimes contain new course material, required practice exercises, and written quiz-like exercises. Our goal in lab is to more-deeply explore course content, including applications of the course content to real problems. In some of the labs you will work in small groups on theoretical homework-like exercises; in other labs you will work alone or in small groups to write programs related to the course content.

In addition to the regularly-scheduled lab time, we've scheduled an overflow / alternative / make-up lab time that you can attend instead of the regularly-scheduled lab. The make-up lab time is Monday from 6:30 - 8 p.m. each week. In any week you may attend either the regular or the make-up lab session without obtaining permission from the instructor.

Homework policy

Homeworks are regularly due each Thursday at the beginning of class, except you may turn in up to two assignments late by Friday at 5 p.m. without penalty without requesting special permission. If you use this option, please turn in your homework directly to the box outside Charlie's office. Otherwise no late work will be accepted unless you obtain prior permission from Charlie for extreme circumstances. Even if you do not complete an assignment, please turn in your work for partial credit. Your lowest non-zero homework score will be dropped when calculating your grade at the end of the semester.

Homeworks must be typeset, not handwritten, although you may hand-draw figures and diagrams if you wish. I recommend Latex as a typesetting tool, but you may use any typesetting tool. I also recommend Tia's resources for help creating documents, graphs, and figures.

We strongly encourage you to talk about the course material with each other, the instructor, and other students. This includes discussions of the homework problems. The work you submit, however, must be written entirely by yourself. To avoid problems with the originality of your work, do not take notes when discussing homework problems and please list all of your collabators and consultants on the first page of your homework.

The homework assignments will vary in difficulty, and I recommend that you read and start thinking about the assignments early; make sure you understand at least what each problem is asking on the day the problems are assigned. Many solutions will require long-term, creative thinking; you will be more successful if you ponder aspects of the problems for several hours, even if you are not constantly thinking about the problems during that time.

Academic accommodations

If you believe that you need accommodations for a disability, please contact Leslie Hempling in the Office of Student Disability Services, located in Parrish 130, or e-mail lhempli1 to set up an appointment to discuss your needs and the process for requesting accommodations. Leslie Hempling is responsible for reviewing and approving disability-related accommodation requests and, as appropriate, she will issue students with documented disabilities an Accommodation Authorization Letter. Since accommodations may require early planning and are not retroactive, please contact her as soon as possible. For details about the Student Disabilities Service and the accomodations process, visit http://www.swarthmore.edu/x7687.xml. You are also welcome to contact me privately to discuss your academic needs. However, all disability-related accommodations must be arranged through Leslie Hempling in the Office Of Student Disability Services.

Academic integrity

Academic honesty is required in all work you submit to be graded. With the exception of your lab partner(s) on lab assignments, you may not submit work done by someone else, or directly examine or use work done by others to complete your own work. Your work should never be shared with anyone; you may not examine or use work belonging to someone else, nor may you let anyone else look at or make a copy of your work. This includes sharing solutions after the due date of the assignment.

Discussing ideas and approaches to problems with others on a general level is fine (in fact, we encourage you to discuss general strategies with each other), but you should never read anyone else's solutions or let anyone else read your solution.

``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 (2008-2009, Section 7.1.2)

Please see me if there are any questions about what is permissible.


For the reading assignments the section numbers are inclusive, so "1.1-1.1.2" means you should read all the sections from 1.1 up to and including section 1.1.2. This schedule is subject to change as the semester progresses.

1 Jan 17   Mathematical preliminaries, languages
Read Sipser Chapter 0.
Homework 1 (pdf | tex)
Jan 19  
2 Jan 24   Regular and non-regular languages, finite automata Read Sipser 1.1 - 1.2.
Homework 2 (pdf | tex)
Jan 26 Drop/Add ends (Jan 27)
3 Jan 31   Read Sipser 1.3 - 1.4.
Homework 3 (pdf | tex)
Feb 02  
4 Feb 07   Regular and non-regular languages, finite automata, Context-free grammars Read Sipser 2.1.
Homework 4 (pdf | tex)
Feb 09  
5 Feb 14   Context-free grammars, context-free languages, and pushdown automata Read Sipser 2.2-2.3.
Homework 5 (pdf | tex)
Feb 16  
6 Feb 21 Midterm 1 Homework 6 (pdf | tex)
Feb 23  
7 Feb 28   Parsing and non-context-free languages Homework 7 (pdf | tex)
Mar 01  

Mar 06

Spring break

Mar 08

8 Mar 13   Turing machines Read Sisper 3.1-3.2.
Homework 8 (pdf | tex)
Mar 15  
9 Mar 20   Read Sisper Chapter 3.
Homework 9 (pdf | tex)
Mar 22 Last day to declare CR/NC or withdraw with a "W"
(Mar 23)
10 Mar 27   Computability theory Read Sisper Chapter 4.
Mar 29 Midterm 2
11 Apr 03   Read Sisper Sections 5.1 and 5.3.
Homework 10 (pdf | tex)
Apr 05  
12 Apr 10   Complexity theory Read Sisper Sections 7.1, 7.2 and 7.3.
Homework 11 (pdf | tex)
Apr 12  
13 Apr 17   Read Sisper Chapter 7.
Homework 12 (pdf | tex)
Apr 19  
14 Apr 24    
Apr 26    

May 10

Final 9am–noon Sci 181