2012 June 5,

CS 254: Computability and Complexity

Carleton College, Spring 2012

Prof. Joshua R. Davis, , Goodsell 106B, 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 210 during period 1A (MW 8:30-9:40, F 8:30-9:30). The course materials are

My office hours are 4A (Mon, Wed, and Fri) and Thu 1:00-2:00. I am often in my office during 2A as well. You can also schedule an appointment with me.


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.

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.

Standards for Work

You are encouraged to work with others on all assignments. 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 multiple pages of paper, staple them into a single packet, in the correct order. Packets that are not stapled are unacceptable. I will not accept packets that are not stapled. Staple your packet. Your packet? Staple it. 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.

Special Accommodations

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 and proposing a new due date. If the due date is extended by only one class meeting, then no explanation is necessary; if you need longer, then convince me. 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.


This schedule is incomplete and tentative; we will fill it in as we go along. (One reason is that the complexity theory material is new to our course this year. Another reason is that our textbook is new this year.)

M 3/2601introductionAssignment A0.1-0.4sosupersum.py
W 3/2802deterministic finite automataAssignment B1.1
F 3/3003nondeterministic finite automataAssignment C1.2
M 4/0204regular expressionsAssignment D1.3Python REs
W 4/0405catching up
F 4/0606pumping lemma1.29b, 1.35, 1.53, 1.54, 1.55c (due Fri)1.4
M 4/0907context-free grammars2.2, 2.4c, 2.6b, 2.17, 2.20 (due Fri)2.1
W 4/1108pushdown automata2.2
F 4/1309catching upAssignment G
M 4/1610exam
W 4/1811pumping lemma2.31, 2.34, 2.36 (due Fri)2.3
F 4/2012Turing machines3.1
M 4/2313catching up
W 4/2514variants of Turing machines3.9b, 3.13 (due Fri)3.2
F 4/2715decidable problems4.12, 4.16, 4.18 (due Fri)4.1
M 4/30midterm break
W 5/0216undecidable problems4.2
F 5/0417mapping reducibilityAssignment K5.1
M 5/0718Rice's theorem5.3
W 5/0919time complexity7.1
F 5/1120polynomial timeexam7.2
M 5/1421nondeterministic polynomial time7.4, 7.6, 7.7, 7.11 (due Fri)7.3
W 5/1622NP-completeness7.4
F 5/1823Cook-Levin theorem7.4
M 5/2124space complexity7.24, 7.25 (due Fri)8.0-8.1
W 5/2325PSPACE-completeness8.2-8.3
F 5/2526Kolmogorov complexityAssignment N6.4
M 5/2827Kolmogorov complexity6.4Kolmogorov Notes
W 5/3028PSPACE-completenessTQBF
M 6/04final exam 12:00PM-2:30PM

Topics removed from my earlier version of the course: minimizing DFAs, Myhill-Nerode, unrestricted grammars, combinatorial logic, Kolmogorov complexity.