cs254-00-w15: Computability and Complexity
Winter 2015, Carleton College

Basic Information

• Instructor: David Liben-Nowell
• Office Hours: see my homepage. Always feel free to email for an appointment if the scheduled times aren't good for you.

• This webpage was originally stored in Moodle, which does not have an easy capacity to publish a version of an old webpage for a course. Major thanks to Dave Musicant, whose Moodle-scraping tool I used to generated this page, which is an approximation of the original.

Course Materials:

Anonymous feedback form

Some useful LaTeX resources

Piazza

Week 1:

Monday:  course overview; history of computing; strings and languages.

1. Reading:  Sipser §0.1–0.4.
2. Complete ps01 for Wednesday.

Wednesday:  strings; intro to DFAs.

1. Reading:  Sipser §1.1.
2. Complete ps02 for Monday/Wednesday (extension from Friday/Monday -- we're behind [yes, already]).

Friday:  DFAs and regular languages.

1. Reading:  review Sipser §1.1; start §1.2.

Week 2:

Monday:  product construction wrapup; nondeterminism and NFAs; the subset construction.

1. Reading:  Sipser §1.2.
2. Complete ps03 for Friday/Monday.

Wednesday:  NFA wrapup; regular expressions.

1. Reading:  Sipser §1.3.
2. Optional reading:  http://yro.slashdot.org/story/09/05/26/159249/ibm-wants-patent-for-regex-ssn-validation.

Friday:  regular expressions.

1. Reading:  Sipser §1.4 and the dfas-and-regexps handout.
2. Complete ps04 for Wednesday/Friday.

Week 3:

Monday:  more on DFA <-> regexps; nonregular languages.

1. Reading: nothing new (we didn't get as far as I'd anticipated).  Feel free to review Chapter 1 and/or start Chapter 2 if you please.

Wednesday:  the pumping lemma and nonregular languages.

1. Reading:  Sipser §2.1.
2. Complete ps05 for Monday.

Friday:  context-free languages.

1. Reading:  Sipser §2.2.
2. Reminder:  the first preliminary exam of the course will be held in class on Wednesday of next week.  We agreed in class that you may use an 8.5"-by-11" crib sheet (two sides, hand-written or typed by you).
   

Week 4:

Monday:  context-free grammar miscellanea:  balanced parentheses, closure properties, normal forms.

1. Reading (for Friday):  review Sipser §2.1 and §2.2, and the cky-algorithm handout.
2. Optional reading:  Gentner, Fenn, Margoliash, Nusbaum, "Recursive syntactic pattern learning by songbirds", Nature 2006.
3. Complete ps06 for Friday and Monday.
4. Reminder:  prelim #1 is on Wednesday.  You may bring a one-page crib sheet.

Wednesday:  Prelim #1!

Friday:  context-free grammars and NPDAs.

1. Reading:  Sipser §2.3.
2. Complete ps07 for Wednesday and Friday.

Week 5:

Monday:  connecting NPDAs and CFGs.

1. Reading:  review Sipser §2.3.

Wednesday:  pumping lemma for CFLs; closure properties for CFLs (and other CFL wrapup).

1. Reading:  Start Sipser §3.1
2. Complete ps08 for Wednesday/Friday.

Friday:  intro to Turing machines.

1. Reading:  Sipser §3.1; start Sipser §3.2.
   
2. Have a great break!

Week 6:

Monday:  midterm break!

Wednesday: midterm evals, Turing machines.

1. Reading:  Sipser §3.2–3.3.
2. Complete ps09 for Monday and Wednesday.

Friday:  Turing machines and variants; midterm eval debrief.

1. Reading:  Sipser §4.1.

Week 7:

Monday:  enumeration machines and Turing machines; encoding Turing machines.

1. Reading:  Sipser §4.2.
2. Complete ps10 for Friday and Monday.
3. Prelim #2 will be held next Wednesday.

Wednesday:  undecidability (diagonalizations and reductions).

1. Reading:  Sipser §5.1.

Friday:  undecidability (more reductions).

1. Reading:  Sipser §5.3.  For enrichment/fun/weltschmertz, read Sipser Chapter 6.
2. The second prelim (next Wednesday) will cover all material through undecidability (so through today in class, through ps10, and through Chapter 5).  You may again use an 8.5"-by-11" crib sheet (two sides, hand-written or typed by you).

Week 8:

Monday:  complexity theory; TIME; and P.

1. Reading:  Sipser §7.1–7.2.
2. Complete ps11 for Friday and Monday.
3. Reminder:  Prelim #2 will be held on Wednesday.

Wednesday:  Prelim #2!

Friday:  P, NP, P vs. NP.

1. Reading:  Sipser §7.3; start §7.4.
2. Complete ps12 for Wednesday and Friday.
3. The final exam will be self-scheduled.

Week 9:

Monday:  P, NP, and NP-completeness; ptime reducibility.

1. Reading:  Sipser §7.5; continue on §7.4.

Wednesday:  Cook's Theorem.

1. Reading:  Sipser §7.4.
2. More reading:  Joey deVilla, "What happened to me and the new girl" [original link].  The Adventures of Accordian Guy in the Twenty-First Century, 2003.
3. Complete ps13 for Monday and Wednesday.

Friday:  wrapping up Cook's Theorem; NP-Completeness of Independent Set, Vertex Cover, etc.

1. Reading:  handouts on Independent Set and k-Coloring reductions.
2. More reading:  Lance Fortnow, "The Status of the P Versus NP Problem" [original link]. Communications of the ACM, 2009.

Week 10:

Monday:  space complexity; PSPACE; the complexity zoo.

1. Reading:  Sipser §8.1–8.3 (through the TQBF piece).
2. More reading:  the complexity petting zoo.
3. Your crib sheets for the final exam will be due on Thursday AM in my office in Weitz.  Details in class on Wednesday.

Wednesday:  course evals; ask me anything.

1. Crib sheets are due in your envelope by 11:00am Thursday (in the box outside my office in Weitz).
2. Bonus office hours at 2:30pm Thursday, or during the afternoon final slot Saturday (12:00pm to 2:30pm, in Olin 149).