Detailed schedule and resources

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)

Class 15

Please complete the mid-semester survey

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

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

Class 14

Explanation of grade and curving for exam 1.

Required reading: WCBC Chapter 10.

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

Class 13

Exam 1. Covers WCBC Chapters 1-9.

Class 12

Exam review – 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 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

Announcements:

Exam web page is now up-to-date with correct information.
Get new version wcbc-programs-v2.0.zip from home page – includes bug fix for universal.py

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

Announcement: Don’t forget that an AI prompt is available to help you with this course. See course home page.

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.

Ribosome video from LMB Cambridge – skip to 1:45.

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

Warmup:

Install JFLAP (see JFLAP instructions below)

Announcements:

If printing code from VScode, save toner by printing with a white background – use Preferences: Toggle between Light/Dark Themes.
If formatting code within Microsoft Word, make sure to use a fixed width font (e.g., Consolas or Courier) for accurate indentation, and find the “Remove Space After Paragraph” option to ensure single spacing.
Icebreaker exercise: back row of students, be ready to state your name and your favorite Dickinson course outside COMP/MATH/DATA – state the name and the instructor of the course.
This is how to interpret graded homework assignments:
- First, remember that only a random subset of questions are graded. Second, usually some points are awarded for completeness (i.e. reasonable attempts at the questions that were not graded). The score written on your homework will look something like “14/14 + 10c = 24/24”. That means the graded questions were worth a total of 14 points and you scored 14/14. In addition, 10 points were awarded for completeness. Your total score was 24/24. So, the letter “c” in “10c” stands for “completeness”.
Homework solutions are available on Moodle.
- Also, we will go over a couple of homework mistakes in class.

Required reading: WCBC Chapter 5.

JFLAP

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

Announcement: How to get help in this course – see new link on the main course homepage.

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

Class will take place in Tome 117 today.
If campus is closed on Tuesday, class will take place online via Zoom. The link and details are on the course home page.

Minilab: Using WCBC programs from a different folder

Chapter 2 of the textbook explains how to use programs that are saved and run from same folder as the WCBC utilities. It’s fine to work like this, but it becomes difficult to keep your files organized in separate folders. This minilab demonstrates how use the WCBC programs while also storing your own Python files somewhere else.

Download and extract wcbc-programs-v1.1.zip into your comp314 folder.

Download use_containsGAGA.py and organize as follows:

comp314
├── classes
│   ├── class01
│   └── class02
│       └── use_containsGAGA.py
├── hw
└── wcbc-programs-v1.1

Open use_containsGAGA.py in IDLE or your favorite Python environment.
Run it, check that it works correctly, add a few more test strings to the source code and rerun. Note the use of
```
import sys
sys.path.append('../../wcbc-programs-v1.1')
```
to make the WCBC utils accessible.
Write your own use_isEven.py.
Write your own use_countLines.py. What inputs can you use? How about some files?

Lecture for today

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:

You can download Python and install it on your own laptop etc.
Python is also available on various college computers, and via online sites such as pythonanywhere.com.

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)