Detailed schedule and resources

Class 28

Required reading: WCBC Ch18

Today’s PowerPoint: 18-conclusion.pptx.

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

Class 27

Please complete the official feedback form for this course.

Required reading: WCBC Ch17

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

Class 26

Required reading: WCBC Ch16

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

Class 25

Exam 2 – see exams page for details.

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.

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.

Class 21

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

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

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.

Class 19

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

Today’s PowerPoint: 13-polyreductions.pptx.

Warmup for today: warmup-class19.docx.

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.

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.

Class 16

Please complete the mid-semester survey

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)

Class 15

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

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

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.

Class 12

Required reading: WCBC Chapter 10.

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

Class 11

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

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.

Class 10

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

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

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

Class 9

Required reading: WCBC Chapter 8.

Today’s warm-up exercise: warmup09.docx

Today’s PowerPoint: 08-nondeterminism.pptx.

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.

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.

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.

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.

If the JFLAP website is down you can get JFLAP on Moodle instead

If JFLAP won’t run when you click on it, open a terminal, navigate to the directory where you have saved the file JFLAP7.1.jar, then enter the command

java -jar JFLAP7.1.jar

(Of course, you need to have Java installed on your computer for this to work.)

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.

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

Class 3

Required reading: WCBC Chapter 3.

Handout for today: class3-handout.pdf.

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

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

Class 2

Required reading: Chapters 1 and 2 of WCBC.

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

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
  • 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)

—- Last modified: Thu May 04 00:45:45 UTC 2023 by jmac.