Detailed schedule and class resources

Class 1: Monday, January 20

Required reading: The introductory reading 01-intro-reading.pdf is available on Moodle..

Example code: class01-programs.zip. (Individual programs are also available from the list of all sample code.)

Instructions for editing and running Python programs on the lab machines. (These instructions were written for people with no CS background, so I apologize if they seem unnecessarily laborious.)

Some essential practice exercises:

• Over the next week or two, learn the basics of Python. Pick your favorite online tutorial. The official Python site provides a good one, for example: http://docs.python.org/2/tutorial/index.html.
• Learn how to convert Python programs from function form to file form and vice versa. Practice on e.g. countLines.py.

Note on Python versions: All example code will work with Python version 2.x. You can use Python 3.x if you want, but you will need to change print ... to print(...), and maybe some other things too.

Class 2: Thursday, January 23

Lecture notes: class02-impossible-programs.pdf.

Source code: class02-programs.zip.

Note that a hint was added to the homework assignment. Make sure to get the latest version.

Class 3: Monday, January 27

Lecture notes: class03-turing-machines-v1.1.pdf.

Minilab: using JFLAP,

• Create and test the basic version of LastTtoA (figure 3 of the lecture notes)
• Create and test the abbreviated version of LastTtoA (figure 4 of the lecture notes)
• Create and test a machine that processes genetic strings, changing every "c" to a "g" and every "g" to a "c"
• Optional extras: (i) Create a machine that increments a binary number. (ii) Create a machine that accepts any string of length 10 or more that also contains an "a".

Class 4: Thursday, January 30

Lecture notes: class04-universal-turing-machines.pdf.

Source code: class04-programs-v2.zip.

Minilab:

• 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 5: Monday, February 3

Lecture notes: class05-reductions-notes-v2.pdf. (version 2 uploaded 4pm, 2/3/14.)

Please note the discussion about homework deadlines posted on the homework page.

Class 6: Thursday, February 6. Happy Waitangi Day!

Lecture notes: class06-rices-theorem-v2.pdf.

HW1 solutions are available on Moodle.

Class 7: Monday, February 10.

A single reading for this class and the next class is available on Moodle.

Class 8: Thursday, February 13.

This class covers the second half of the reading posted on Moodle.

Class 9: Monday, February 17.

A single reading for Topic 5 (classes 9-12) is available on Moodle.

Example code for today: findMultiples.py

Solutions to homework assignment 3 have been posted to Moodle.

Some details about Thursday's exam are available from a link on the main course page (you may need to hit refresh to view it).

Class 11: Monday, February 24.

The reading for this topic has been significantly updated. Please download a new copy from Moodle. (The filename is classes09-11-complexity-basics-v2.pdf).

Homework assignment 5 is available, and after today's class, we have covered everything you need to attempt this assignment.

Exam solution is on Moodle.

Class 12: Thursday, February 27.

The reading for this topic has been updated again (sorry!). Please download a new copy from Moodle. (The filename is classes09-11-complexity-basics-v3.pdf).

Class 13: Monday, March 3.

A reading is available on Moodle (filename linz-dfas-pages38-47.pdf).

Additional notes: a one-page note giving the formal definition and examples of a language, languages.pdf.

Class 14: Thursday, March 6.

A reading is available on Moodle (filename linz-regexps-pages71-75.pdf).

Class 15: Monday, March 17.

Lecture notes: class15-pumping-lemma.pdf.

Class 16: Thursday, March 20.

Please take the class survey.

Today's class consists mostly of independent work on homework and exam revision. I will be available to answer questions.

In addition, we can check out a few demos of working with dfas and regular expressions. JFLAP has facilities for converting between dfas and regexps, and there are various online resources, such as the HackingOff regexp-to-dfa converter.

Class 17: Monday, March 24.

A reading is available on Moodle (filename class17-nondeterminism.pdf).

Example code and input files are available as class17-programs.zip.

Class 19: Monday, March 31.

Lecture notes: class19-nfas-v3.pdf (version 3 uploaded 4/8/14).

Class 20: Thursday, April 3.

Lecture notes: class20-polycheck-defn.pdf.

Class 21: Monday, April 7.

Lecture notes: class21-polycheck-npoly-equiv.pdf and class21b-three-problems.pdf.

Class 22: Thursday, April 10.

Lecture notes: class22-polytime-reductions.pdf.

Don't forget to finish the Golden Ticket excerpt from Lance Fortnow's book before our next class. (The excerpt is available on Moodle.)

Class 23: Monday, April 14.

Lecture notes: class23-p-equals-np.

Class 24: Thursday, April 17.

Lecture notes: class24-more-np-completeness.pdf.

Class 25: Monday, April 21.

Required reading: the excerpt from Chapter 4 of The Annotated Turing by Charles Petzold, available on Moodle.

Optional reading: read Sections 1-3 of Turing's original 1936 paper On Computable Numbers..., also available on Moodle.

Ungraded in-class project: over the next three classes, use JFLAP to develop one or more Turing machines that do something interesting. Suggestions include:

• a machine that increments a binary number
• a machine that converts a unary number to a binary number
• a machine that converts a binary number to a unary number
• a machine that adds two unary numbers
• a machine that adds two binary numbers
• a machine that multiplies two binary numbers
• a machine that recognizes the language a^n b^n
• a machine that recognizes the language a^n b^n c^n
• a machine that recognizes binary strings that are palindromes (i.e. they read the same backwards as forwards)

Class 26: Thursday, April 24.

Required reading: Chapter 11 of The Annotated Turing by Charles Petzold, available on Moodle.

Class 27: Monday, April 27.

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.