Before we start the course, please complete the following survey that will help me to improve the targeting of the course in future: computational theory pedagogy survey.
The textbook is called What Can Be Computed?, which we abbreviate as WCBC. A free electronic copy of WCBC and all of the sample programs are available on Moodle.
It is recommended, but not required, that you also purchase a printed copy of WCBC. The cost is $11. To order your printed copy, you must give $11 to me or to Tonya Miller in the department office by 5PM Thursday, January 26. Please pay by cash or check to "Dickinson College".
Today 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:
Required reading: Chapters 1 and 2 of WCBC.
Warm-up: use containsGAGA.py to determine whether the file CAGT.txt contains the string "GAGA".
Required reading: WCBC Chapter 3.
Required reading: WCBC Chapter 4.
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 JFLAP_Thin.jar from May 2011.
Minilab (ungraded): using JFLAP,
Required reading: WCBC Chapter 6.
Minilab (ungraded, but important and fun):
Required reading: WCBC Chapter 7, sections 7.1-7.5.
Required reading: WCBC Chapter 7, sections 7.6-end.
Required reading: WCBC Chapter 8.
Required reading: WCBC Chapter 9, sections 9.1-9.4.
Required reading: WCBC Chapter 9, sections 9.5-end.
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.
Required reading: WCBC Chapter 10.
Note that there is an "exams" link on the main course webpage. Important information about the upcoming midterm exam is available there.
Please take the midsemester survey.
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.
Exam 1. Covers WCBC Chapters 1-9.
Required reading: WCBC Chapter 11, sections 11.1-11.3.
Thank you very much for the feedback in the midsemester survey. Results and action items are available as tfocs-feedback-2017.pptx.
Required reading: WCBC Chapter 11, sections 11.4-end.
Required reading: WCBC Chapter 12, sections 12.1-12.3.
You'll need to update to a new version of verifyTspD.py (the previous version had a bug).
Required reading: WCBC Chapter 12, sections 12.4-end.
Required reading: WCBC Chapter 13, sections 13.1-4.
Required reading: WCBC Chapter 13, sections 13.5-end.
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.
Required reading: WCBC Chapter 14, sections 14.1-5.
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).
Required reading: WCBC Chapter 15.
Announcement about grading of homework H: You may optionally choose to submit homework H to the receptacle outside my office by 5 PM on Wednesday, April 19. If submitted by that time, the work will be graded and returned to you in class on Thursday, April 20. Otherwise, the graded work will not be returned to you until Monday, April 24 or later.
Revision of NP-completeness, and exam revision for chapters 10-14. No required reading.
I apologize in advance for the inconvenience, but I will be out of the office on Friday, April 21 (and in particular, my regular office hours will be canceled on that day). So our April 20 class session is the last meaningful opportunity to ask for help with exam material.
Exam 2 -- covers chapters 10--14.
Required reading: WCBC Ch16
Required reading: WCBC Ch17
