2013 June 12,

Carleton College, Spring 2013

Prof. Joshua R. Davis, , CMC 325, x4473

This course addresses two fundamental questions in computer science: What can computers do? And how much time and space do they require, to do it? While answering these questions, if only partially, we will touch on various fascinating topics in philosophy, linguistics, programming languages, etc. Your work will be a mixture of proofs and programs. For example, you will learn how to determine whether a programming problem is solvable by regular expressions, and solve it with them if it is.

The official prerequisites for this course are CS 201 (Data Structures) and CS 202 (Mathematics of Computer Science). Math 236 may be substituted for CS 202. Talk to me, if you are concerned about your background. Our class meets in CMC 206 during period 1A (MW 8:30-9:40, F 8:30-9:30). My office hours are Monday 9:50-11:00, Wednesday 9:50-11:30, and Thursday 6:00-6:50. If you can't make an office hour, then schedule an appointment with me. The course materials are

*Introduction to the Theory of Computation*, 2nd Ed, by Michael Sipser. The third edition is probably fine, except that you will have to reconcile the section and problem numbers yourself.- Exams from my Spring 2012 version of the course:
- Exams from this term:

Final grades (A, B, C, etc.) are assigned according to an approximate curving process. By this I mean that there are no predetermined percentages (90%, 80%, 70%, etc.) required for specific grades. The following elements contribute to the final grade.

- Participation: You are expected to attend every class meeting promptly, and to participate in the discussion and group work. You are also required to visit me in my office at least once during the first two weeks. You can make up for a deficiency in class participation by talking with me frequently in office hours or generally demonstrating exceptional effort and interest. Participation is used to make small adjustments to the class grades.
- Assignments: Assignments are where you learn the material. They are a mixture of proving and programming. They count for 25% of your grade.
- Exam A: The first midterm exam is given in class about 1/3 of the way through the term. It counts for 25% of your grade.
- Exam B: The second midterm exam is cumulative and given as a take-home exam about 2/3 of the way through the term. It counts for 25% of your grade.
- Final Exam: The final exam is cumulative. It is scheduled for Monday 2012 June 10, 7:00PM-9:30PM. It counts for 25% of your grade. Self-scheduled final exams are not allowed.

You are expected to spend at least 10 hours per week on this course outside class. Some students need to spend more than 10 hours. If you find yourself spending more than, say, 15 hours, then talk to me.

You are encouraged to work with others on all assignments (but not exams). Work together to figure out the problems/programs, but write/type them up separately, in your own words. You may not copy someone else's work or allow them to copy yours. Presenting someone else's work as your own is an act of Academic Dishonesty. If Carleton College finds you to not to have upheld its Academic Honesty standards in this course, then you will receive an F for this course.

Writing is not just for English and history majors. Written and oral communication skills are essential to *every* academic discipline, and are highly prized by employers. In this course, your written work is evaluated both for correctness and for presentation. You may find it easier to type your solutions in LaTeX than to edit them by hand.

How much work should you show? The answer is simple: Compose your solutions as if the intended audience is your fellow students. By doing so, you show enough detail that your grader can ascertain whether you yourself understand the material. Your solutions should also be self-explanatory. In short, if a classmate were to read one of your solutions, then she or he should be able to understand what the problem was and how you solved it.

When handing in a week's homework, *staple* your pages into a single packet, in the correct order. Packets that are not stapled are unacceptable. I will not accept packets that are not stapled. Is there a stapler in the classroom? Often not, so staple ahead of time. Is a paper clip okay? No.

Computer files should be submitted in plain text (.txt), PDF (.pdf), or Python (.py) formats only, unless otherwise specified. In particular, Microsoft Word documents are unacceptable. Fortunately, you can "print" any document to PDF easily.

Depending on time constraints in any given week, perhaps not all of your homework is graded. In order to ensure full credit, do all of the assigned problems.

During the term, you have one free pass to hand in an assignment late. Instead of handing in the assignment, send me e-mail, by the due date, declaring that you are using your late pass. No explanation is necessary. Your work is now due when the *next* assignment is due. When you submit your late work, mark it "Late Pass Used" prominently at the top. Once you have used your late pass, no late assignments are accepted, except in extreme circumstances that are truly beyond your control.

If some medical condition affects your participation in class or your taking of exams, let me know in the first week of class. You may need to make official arrangements with the Office of Disability Services.

Here is some advice from actual students who have taken this course in the past:

- Get started on homework assignments well before they are due.
- Work with others on the assignments.
- Use office hours. The work is hard, but the professor is happy to help.
- Be honest with yourself about whether you truly understand the material. You will be tested.
- Reading the book can actually be helpful.
- Figure out which problem-solving skills you need ASAP. If you don't have them, then ask for help early.

Date | Day | Topic | Assignment | Due | Reading | Notes |
---|---|---|---|---|---|---|

M 4/01 | 01 | introduction | Day 01 | 01 | 0.1-0.4 | sosupersum.py |

W 4/03 | 02 | deterministic finite automata | Day 02 | 03 | 1.1 | |

F 4/05 | 03 | nondeterministic finite automata | Day 03 | 06 | 1.2 | |

M 4/08 | 04 | regular expressions | Day 04 | 06 | 1.3 | Python REs |

W 4/10 | 05 | pumping lemma | 1.29b, 1.35, 1.53, 1.54, 1.55c | 09 | 1.4 | Radiolab: Loops |

F 4/12 | 06 | catching up | Day 06 | 09 | Stack Exchange: Recursion or Loops? | |

M 4/15 | 07 | context-free grammars | 2.2, 2.4c, 2.6b, 2.17, 2.20 | 09 | 2.1 | |

W 4/17 | 08 | pushdown automata | Day 08 | 12 | 2.2 | |

F 4/19 | 09 | pumping lemma | 2.31, 2.34, 2.36 | 12 | 2.3 | |

M 4/22 | 10 | catching up | ||||

W 4/24 | 11 | EXAM A | ||||

F 4/26 | 12 | Turing machines | Day 12 | 15 | 3.1 | Wikipedia: Alan Turing |

M 4/29 | 13 | Turing machines | 2.26, 3.9, 3.16 | 15 | 3.2 | |

W 5/01 | 14 | Turing machines | Day 14 | 17 | 3.3 | |

F 5/03 | 15 | decidability | 4.12, 4.16 | 17 | 4.1 | |

M 5/06 | midterm break | |||||

W 5/08 | 16 | decidability | Day 16 | 20 | 4.2 | |

F 5/10 | 17 | HALT is undecidable | Day 17 | 20 | 5.1 | |

M 5/13 | 18 | Rice's theorem | 5.1 | |||

W 5/15 | 19 | time complexity | Day 19 | 23 | 7.1 | |

F 5/17 | 20 | time complexity | EXAM B | 21 | 7.2 | |

M 5/20 | 21 | time complexity | 7.4, 7.6, 7.7 | 23 | 7.3 | |

W 5/22 | 22 | time complexity | 7.4 | |||

F 5/24 | 23 | SAT is NP-complete | Day 23 | 26 | 7.4 | |

M 5/27 | 24 | space complexity | 7.24, 7.25 | 26 | 8.0-8.1 | |

W 5/29 | 25 | space complexity | 8.2-8.3 | |||

F 5/31 | 26 | TQBF is PSPACE-complete | Day 26 | 28 | TQBF | |

M 6/03 | 27 | catching up | ||||

W 6/05 | 28 | what haven't we learned? | ||||

M 6/10 | FINAL EXAM 7:00PM-9:30PM |