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|
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 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.
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 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)
|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)
|4||Feb 07||Regular and non-regular languages, finite automata, Context-free grammars||Read Sipser 2.1.
Homework 4 (pdf | tex)
|5||Feb 14||Context-free grammars, context-free languages, and pushdown automata||Read Sipser 2.2-2.3.
Homework 5 (pdf | tex)
|6||Feb 21||Midterm 1||Homework 6 (pdf | tex)|
|7||Feb 28||Parsing and non-context-free languages||Homework 7 (pdf | tex)|
|8||Mar 13||Turing machines||Read Sisper 3.1-3.2.
Homework 8 (pdf | tex)
|9||Mar 20||Read Sisper Chapter 3.
Homework 9 (pdf | tex)
|Mar 22||Last day to declare CR/NC or withdraw with a "W"
|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)
|12||Apr 10||Complexity theory||Read Sisper Sections 7.1, 7.2 and 7.3.
Homework 11 (pdf | tex)
|13||Apr 17||Read Sisper Chapter 7.
Homework 12 (pdf | tex)
Final 9am–noon Sci 181