2013 December 2,

CS 254: Computability and Complexity

Carleton College, Fall 2013, Prof. Joshua R. Davis, , Laird 205A, 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 111 (Intro) 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 210 during period 2A (MonWed 9:50-11:00, Fri 9:40-10:40). My office hours are

If you can't make office hours, then schedule an appointment with me. The course materials are


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 advantage of this system is that student grades don't suffer when I write a difficult exam. The disadvantage is that you cannot compute your own grade. If you visit me in my office, then I am happy to estimate your current grade for you. The following elements contribute to your final grade.

You are expected to spend about 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 15 hours, then talk to me.

Standards for Work

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? 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 this course, the required level of rigor in proofs is sometimes unclear. Mimic the book's level of rigor, preferably with explanation and motivation, and with note of any pitfalls in the logic. If a fellow student were to read your solution, she should be convinced that you understand the problem.

Although homework is assigned every day, it is collected only once a week (usually Mondays). 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 will be graded. In order to ensure full credit, do all of the assigned problems.

Special Accommodations

During the term, you have one free pass to hand in a week's homework packet late. Instead of handing in the packet, send me e-mail, by the due date, declaring that you are using your late pass. No explanation is necessary. Your packet is now due when the next packet is due. When you submit your late packet, write "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:


This schedule is tentative. It will be adjusted as we go along. To help you decode the schedule, here is an example. On Day 02 we discuss deterministic finite automata, which are covered in Section 1.1 of our textbook. You have homework called "Day 02", which you hand in on Day 04.

M 09/1601introductionDay 01010.1-0.4sosupersum.py
W 09/1802deterministic finite automataDay 02041.1
F 09/2003nondeterministic finite automataDay 03071.2
M 09/2304regular expressionsDay 04071.3Python REs
W 09/2505pumping lemmaDay 05071.4Radiolab: Loops
F 09/2706catching upDay 0610Stack Exchange: Recursion or Loops?
M 09/3007context-free grammarsDay 07102.1
W 10/0208pushdown automataDay 08102.2
F 10/0409pumping lemma2.30d, 2.31, 2.36132.3
M 10/0710catching up
W 10/0911Turing machinesEXAM A123.1Wikipedia: Alan Turing
F 10/1112Turing machinesDay 12163.2
M 10/1413Turing machines3.15bcde, 3.16bcd163.3
W 10/1614Turing machinesDay 14164.1
F 10/1815HALT is undecidableDay 15184.2
W 10/2316Rice's theoremDay 16185.1
F 10/2517time complexityDay 17217.1
W 10/3019EXAM B
F 11/0120time complexity7.6, 7.7247.1
M 11/0421time complexity7.4, 7.14247.2
W 11/0622time complexityDay 22247.3
F 11/0823SAT is NP-complete7.4
M 11/1124space complexity7.24, 7.25278.0-8.1
W 11/1325NPSPACE = PSPACEDay 25278.2
F 11/1526TQBF is PSPACE-complete8.3TQBF
M 11/1827Kolmogorov complexityEXAM C286.4
W 11/2028Kolmogorov complexityDay 286.4Kolmogorov
S 11/23FINAL EXAM 8:30AM-11:00AM