CS 381 - Introduction to Theory of Computing, Summer 2005
- July 1st - As mentioned in class, July 5th's class will be a review for the final. Please send me questions via email over the weekend if you would like
me to discuss particular topics in more depth at the session (or bring your questions with you on Tuesday morning). I expect to go over a brief summary
of all the material covered, to point out particularly important concepts and to clarify my expectations as to your familiarity with the material covered. In
the meantime, watch CMS for sample questions on Turing Machines later this weekend.
- June 24th - Frequently Asked Question: For the Turing Machines in HW7, can I change small details such as using/not using endmarkers, the
placement of the output on the tape after the machine halts, etc.? Answer - yes, you may make any minor technical modifications that you wish.
HOWEVER, you must explain very clearly in your high-level description how your machine works, and in what format it receives input and produces
output. Also, your modifications must not be so drastic that they change the machine completely - your submission should still clearly be a
machine that performs multiplication of arbitrary unary numbers. For instance, don't hard-wire in one or two pairs of numbers and say that your machine
can only multiply those.
- June 23rd - As mentioned in class today, please take the time over the weekend to read Lecture 30 in the book (sections on Multiple Tapes,
Two-Way Infinite Tapes, and Enumeration machines), as well as my extra handout on nondeterministic TMs. I
will not expect the same detailed grasp of this material as I will for things we cover in class, but I may well refer to it in lectures and/or
ask simple questions about it (e.g. true/false) on tests/quizzes. As always, feel free to ask me if you have any questions or trouble with
understanding this material.
- June 18 - Some sample questions for Prelim 2 are available in CMS (click on "Source" - this contains a zip of the questions and solutions).
- June 17 - 12 noon. There was a bug in one of my solutions for HW5, in the JFLAP file for PDA2.jff. The bug has now been fixed and the updated solutions
are in CMS.
- June 10 - Based on my observations while grading your proofs, I have prepared some guidelines for
proof writing for you. Please read them and follow them, as I will take points off for disregarding them.
- June 10 - Some people have inquired about the weighting of the assignments: each assignment will be counted equally in the calculation of your
final grade. You should not read any meaning into the fact that some assignments were out of 100 points and others were out of 50 points.
- June 07 - Updated versions of the handouts from today's class are now available (current version updated at noon).
- June 06 - By popular demand, I will make sure to be available in my office most of the day tomorrow (Tue 7th).
- June 05 - Some sample questions for Prelim 1 are available in CMS (click on "Source" - this contains a zip of the questions and solutions).
- June 01 - The final exam room has been finalized - it's Hollister 362 (our usual room)
- May 27 - The time of the final has now been fixed: July 6th, 3-5:30 pm. I will post the room on the website at a later date.
- May 24 - Please let me know ASAP if you have conflicts with other tests or exams on July 6th, so I can finalize an exam time.
- May 24 - CMS site for the class is now up. You will have to select "Summer '05" manually, as it is not the default yet. Please let me
know if you are in the class and cannot access CMS. Homework 1 (due Tuesday 5/31) is also available in CMS.