Note: This course ended on December 17, 2003

CS 229: Foundations of Computation

   Department of Mathematics and Computer Science
   Hobart and William Smith Colleges

   Fall, 2003.

   Instructor:  David J. Eck  (

   Monday, Wednesday, Friday, 10:10 -- 11:55.
   Room Gulick 206A.

   Course Handout:
   Textbook: Foundations of Computation (PDF format; local access only)

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 2003.

End of Term: December 8, 10, 12, and 17

During the last week of class, we will cover some of the material in Chapter 5. Unfortunately, we will not have time to cover this material in detail. The final exam is at 7:00 PM on Wednesday, December 17. I am assigning some final homework problems for you to work on. However, they will not be collected or graded. I will have a solution sheet on the last day of the course.

End of term office hours:

Final Homework and Final Exam Info (PDF format)

Fourteenth Weeks: December 1, 3, and 5

There is a test on Wednesday, December 3. An information sheet (PDF format) is available. On Monday and Friday, we will wrap up Chapter 4 by covering Sections 4.4 and 4.5. Any material that we cover on Monday will not be on the test.

Update (Monday, December 1): We decided in class today to postpone the test until Friday of this week and to postpone the due date on homework 9 until Wednesday.

Twelfth and Thirteenth Weeks: November 17, 19, 21, and 24

The reading for this two week period is Chapter 4, Sections 1 to 4. We will not get to Section 3.4 until the 24th. We will not cover all the topics in Sections 3.2 and 3.3. In particular, we will not be covering LL(1) or LR(1) parsing from 3.3. However, we will cover parse trees and left and right derivations.

There is no class on Wednesday, November 26 or Friday, November 28, because of the Thanksgiving holiday. The next homework assignment is due on the Monday after Thanksgiving, and I will have an answer sheet for you at that time. There is a test on the Wednesday after Thanksgiving.

Homework for the week, due Monday, December 1 (PDF format)

Eleventh Week: November 10, 12, and 14

We will finish Chapter 3 this week. The reading is Sections 3.6 and 3.7.

Homework for the week, due Wednesday, November 19 (PDF format)

Tenth Week: November 3, 5, and 7

The reading for the week is Chapter 3, Sections 4 and 5. We might start Section 6 by Friday.

Homework for the week, due Monday, November 10 (PDF format)

Ninth Week: October 27, 29, and 31

There is a test on Wednesday of this week. An information sheet for the test is available. We will cover Section 3.3 on Friday. This is the only reading for the week, and there will be no new homework assignment until next week.

Eighth Week: October 20, 22, and 24

Remember that there is a test next week, on Wednesday, October 29. For this week, you should read Sections 3.1 and 3.2. We might start talking about Section 3.3 on Friday, but that will not be on the test. Homework 6 is due next Monday, October 27. There will be office hours on Sunday from 12:00 until 3:00 in case you need help with the homework. Here is the assignment:

Homework for the week, due October 27 (PDF format)

Seventh Week: October 15 and 17

There is no class on Monday because of Fall Break. The reading for the week is Section 2.6. We will be skipping Sections 2.7 and 2.8. We might get started on Section 3.1 on Friday. Here is the homeowork assignment that is due Friday:

Homework for the week, due October 17 (PDF format)

Sixth Week: October 6, 8, and 10

We will continue with Chapter 2 and should finish Sections 2.3, 2.4, and 2.5 by the end of the week. We will move on to Section 2.6 next week. However, note that we will not cover Sections 2.7 and 2.8 in this course.

Here is the homework assignment that is due on Friday of this week:

Homework for the week, due October 10 (PDF format)

Fifth Week: September 29; October 1 and 3

The first test of the term is on Monday. After the test, we will start work on Chapter 2. The reading for the week is Sections 2.1, 2.2, and 2.3. The next homework assignment will be due on Friday of next week.

Fourth Week: September 22, 24, and 26

There will be a test on Monday of next week, which will cover Chapter 1, Sections 1 through 9. The only new reading for the week is Chapter 1, Section 8. We might do some examples from Sections 10 and 11, but they will not be on the test. An information sheet for the test is available (PDF format).

There is no new homework for this week.

Third Week: September 15, 17, and 19

This week, we move from the "formal proofs" of Section 1.5 to the more informal type of proof that is generally used in mathematics. We will look at general proof techniques, and then turn to an important specific technique known as Mathematical Induction. The reading for the week is Sections 7 and 9 in Chapter 1.

Homework for the week, due September 24 (PDF format)

Second Week: September 8, 10, and 12

We will continue the study of logic by looking at predicate logic, followed by logical deduction and formal proofs. The reading for the week is Section 4 and Section 5 of Chapter 1 in the textbook.

Homework for the week, due September 17 (PDF format)

First Week: September 1, 3, and 5

We begin the course with propositional logic and its relation to logic circuits, topics that will be generally familiar to you from CPSC 120. However, our approach will be a little more mathematical than it was in that course. The reading for the week is Chapter 1, Sections 1, 2, and 3.

Homework for the week, due September 10 (PDF format)