Annoucements

THEORY OF COMPUTING
Com S 331

Course News

• 9 May 2003
Exam 3 has been graded. You can come and pick it up from my office (230 Atanasoff). Grades for homework 12 and the exam are now posted. Please verify that the grades posted on the course web site are correct - today is your last chance to make sure that corrections are made if needed!

• 8 May 2003
The Exam 3 solutions have been posted. Note that there are two solutions given for Problem 3; one non-deterministic and one deterministic.

• 5 May 2003
Brian will be holding office hours from 12-2 on Tuesday (May 6) and 1-2 on Wednesday (May 7th).

Grades for Homework 11 and solutions to Homeworks 11 and 12 have been posted on the web page. Note that this means that we will no longer accept any late Homework 12s.

Grades for Homework 12 will be posted together with Exam 3 and final grades. Please verify that all the grades posted for you are correct - this is your last chance to give us notice if not!

Update: Section 5.1 of Sipser's textbook has been posted on the Handouts page. It has several good examples of undecidability reduction proofs.

Mike will be holding office hours tomorrow (Tuesday May 6) from 2-4.

• 30 April 2003
Brian and Mike will be holding a joint review session from 12 to 1 on Wednesday, May 7th in Atanasoff B029. They will also be holding office hours during finals week; the hours will be announced shortly.

Brian's office hours from 4 to 5 today (Wednesday) have been cancelled. Instead, he will be holding office hours from 10 to 11 on Friday. Mike's office hours from 12 to 2 today (Wednesday) will be shifted to 1 to 3 today (Wednesday).

• 29 April 2003
Solutions and grades for Homework 10 have been posted.

• 28 April 2003
We have defined the terms acceptable and decidable in class. Note that r.e. (recursively enumerable) and Turing-recognizable mean the same thing as acceptable, and recursive means the same thing as decidable. You will see these other terms in the textbooks.

• 25 April 2003
Chapter 4 from Sipser's textbook has been posted on the Handouts page. It is highly recommended reading for doing Homework 12.

• 24 April 2003
Homework 12 has been posted. It will be due on Monday, May 5 by 12 noon. Since the solutions will be posted shortly after, no late homework will be accepted.

Homework 11 and 12 will count as extra credit. You are strongly encouraged to do them since they will help improve your grade and will be good preparation for Exam 3.

• 23 April 2003
All Exam 2 scores have been increased by 10 points. This will be reflected on the Grades page shortly.

For the remaining lectures, we will be covering Undeciadability from Chapter 4 of Sipser (this is one of the reference texts listed and is on reserve at the library).

Update: The solutions to Exam 2 have been posted on the Exams page. Note that there are two alternative solutions given to Problem 5.

• 22 April 2003
The due date for Homework 11 has been postponed to Monday, April 28.

• 21 April 2003
Solutions to Homework 9 have been posted.

• 19 April 2003
Homework 11 has been posted. It is due on Friday, April 25. Remember that the definition of the Turing Machine model and configurations given in lecture is different from the definitions in the book. We would like you to use the lecture definitions in the homework.

• 14 April 2003
Grades for Homework 8 and a histogram of Exam 2 grades have been posted. The homework can be retrieved at recitation Tuesday or after class on Wednesday.

• 12 April 2003
Homework 10 has been posted. It is due on Friday, April 18.

• 10 April 2003
Exam 2 grades are posted on the grades page (note also there's an option to download a PDF file of the same if you can't read it). Breakdown of who graded what is on the exams web page and a histogram and solution key will be forthcoming (probably by this weekend).

• 4 April 2003
Solutions for Homework 8 have been posted. Grades will be posted and homework returned later this week.

On Homework 9, you don't need to do problem 84d (page 334) - to do it correctly, you need a stronger theorem than the pumping lemma for CFLs from lecture or the book.

• 2 April 2003
Because some students found the practice exam given last time misleading and you already know the format of an exam in this course (from the first exam), there will not be a practice exam given for Exam 2.

• 25 March 2003
Solutions and grades for Homework 7 have been posted. They will be returned after class on Wednesday.

• 31 March 2003
Homework 9 has been posted. It is due on Friday, April 11.

• 28 March 2003
Topics for Exam 2 have been posted on the Exams page.

• 25 March 2003
Solutions and grades for Homework 6 have been posted. They will be returned after class on Wednesday.

• 12 March 2003
By popular demand, the due date for Homework 7 has been postponed to Monday, March 24. Note that Homework 8, which has just been posted, is due on Friday, March 28.

• 8 March 2003
One minor correction to the solution of Problem 5 in Homework 5 and some formatting changes made.

