Detailed schedule and class resources

Class 1: Tuesday, January 19

We will go through the syllabus and an overview of the course, corresponding to WCBC Chapter 1.

If there's time, we will try to run and edit some Python programs using IDLE. Key points:

• Always use Version 3.x of Python for this course
• You can download Python 3 and install it on your own laptop etc.
• Python is also available on all department iMacs in Tome: use Finder | Applications | Python 3.4 | IDLE

Class 2: Thursday, January 22

Required reading: Chapters 1 and 2 of WCBC.

Warm-up: use containsGAGA.py to determine whether the file CAGT.txt contains the string "GAGA".

Class 3: Tuesday, January 27

Required reading: WCBC Chapter 3.

class3-handout.pdf

Class 4: Thursday, January 29

Required reading: WCBC Chapter 4.

Class 5: Tuesday, February 3

Required reading: WCBC Chapter 5.

Minilab (ungraded): using JFLAP,

• experiment with binary-incrementer.jff
• Create and test the basic version of LastTtoA (fig 5.5)
• Create and test the abbreviated version of LastTtoA (fig 5.6)
• Create and test a machine that processes genetic strings, changing every "c" to a "g" and every "g" to a "c"
• Optional extras: Create a machine that accepts any string of length 10 or more that also contains an "a".

Class 6: Thursday, February 5.

Required reading: WCBC Chapter 6.

Minilab (ungraded, but important and fun):

• Download the Universal Turing machine of Lucas and Jarvis (see also their explanatory webpage if you're interested).
• Create a LastBtoA machine, similar to LastTtoA from the previous class, but using only the alphabet a,b (and blanks). If this isn't clear, you can also use the provided version of LastBtoA. We will use LastBtoA as an input to the Lucas and Jarvis Universal Turing machine.
• Encode LastBtoA so that it is suitable for input to the Lucas and Jarvis Universal Turing machine. An explanation of the encoding is provided. Lucas and Jarvis provide another explanation on their website.
• Test your encoding using the Universal Turing machine and an appropriate input string. In JFLAP, the best way to run this test is to first save your input to a text file, then use the "multiple inputs (transducer)" option from the "input" menu.

Class 7: Tuesday, February 10.

Required reading: WCBC Chapter 7, sections 7.1-7.5.

Class 8: Thursday, February 12.

Required reading: WCBC Chapter 7, sections 7.6-end.

Handout providing an additional explanation of reducing YesOnString to KoalaOnString.

Class 9: Tuesday, February 17.

Required reading: WCBC Chapter 8.

Class 10: Thursday, February 19.

Required reading: WCBC Chapter 9, sections 9.1-9.4.

Handout: dfa-regexp-conversion-examples-v2.pdf (version 2, updated after class 2/19/15)

Class 11: Tuesday, February 24.

Required reading: WCBC Chapter 9, sections 9.5-end.

Class 12: Thursday, February 26.

Required reading: WCBC Chapter 10, sections 10.1-10.3.

Class 13: Tuesday, March 3.

Required reading: WCBC Chapter 10, sections 10.4-end.

Please take the midsemester survey.

Class 14: Thursday, March 5.

Exam 1. Covers WCBC Chapters 1-9.

Class 15: Tuesday, March 17.

Required reading: WCBC Chapter 11, sections 11.1-11.3.

Class 16: Thursday, March 19.

Required reading: WCBC Chapter 11, sections 11.4-end.

Class 17: Tuesday, March 24.

Required reading: WCBC Chapter 12, up to end of section 12.1.

Class 18: Thursday, March 26.

Required reading: WCBC Chapter 12, sections 12.2-end.

Class 19: Tuesday, March 31.

Required reading: WCBC Chapter 13, sections 13.1-3.

Class 20: Thursday, April 2.

Required reading: WCBC Chapter 13, sections 13.4-end. You will also need the handout: Definitions of CircuitSAT, SAT, and 3SAT. (As of 3/30/15, the content of this handout does appear in Chapter 13.)

Class 21: Tuesday, April 7.

Required reading: WCBC Chapter 14, sections 14.1-5.

Class 22: Thursday, April 9.

Required reading: WCBC Chapter 14, sections 14.6-12. Please also read the excerpt from Lance Fortnow's book, The Golden Ticket (available on Moodle).

Class 23: Tuesday, April 14.

Required reading: read the two excerpts from Charles Petzold's book, The Annotated Turing -- both are available on Moodle.

Update: Chapter 15 of the textbook is available on Moodle, as of 4/13/2015. This will help you to understand Turing's paper in a little more detail.

Class 24: Thursday, April 16.

Revision of NP-completeness, and exam revision for chapters 10-14. No required reading.

Class 25: Tuesday, April 21.

Exam 2 -- covers chapters 10--14.

Class 26: Thursday, April 23.

Required reading: WCBC Ch16

Class 27: Tuesday, April 28.

Required reading: Richard Karp's 1972 paper, Reducibility Among Combinatorial Problems, available on Moodle. Obviously, you're not expected to understand all details of this paper. Here's what you should do to prepare for our discussion:

1. Skim the whole paper, skipping over any technical definitions and formulas, just to get a feel for what is there.
2. Read pages 94-97 a bit more carefully, but still skipping over anything that seems tricky.
3. Choose 2 or 3 problems from the list of 21 problems on pages 94-96. (Include at least one problem that we have not discussed in class.) For each of your chosen problems, make sure you understand Karp's description of the problem.
4. Choose 1 reduction from the 20 reductions in the proof of the main theorem, pages 97-100. (Don't choose one of the ones we have proved in class.) Understand the reduction to the best of your ability, and make some brief notes so that you can present an explanation of the reduction to the rest of the class. If there are some parts of the reduction you can't understand, that's OK -- just make a careful note of anything you don't understand, and include a description of this in your presentation plan.

Update, 4:30pm 4/27/15: Chapter 17 of the textbook is now available on Moodle. Given the late availability, this can be considered optional reading. But it will probably help you to understand one or two of Karp's reductions mentioned above, so I do recommend you take a look at it either before class or after class.

Class 28: Thursday, April 30.