Class 1 was canceled due to the snowstorm. We will be combining the schedule for class 1 and class 2 into a compressed version of class 2, then continue as previously scheduled starting with class 3.
The textbook is called What Can Be Computed?, which we abbreviate as WCBC. Part I of WCBC, and all of the sample programs are available on Moodle (filenames wcbc-part1-Jan22.pdf and wcbc-programs-1-18-2016.zip). Parts II and III of WCBC will be made available later in the semester.
You can also purchase a printed copy of WCBC Part I for $10. To
order your printed copy, you must give $10 to me or to Tonya Miller in
the department office by 5PM Thursday, January 28 midnight Friday,
January 29. Please pay by cash, check to "John MacCormick" or PayPal
to jmac@dickinson.edu.
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.
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.
Please download a new copy of the programs folder (available on Moodle as wcbc-programs-2-22-2016.zip). Do not use the previous version, as some important changes have been made.
Required reading: WCBC Chapter 9, sections 9.1-9.4.
Required reading: WCBC Chapter 9, sections 9.5-end.
Parts II and III of the textbook are now available on Moodle.
Please give me five dollars by the end of class today if you would like to purchase a printed copy of the second half of the textbook. Thanks!
Required reading: WCBC Chapter 10.
Note that there is now an "exams" link on the main course webpage. Important information about the upcoming midterm exam is available there.
There is a handout available on Moodle (sameGT-handout.pdf) covering the additional example described in class today.
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.
Required reading: WCBC Chapter 11, sections 11.4-end.
Please take the midsemester survey.
Required reading: WCBC Chapter 12, sections 12.1-12.3.
Thank you very much for the feedback in the midsemester survey. A complete listing of responses is available: all-responses.pdf. As a result of this, I will do my best to slow down a little in the technical parts of lectures (it is a 60%-40% split on whether lectures are "a little too fast" or "about right"). Most other aspects of the course appear to be on track, but of course I take all feedback seriously and will pay attention to all of the suggestions. One important piece of feedback for students is that 75% of students are not reading the relevant sections of the textbook in advance. It will be extremely helpful for you to read the textbook in advance, even if you find it difficult to understand.
Required reading: WCBC Chapter 12, sections 12.4-end.
Required reading: WCBC Chapter 13, sections 13.1-4.
Please also note the following extra credit opportunity. Attendance at the Clarke Forum panel session, iPhone vs. the FBI: Government Surveillance in the Post-Snowden Era, will entitle you to upgrade the homework revision of a single homework assignment of your choice. Specifically, instead of receiving 50% of deducted points back, you will receive 100% of the deducted points (assuming your revisions are complete and correct). To claim your upgrade, keep the paper program of the Clarke Forum event and staple it to the front of your homework revision when you submit it.
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.
Revision of NP-completeness, and exam revision for chapters 10-14. No required reading.
Exam 2 -- covers chapters 10--14.
Required reading: WCBC Ch16
Required reading: WCBC Ch17
