## CPSC 229:

Foundations of ComputationDepartment of Mathematics and Computer Science Hobart and William Smith Colleges Fall, 2000. Instructor: David J. Eck. Monday, Wednesday, Friday, 1:55 -- 2:50. Room Lansing 300.

## 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.You do not need to purchase a textbook for the course. The textbook will be handed out in class in several sections. The first three chapters will be available on the first day of class. I suggest that you buy a three-ring binder for the textbook and for other handouts. The text will have seven chapters. Here, very briefly, is a tentative schedule for the course:

- Chapter 1:
Logic.(5 classes)- Chapter 2:
Sets, Functions, and Relations.(6 classes)- Chapter 3:
Proof and Induction.(5 classes)- Chapter 4:
Languages and Regular Languages.(5 classes)- Chapter 5:
Finite Automata.(6 classes)- Chapter 6:
Grammars.(5 classes)- Chapter 7:
Turing Machines and Computability.(6 classes)This schedule allows for three in-class tests and a day of review at the end of the term.

## 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, but this is not a programming class and there will be no major programming assignments. Almost all the assignments will be taken from the end-of-section exercises in the textbook.

The assignments for each week will be collected on the following Monday. Generally, assignments will not be accepted late. However, under certain circumstances, such as illness, I will consider accepting an assignment on the Tuesday following the Monday 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 text, whether or not they are assigned as homework.

Please note that for all homework exercises, you are required to

show your workandexplain 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 Wednesday, September 20; Wednesday, October 18; and Wednesday, November 15. The final exam for the course will take place at the time scheduled by the Registrar's office: Thursday, December 14, at 1:30 PM. The final exam will be in our regular classroom, Lansing 300. 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 grade for the course will be computed as follows:

First Test: 15% Second Test: 15% Third Test: 15% Assignments: 30% Final Exam: 25%

## Attendence Policy

This is a college-level class, which moves very quickly. You will almost surely do poorly in the class if you don't come to class, do the work, and keep up with the material. I assume that you understand this. I do not take attendence and I do not enforce an attendence policy.

## 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. I have scheduled office hours for the following times:

- Monday, 1:00--1:50
- Tuesday, 1:00--3:30
- Wednesday, 1:00--1:50
- Friday, 11:00--12:00
It is possible that I might have to make some changes to this schedule. If so, I will announce the changes in class and on my office door.

Office hours are times when I promise to try my best to be in my office. I do not 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 the day I receive them.

You'l find a small Web page for this course at http://math.hws.edu/eck/cs229.html. I will post weekly readings and assignments on that page. You can find them there in case you miss them in class.

## First Assignment

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:

- From Chapter 1, Section 1: 4abd, 6, 8, 9, 10
- From Chapter 1, Section 2: 3, 7acf, 9, 10
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.