Detailed schedule and class resources

Class 28

Required reading: WCBC Ch18

Today's PowerPoint: 18-conclusion.pptx.

Also today: exam review and independent homework on assignment J.

Whiteboard with review of logical systems: logical-systems-review.png.

Recording of this class: class 28.

Class 27

Required reading: WCBC Ch17

Today's PowerPoint: 17-karps-problems.pptx.

Recording of this class: class 27.

Class 26

Required reading: WCBC Ch16

Today's PowerPoint: 16-godels-theorem.pptx.

Recordings of this class: segment 1, segment 2, segment 3.

Class 25

Exam 2 -- covers chapters 10-14.

There is no in-classroom session today and no Zoom session. Please work on the exam during class time and submit questions to the Exams channel on Teams.

Class 24

Exam review for chapters 10-14. No required reading.

Class 23

Required reading: WCBC Chapter 15.

Today's PowerPoint: 15-original-turing-machine.pptx.

Recordings of this class: segment 1, segment 2, segment 3.

Class 22

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

Fortnow discussion questions: fortnow-discussion-questions.docx.

Today's PowerPoint (same as last time): 14-np-completeness.pptx.

Recordings of this class: segment 1, segment 2.

Class 21

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

Today's PowerPoint: 14-np-completeness.pptx.

Recordings of this class: segment 1, segment 2.

Class 20

Required reading: WCBC Chapter 13, sections 13.5-end.

Today's PowerPoint (same as last time): 13-polyreductions.pptx.

Clarification of what you are expected to understand: the details of the Tseytin transformation will not be tested in homework or exams. All other reductions in this chapter are examinable.

Recordings of this class: segment 1, segment 2, segment 3, segment 4.

Class 19

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

Today's PowerPoint: 13-polyreductions.pptx.

Warmup for today: warmup-class19.docx.

Recordings of this class: segment 1, segment 2, segment 3.

Class 18

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

Today's PowerPoint (same as last time): 12-polycheck-and-npoly.pptx.

Warmup for today: warmup-class18.docx.

Whiteboard for proof that PolyCheck is a subset of NPoly: polycheck-in-npoly-whiteboard.png.

Recordings of this class: segment 1, segment 2, segment 3.

Class 17

Required reading: WCBC Chapter 12, sections 12.1-12.3.

Warmup for today: warmup-class17.xlsx.

Today's PowerPoint: 12-polycheck-and-npoly.pptx.

Recordings of this class: segment 1, segment 2.

Class 16

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

Today's PowerPoint (same as last time): 11-poly-and-expo.pptx.

Handout comparing the proof that the halting problem is undecidable with the proof that HaltsInExpTime cannot be solved in polynomial time: Proof-that-HET-not-in-poly.pdf. (optional enrichment)

Warmup for POLY vs EXPO: warmup-for-poly-vs-expo.png.

Recordings of this class: segment 1, segment 2.

Class 15

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

Today's PowerPoint: 11-poly-and-expo.pptx.

Recordings of this class: segment 1, segment 2,

Class 14

Exam 1. Covers WCBC Chapters 1-9.

Class 13

Exam revision -- please bring questions to class and we will go over them. We can go over specific examples and/or general areas depending on student demand.

Recordings of this class: segment 1, segment 2.

Whiteboard notes from class: rices-theorem.png, pumping-lemma-etc.png.

Class 12

Required reading: WCBC Chapter 10.

Today's PowerPoint: 10-complexity-theory-basics.pptx.

Whiteboard notes on big ideas in the course so far: big-ideas.png.

Recordings of this class: segment 1, segment 2.

Class 11

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

Please fill out the GitHub username form if you haven't done so already.

Today's PowerPoint (same as last time): 09-finite-automata.pptx.

Optionally, you can gain familiarity with pumping lemma proofs by playing a game within JFLAP. Choose "regular pumping lemma" from the initial JFLAP window. Then choose "computer goes first" (the "you go first" option is also interesting and useful, but we don't explain it further here). Choose one of the languages. Now your job is to force the computer to violate the pumping lemma. JFLAP's notation is as follows: m is the pumping cutoff; w is the string in the language that will have some substring pumped; i is the number of times w will have a substring pumped; w gets partitioned as w=XYZ where Y is the substring to be pumped.

Recording of this class: class 11.

Class 10

If you haven't done so already, please fill out the survey about in-person class meetings.

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

Today's PowerPoint: 09-finite-automata.pptx.

In-class JFLAP activity: activity-class10.docx.

Recordings of this class: segment 1, segment 2.

Class 9

Required reading: WCBC Chapter 8.

Today's warm-up exercise: warmup09.docx

Today's PowerPoint: 08-nondeterminism.pptx.

Recordings of this class: segment 1, segment 2.

Class 8

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

Today's warm-up exercise: warmup08.docx

Today's PowerPoint (same as last time, starting on slide 13): 07-reductions.pptx.

Recordings of this class: segment 1, segment 2.

Class 7

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

Today's warm-up exercise: warmup07.docx

Today's PowerPoint: 07-reductions.pptx.

Recordings of this class: segment 1, segment 2.

Class 6

Required reading: WCBC Chapter 6.

Today's PowerPoint: 06-universal-programs.pptx.

Really nice online cellular automaton simulator.

Optional 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.

Recordings of this class: segment 1, segment 2.

Class 5

Required reading: WCBC Chapter 5.

To download JFLAP, follow the instructions at jflap.org (you will be asked to fill out a short form). The best version for this course is JFLAP7.1.jar from Jul 27, 2018.

Minilab (ungraded): using JFLAP,

experiment with binary-incrementer.jff
Create and test the basic version of LastTtoA (fig 5.3)
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".

Today's PowerPoint: 05-turing-machines.pptx.

Recordings of this class: segment 1, segment 2.

Class 4

Required reading: WCBC Chapter 4.

Today's warm-up exercise: 04-warmup.docx

Today's PowerPoint: 04-computational-problems.pptx.

Programs for experimenting with ESS and DESS: switchAndConcat.py, switchAndConcat1Param.py. (Remember to move these into your wcbc-programs-v1.1 folder.)

Recordings of this class: segment 1, segment 2.

Class 3

Required reading: WCBC Chapter 3.

Handout for today: class3-handout.pdf. If you have easy access to a printer, print this out before class, but that is not essential.

Today's warm-up exercise: 03-warmup.docx

Today's PowerPoint: 03-impossible-programs.pptx.

Recordings of this class: segment 1, segment 2.

Class 2

Required reading: Chapters 1 and 2 of WCBC.

Today's PowerPoint: 02-computer-programs.pptx.

Recordings of this class: segment 1, segment 2.

Class 1

The textbook is called What Can Be Computed?, which we abbreviate as WCBC.

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

Today's PowerPoint: 01-intro.pptx.

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 the search functionality (top right of the desktop) to open IDLE with Version 3.x of Python
- see the accompanying screenshot if desired
- you can ignore any warnings about the version of Tcl/Tk

Another option is to use an online Python environment such as https://repl.it/new/python3. Here is some code to paste in and experiment with:

    
def containsGAGA(inString): 
    if 'GAGA' in inString: 
        return 'yes' 
    else: 
        return 'no'

Here's another one:

  
def multiply(inString): 
    (M1, M2) = inString.split()
    product = int(M1) * int(M2) 
    return str(product)

Recordings of this class: segment 1, segment 2.