CS 229: Foundations of Computation


   Department of Mathematics and Computer Science
   Hobart and William Smith Colleges

   Fall, 2000.

   Instructor:  David J. Eck  (eck@hws.edu)

   Monday, Wednesday, Friday, 1:55 -- 2:50.
   Room Lansing 300.

   Course Handout:  http://math.hws.edu/eck/courses/cpsc229_f00.html

Assignments in CS 229, and possibly other information about the
course, will be posted on this page as the course is taught
during the Fall term of 2000.

The Final Exam

The information sheet for the final exam is available at http://math.hws.edu/eck/info/cs229_final.txt.

The End of the Course: December 4, 6, 8, and 14

The final exam for this course is scheduled for 1:30--4:30 PM on Thursday, December 14, in Lansing 300 (our regular classroom). You can expect the exam to be five or six pages long. It will be about 50% on material we have covered since the third test and 50% on older material. I will post a list of terms and ideas from the new material by Friday, December 8.

For the last week of the course, you should read Chapter 6 of the textbook. On the final exam, I will not ask you to "program" a Turing machine by creating its transition diagram or table of rules. However, I might give you a transition diagram for a Turing machine and ask you want the machine does when it is run with a given input. As for Sections 6.2 and 6.3, you are not responsible for all the proofs in those sections.

Fourteenth Week: November 27 and 29; December 1

For this week, you should read Sections 5.2 and 5.5. You do not need to read all of Section 5.3, but we will cover a few concepts from that section: the definition of parsing, parse trees, and ambiguity of grammars. From Section 5.4, you should only know that certain languages are not context-free, specifically the languages {anbncn | n is a natural number}, {w in {a,b}* | na(w) = nb(w) = nc(w)}, {ww | w in {a,b}*}, {am | m = n2 for some natural number n}, and {an | n is a prime number}.

Here is the homework for this week. This is the last homework assignment that you will turn in for this course. It is due on Wednesday, December 6:

I will give out the short final section of the textbook in class on Friday.

Twelfth and Thirteenth Weeks: November 13, 15, 17, and 20

Because of Thanksgiving vacation, there is no class on November 22 or 24.

After the test on Wednesday, we will start Chapter 5. You should read Section 5.1. The following homework exercises are due in class on Wednesday, November 29:

We might skip Sectin 5.2. (I will let you know soon.)

Eleventh Week: November 6, 8, and 10

We will finish Chapter 4 this week. You should read Section 5 of Chapter 4. I will cover some parts of Section 6 in class, but you are not required to read the entire section.

There will be a test next week, on Wednesday, November 15. Because of the test, I will not collect any homework next week. However, I strongly advise you to do questions 12, 13, and 16 from Chapter 4 (pages 145 and 146), since similar questions might appear on the test.

An information sheet for the test can be found at http://math.hws.edu/eck/info/cs229_test3.txt.

Tenth Week: October 30; November 1 and 3

The reading for this week consists of Sections 3 and 4 of Chapter 4. These sections cover FSA's (Finite State Automata), which are our first example of abstract computing "machines." The following homework is due next Wednesday, November 8:

Ninth Week: October 23, 25, and 27

We will begin Chapter 4 on Wednesday. You should read Sections 1 and 2 of Chapter 4. The following homework is due next Wednesday, November 1:

Eighth Week: October 16, 18, and 20

There is a test on Wednesday of this week. You can find more information about the test at http://math.hws.edu/eck/info/cs229_test2.txt.

You should read sections 3.3 and 3.4. (However, you will not be responsible for the material in 3.4 on binary trees, since not everyone in the class has taken CPSC 125.) We will not cover Section 3.5. The next two chapters will be available in class next Monday.

The following homework exercises are due next Wednesday, October 25:

Seventh Week: October 11 and 13

Monday of this week is a holiday. We will cover Section 3.2 on Wednesday. On Friday, we will begin Section 3.3. There is a test on Wednesday of next week, but it will not cover Section 3.3. The following homework from section 3.2, which will be covered on the test, is due in class next Monday:

Sixth Week: October 2, 4, and 6

I have decided to skip Sections 2.7 and 2.8, at least for the time being. After finishing up a few remaining items from Section 2.6, we will move on to a more formal study of proof and proof techniques. We will begin by going back to look at the last section of chapter 1.

The reading for the week is:

We might not get to Section 3.2, and I won't assign any homework on it for this week. The following homework is due next Friday, October 13. (This is a change from the originally announced due date of October 11. Remember that there are no classes on October 9 or 10.)

Fifth Week: September 25, 27, and 29

For this week, you should read Sections 6 and 7 of Chapter 2. (We will begin Section 7 on Friday, but there will be no homework from this section until next week.) The homework from sections 2.4 and 2.5, which was assigned last week, is due next Monday, October 2. To that, you can add the following homework, which is also to be turned in on Monday:

Fourth Week: September 18, 20, and 22

The main even for the week is the first test of the course, which is on Wednesday, September 20. After getting the test out of the way, you should read Sections 4 and 5 of Chapter 2. However, you are not responsible for learning the material on the JavaScript programming language that is covered in Section 5. We will probably not finish all the material from these two sections in class this week. The homework from these sections will not be collected until Monday, October 2, along with other homework that will be assigned next week. The homework for Sections 4 and 5 is as follows:

Again, note that this homework is to be turned in on Monday, October 2.

I will hand out a sheet of information about the test in class on Monday, September 18. For an on-line copyf of that sheet, click here.

Third Week: September 11, 13, and 15

For this week, you should read Sections 1, 2, and 3 of Chapter 2. The following homework from these sections is due in class next Monday, September 18:

(Note that the last question is an essay question. A good answer will require a few paragraphs.)

Reminder: There is a test next week, on Wednesday, September 20. It will cover Chapter 1, Sections 1 through 4 and Chapter 2, Sections 1 through 3.

Second Week: September 4, 6, and 8

The reading assignment for this week is Sections 3 and 4 of Chapter 1. (Yes, I assigned Section 3 last week, but we didn't do anything with it in class last week. So this week, read it for real.) I will not assign Section 5 from Chapter 1, although we will probably cover a few of the ideas from that section in class. There will be no homework assignments from Section 5.

The following homework problems are due in class next Monday, September 11:

I will have extra office hours on Sunday, September 10, from 1:00 until 3:00.

First Week: September 28 and 30 and October 1

For the first week of the course, you should read Sections 1, 2, and 3 of Chapter 1 in the textbook. (You will receive these as part of a handout on the first day of classes.) Do the following exercises and turn them in on the following Monday, September 4:

Note that we will probably not finish all of Section 3 during the first week of classes. There will be homework exercises from Section 3 during the second week of the term.