CPSC 229:
Foundations of Computation

   
   Department of Mathematics and Computer Science
   Hobart and William Smith Colleges

   Fall, 2015.

   Instructor:  David J. Eck.

   Monday, Wednesday, Friday, 12:20–1:15 PM.
   Room Eaton 111.

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, grammars, 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. 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.

There is too much material in the textbook to be covered in a one semester course. In order to allow sufficient time for the last three chapters, we will omit some of the material from Chapters 1 and 2. In particular, we will not cover recursive definitions (Section 1.10) or relations (Sections 2.7 and 2.8), and we will not cover all the details of proof (Sections 1.6 through 1.9) and functions (Sections 2.4 and 2.5).

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 from the book.

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 the following Wednesdays: September 23, October 21, and November 18. The final exam for the course will take place at the time scheduled by the Registrar's office: Tuesday, December 15, 7:00 -- 10:00 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.

Statement from the CTL

Disability Accommodations: If you are a student with a disability for which you may need accommodations, you should self-identify and register for services with the Coordinator of Disability Services at the Center for Teaching and Learning (CTL), and provide documentation of your disability. Disability related accommodations and services generally will not be provided until the registration and documentation process is complete. The guidelines for documenting disabilities can be found at the following website:

http://www.hws.edu/academics/ctl/disability_services.aspx

Please direct questions about this process or Disability Services at HWS to Administrative Coordinator, Jamie Slusser, (slusser@hws.edu, 781-3351) or Coordinator of Disability Services, David Silver at silver@hws.edu.

Office Hours, E-mail, and Web

My office is room 313 in Lansing Hall. My office phone extension is 3398. You are welcome to stop by my office anytime you can find me there. My regular office hours, when I am almost certain to be in my office, are:

       Monday,     11:15–12:10 
       Wednesday,  11:15–12:10
       Thursday,   1:00–3:00
       Friday,     10:10–11:05

However, I will generally be in my office Wednesday and Friday from 10:10 to 12:10, and Monday, Wednesday, and Friday from 1:30 to 3:00 or later. And I will often be on campus on Tuesday.

My e-mail address is eck@hws.edu.

There is a short Web page for this course at http://math.hws.edu/eck/cs229/index_f15.html. 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 Sections
Aug. 31; Sept. 2, 4 Propositional Logic and Logic Circuits. 1.1,1.2,1.3
Sept. 7, 10, 11 Predicate Logic; Deduction. 1.4,1.5
Sept. 14, 16, 18 Proof; Mathematical Induction. 1.6,1.7,1.8
Sept. 21, 23, 25 Recursion and Induction.
TEST, Wednesday, September 23. 		1.9
Sept. 28; 30; Oct. 2 Sets and Operations on Sets. 2.1,2.2,2.3
Oct. 5, 7, 9 Functions; Counting; Infinity. 2.4,2.6
Oct. 14, 16 Languages; Regular Expressions
Fall Break, Monday, October 12. 		3.1,3.2
Oct. 19, 21, 23 Regular Expressions on the Computer.
TEST, Wednesday, October 21. 		3.3
Oct. 26, 28, 30 Finite-state Automata. 3.4,3.5
Nov. 2, 4, 6 Regular and Non-regular Languages. 3.6,3.7
Nov. 9, 11, 13 Context-free Grammars and BNF. 4.1,4.2
Nov. 16, 18, 20 Parsing and Parse Trees.
TEST, Wednesday, November 18. 		4.3
Nov. 23 Pushdown Automata.
Thanksgiving Break, November 25—27. 		4.4
Nov. 30; Dec. 2, 4 Non-context-free Languages; General Grammars. 4.5,4.6
Dec. 7, 9, 11 Turing Machines and Computability. 5.1,5.2,5.3
Dec. 15 Final Exam: Tuesday, December 15, 7:00--10:00 PM