CPSC 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:05.
   Room Gulick 206A.

About This Course

This course surveys the mathematical foundations of computer science. These foundations include some basic mathematical concepts, such as logic, sets, and functions. They also include some ideas more specific to computing, such as languages and abstract machines.

The prerequisite for the course is CPSC 124: Introductory Programming. However, the prerequisite is more for general background in computing rather than for detailed programming skills. We will use the Java programming language in a few examples, and there may be a few homework exercises that use Java. However, for the most part, this is a mathematics course, and most of the exercises will be mathematical.

You do not need to purchase a textbook for the course. The textbook will be handed out in class. The text was written by Professors David Eck and Carol Critchlow. The book includes five chapters:

The first two chapters cover general mathematical background. This material is often covered in a course on "Discrete Mathematics," along with other topics such as probability and graph theory. The material that we've chosen for inclusion in these chapters is the most fundamental and is a prerequisite for the rest of the book. The final three chapters cover material that form the theoretical foundation of computer science. This material is often covered in a course called "Automata Theory" or "Formal Language Theory." It deals with computation, languages, and automata and with their interrelationships. The word "automata" is just another term for "computing machines," and the languages that we are interested in here are the ones that are used to program or describe computing machines.

Although the course is mathematical, the first four chapters, at least, are highly relevant to applications of computer science. There are sections throughout these chapters that cover applications. The chapter on Turing machines probably has few practical applications, but it is right at the theoretical heart of computer science and no one can claim to understand computers without knowing this material.

Homework Assignments

There will be weekly homework assignments, which will be collected and graded. A few of the homework problems might involve writing short programs or code segments, but this is not a programming class and there will be no major programming assignments. The assignments will be similar to the end-of-section assignments in the textbook but will not be taken directly form the book. (I will be writing new exercises because the ones in the textbook have been used for the past three years.)

The assignments for each week will be collected the following week. Generally, assignments will not be accepted late. However, under certain circumstances, such as illness, I will consider accepting an assignment in the class period after the one when it is due.

Although I will collect and grade just a few exercises each week, I encourage you to try as many of the exercises in the textbook as you can find time for. You can only learn mathematics by doing it! During my office hours, I will be happy to answer questions about exercises from the textbook, and I will do some of them as examples in class.

Please note that for all homework exercises, you are required to show your work and explain your reasoning. You should not expect to get much credit for unsupported answers. Please write up your answers carefully, with full English sentences and paragraphs where they are appropriate. Math problems are, among other things, writing assignments, and you should write your answers with the same care that you would give to any other writing assignment.

It's OK for you to work with other people in the class on homework problems. However, you should, in the end, write up your own solutions in your own words to be turned in.

Tests

There will be three in-class tests, which will be given on Monday, September 29; Wednesday, October 29; and Wednesday, December 3. The final exam for the course will take place at the time scheduled by the Registrar's office: Wednesday, December 17, at 7:00 PM The final exam will be in our regular classroom. The final exam will cover material from the entire term, with some emphasis on material that is covered after the third in-class test.

Grading

Your numerical grade for the course will be computed as follows:

            First Test:        15%
            Second Test:       15%
            Third Test:        15%
            Assignments:       35%
            Final Exam:        20%

The grade might then be lowered because of missed classes. In my grading scale, an A corresponds to 90--100%, B to 80--89%, C to 65--79%, D to 50--64%, and F to 0--49%. Grades near the endpoints of a range get a plus or minus.

Attendance Policy

This is a college-level class, which moves very quickly. Attendance is required. I will take attendance, and your final grade for the course can be lowered by up to a full letter grade if you miss class without a good excuse.

Office Hours, E-mail, and Web

My office is room 301 in Lansing Hall. My office phone extension is 3398. I am on campus most days, and you are welcome to come in anytime you can find me there. My regular office hours will be posted on my door, as soon as my schedule is fixed. Office hours are times when I promise to try my best to be in my office. I do not generally make appointments during my office hours, since they are times when I am available to students on a first-come, first-served basis. When necessary, I can make appointments for meetings outside my scheduled office hours.

My e-mail address is eck@hws.edu. E-mail is good way to communicate with me, since I usually answer messages within a day of the time I receive them.

There is a short Web page for this course at http://math.hws.edu/eck/cs229_f03/. I will post weekly readings and assignments on that page. You can find them there in case you miss them in class.

Tentative Schedule

Here is a very tentative weekly schedule of topics for the course:

Week Topic
Sept. 1 Propositional Logic and Boolean Algebra. (Chapter 1)
Sept. 8 Logic Circuits; Predicate Logic. (Chapter 1)
Sept. 15 Predicate Logic; Deduction and proof. (Chapter 1)
Sept. 22 Proof methods including contradiction and induction. (Chapter 1)
Sept. 29 TEST on Monday; Sets. (Chapter 2)
Oct. 6 Functions; Programming with Sets and Functions. (Chapter 2)
Oct. 13 No class Monday; Counting; Introduction to languages. (Chapters 2 and 3)
Oct. 20 Regular languages and regular expressions. (Chapter 3)
Oct. 27 TEST on Wednesday; DFA's. (Chapter 3)
Nov. 3 NFA's; Regular expressions and FA's. (Chapter 3)
Nov. 10 Non-regular languages; Introduction to grammars. (Chapters 3 and 4)
Nov. 17 Context-free grammars, parsing and the pumping lemma. (Chapter 4)
Nov. 24 No class Wednesday or Friday; Continue with context-free grammars. (Chapter 4)
Dec. 1 TEST on Wednesday; General grammars; Turing machines. (Chapters 4 and 5)
Dec. 8 Turing machines and computability.. (Chapter 5)
Final Exam: Wednesday, December 17, 7:00 PM