• 7 March 2003
A modified version of Homework 7 has been posted. The due date is Friday, March 14. If you downloaded an earlier version, note that there is an error in the due date. Also note that Problem 4 explains better what is being asked.

Update: Since I haven't heard any opposition to starting Exam 2 early, but received several messages supporting the extra time, the exam will be held 7:45 am - 8:55 am on Monday, April 7.

• 6 March 2003
Homework 7 has been posted. Grades and solutions for Homework 5 have been posted.

• 4 March 2003
All of the reference books listed on the front page are available via the Reserve Desk (details at the library's page for this course). These reference books are a good source of practice problems.

Update: The solutions to the first exam have been posted on the exams page.

• 3 March 2003
Looking at the exam scores, and the fact that several students mentioned that they could have done much better on the exam if they had just a little more time, I would like to consider giving an extra 20 minutes on the exam. To do this during class time, we would have to do 7:40 am - 8:50 am or 7:45 am - 8:55 am. Please let me know by the end of this week if you would prefer this option, or if you have a problem with this. I will decide based on your responses.
Soma Chaudhuri

• 28 February 2003
Problem 2 on Homework 6 has been changed. Also, the due date for the homework has been extended to Monday, March 10. You now have an extra weekend to work on the homework. Your solutions should include complete proofs.

• 27 February 2003
Grades have been posted for the exam and average for the course so far. This will be used to determine your mid-term grades. Details of who graded what can be found on the exams page and a histogram of the grades for the exam is available here. The exams will be returned after class on Friday (tommorrow).

• 26 February 2003
Homework 6 has been posted. It will be due on Friday, March 7. The topics for the homework will be covered starting this Friday.

• 24 Februrary 2003
An example of DFA to regular expression conversion has been posted on the handouts page.

• 21 February 2003
Late homework may be graded together with the next homework. Therefore, you may see a delay of a week before your scores are posted.

Good luck studying for the exam! We will be happy to answer questions by email. We will check mail periodically over the weekend. Send mail to cs331staff@iastate.edu and one of us will get back to you as soon as possible.

Update: Grades and solutions for Homework 4 are now up.

• 19 February 2003
Some students have asked if they would be required to give n-tuple definitions of NFAs and DFAs, or if transition diagrams are sufficient. You will probably be asked to do both; this will be specified in each exam problem. Make sure you are familiar with the formal notation.

Also, make sure you are comfortable defining general NFA's formally based on general NFAs provided. For example, given NFAs for languages A and B, we can define an NFA accepting AB.

• 17 February 2003
Homework 5 has been posted. It will be due on Friday, February 28. Note that, though the due date is not until next Friday, you should start working on the problems since it will help in preparing for the exam next Monday.

Update 1: Topics for the exam have been posted on the Exams page.

Update 2: A sample exam has also been posted on the Exams page.

• 12 February 2003
Exam I has been rescheduled to Monday, February 24.

Update: Grades and solutions for Homework 3 are now up.

• 7 February 2003
Homework 4 has been posted. It will be due on Friday, February 14. Note that Problems 2 and 3 (Kozen, page 315, problems 3 and 5) are on subset construction, which we will be covering in class on Monday. You can work on Problems 1 and 4 first.

• 6 February 2003
Grades and solutions for Homework 2 are now up.

• 3 February 2003
Solution to Homework 1 posted. Revisions to how solutions are posted made.

• 31 January 2003
Homework 3 has been posted. It will be due on Friday, February 7.

• 27 January 2003
The third recitation has been scheduled for T 5 in B29 Atanasoff. Since this is not an official recitation section, you do not need to register for it. It has been scheduled as an alternative for students who cannot attend their assigned recitation. As Brian will be teaching this, his office hours are now W 3-4 and R 12-1.

• 24 January 2003
Homework 2 has been posted. It will be due on Friday, January 31. I have listed a reference text in the course homepage which will be useful for this homework. The relevant sections will be posted.

Update 1: Sections 1.4 and 1.5 of the Elements of the Theory of Computation text have been posted on the Handouts page.

Update 2: Homework 2 has been modified at 5:30 pm. Specifically, Problem 4 has been corrected and Problem 5 has been clarified. If you already printed it out, please make sure you note the changes.

• 17 January 2003
Homework 1 has been posted. Given my delay in posting it and since many of you may have already left for the long weekend, I will make this due on Monday, January 27. Homework 2 will still be due on Friday, January 31.

• 14 January 2003
There has been a change of instructors. Jennifer Freeman is no longer the instructor. Soma Chaudhuri will be the new instructor for the course.

• 12 January 2003
Recitations will be held on January 14.