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:
To enroll in this course you must have completed CS35. Discrete Mathematics (MATH 29) is strongly recommended.
Grades will be weighted as follows:
40%  Homework and lab assignments 
10%  Class and lab participation 
25%  Two midterms 
25%  Final exam 
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 takehome 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 attendance in CS46 is required. Lab sessions will sometimes contain new course material, required practice exercises, and written quizlike exercises. Our goal in lab is to moredeeply 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 homeworklike exercises; in other labs you will work alone or in small groups to write programs related to the course content.
In addition to the regularlyscheduled lab time, we've scheduled an overflow / alternative / makeup lab time that you can attend instead of the regularlyscheduled lab. The makeup lab time is Monday from 6:30  8 p.m. each week. In any week you may attend either the regular or the makeup lab session without obtaining permission from the instructor.
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 nonzero homework score will be dropped when calculating your grade at the end of the semester.
Homeworks must be typeset, not handwritten, although you may handdraw 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 longterm, 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 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 (20082009, 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.11.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.
WEEK  DAY  ANNOUNCEMENTS  TOPIC  HOMEWORK 
1  Jan 17  Mathematical preliminaries, languages 
Read Sipser Chapter 0. Homework 1 (pdf  tex) 

Jan 19  
2  Jan 24  Regular and nonregular 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 nonregular languages, finite automata, Contextfree grammars  Read Sipser 2.1. Homework 4 (pdf  tex) 

Feb 09  
5  Feb 14  Contextfree grammars, contextfree languages, and pushdown automata  Read Sipser 2.22.3. Homework 5 (pdf  tex) 

Feb 16  
6  Feb 21  Midterm 1  Homework 6 (pdf  tex)  
Feb 23  
7  Feb 28  Parsing and noncontextfree languages  Homework 7 (pdf  tex)  
Mar 01  
Mar 06 
Spring break 

Mar 08 

8  Mar 13  Turing machines  Read Sisper 3.13.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 