CPSC 229:
Foundations of Computation

   Department of Mathematics and Computer Science
   Hobart and William Smith Colleges

   Fall, 2008.

   Instructor:  David J. Eck.

   Monday, Wednesday, Friday, 12:20 -- 1:15 PM.
   Room Stern 204.

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. We will use the Java programming language in some examples. Furthermore, there will be a few homework assignments that require writing programs in Java. However, for the most part, this is a mathematics course, and the majority of the assignments will be mathematical.

You do not need to purchase a textbook for the course. The textbook will be handed out in class. A copy is also available in PDF format on the Internet at http://math.hws.edu/FoundationsOfComputation. The text was written by Professors David Eck and Carol Critchlow. The book has 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 forms 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 artificial languages 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 truly understand computers without knowing something about the abstract machines covered in that chapter.

Homework Assignments

There will be weekly homework assignments, which will be collected and graded. Some of the assignments will involve writing computer programs, but this is not primarily a programming class, and none of the programming assignments will be very large or complex. The mathematical assignments will be similar to the end-of-section exercises in the textbook, but most will not be taken directly form the book. (I will be writing new exercises because the ones in the textbook have been around for several years.)

The assignments for each week will be collected the following week. I will usually hand out solutions to the homework at the same time that I collect the assignments. This means that, generally, assignments will not be accepted late.

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 mathematics problems. However, you should, in the end, write up your own solutions in your own words to be turned in. For programming assignments, you should work on your own unless the assignment tells you to do otherwise.

Tests

There will be three in-class tests, which will be given on Friday, September 26; Friday, October 24; and Monday, November 24. The final exam for the course will take place at the time scheduled by the Registrar's office: Thursday, December 18, 1:30--4:30 PM. 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%

I reserve the right to adjust your grade downwards if you miss more than a couple of classes without a good excuse. 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.

Office Hours, E-mail, and Web

My office is room 313 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. On most weekdays, I will be on campus at least between 10:00 AM and 3:00 PM (but I am less likely to be in on Thursday). I have class Monday, Wednesday, and Friday from 12:20 to 1:15 and from 3:00 to 3:55. My official office hours are 1:30 to 2:50 on Monday, Tuesday, Wednesday, and Friday. 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 am happy to 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_f08/. I will post weekly readings and assignments on that page.

Tentative Schedule

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

Dates Topic
Sept. 1, 3, 5 Propositional Logic and Logic Circuits.
Sept. 8, 10, 12 Predicate Logic.
Sept. 15, 17, 19 Deduction and Proof.
Sept. 22, 24, 26 Mathematical Induction and Recursion.
TEST, Friday, September 26.
Sept. 29; Oct. 1, 3 Sets and Operations on Sets.
Oct. 6, 8, 10 Functions.
Oct. 15, 17 Counting; Relations.
Fall Break, Monday, October 13.
Oct. 20, 22, 24 Formal Languages.
TEST, Friday, October 24.
Oct. 27, 29, 31 Regular Expressions and Automata.
Nov. 3, 5, 7 More on Automata and Languages.
Nov. 10, 12, 14 Context-free Grammars and BNF.
Nov. 17, 19, 21 Parsing and Parse Trees.
Nov. 24 Thanksgiving Break, November 26 -- 28.
TEST, Monday, November 24.
Dec. 1, 3, 5 Non-context-free Languages and General Grammars.
Dec. 8, 10, 12 Turing Machines and Computability.
Dec. 18 Final Exam: Thursday, December 18, 1:30--4:30 PM