CPSC 229:
Foundations of Computation

   
   Department of Mathematics and Computer Science
   Hobart and William Smith Colleges

   Sprng 2018.

   Instructor:  David J. Eck.

   Monday, Wednesday, Friday, 12:15–1:15 PM.
   Room Gulick 2001.

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 formal 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. A copy is available in PDF format 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 abstract 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 Chapter 1 and a good deal of Chapter 2.

Homework Assignments

There will be weekly homework assignments, which will be collected and graded. A few 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. 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. It should go without saying that you need to do the reading assignments from the book, but you can only really 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 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 assignments. However, you must fully understand the work that you turn in, and you should always, in the end, write up your own solutions in your own words. I reserve the right to ask you to come to my office hours to explain your work or re-do it on my board.

Tests

There will be two in-class tests, which will be given on Wednesday, February 26, and on Wednesday, April 15. The final exam for the course will take place at the time scheduled by the Registrar's office: Saturday, May 9, at 8:30 AM. The final exam will cover material from the entire term, with some emphasis on material that is covered after the second in-class test.

No Technology During Lecture!

This is a computer science course, but that doesn't mean that it is OK to use a computer or cell phone during lecture. Use of a laptop, cell phone, or other device is not allowed during lecture. (The only exception is if you have a verified medical reason to take class notes on a computer.) For note taking, you should use paper.

There is substantial research showing that taking notes on paper can improve retention of the material, compared to note-taking on computer. My real advice is to take notes in outline form, noting down important ideas and examples, and to make a more formal copy of the notes after class, filling in any missing details. There is also research showing that the multitasking that you are likely to engage in if you have a computer open in front of you is detrimental to learning.

Grading

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

            First Test:        18%
            Second Test:       18%
            Assignments:       40%
            Final Exam:        24%

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 for this course, an A corresponds to 90–100%, B to 80–89%, C to 68–79%, D to 55–67%, and F to 0–54%. Grades near the endpoints of a range get a plus or minus.

Statements from the Center for Teaching and Learning

At Hobart and William Smith Colleges, we encourage you to learn collaboratively and to seek the resources that will enable you to succeed. The Center for Teaching and Learning (CTL) is one of those resources: CTL programs and staff help you engage with your learning, accomplish the tasks before you, enhance your thinking and skills, and empower you to do your best. Resources at CTL are many: Teaching Fellows provide content support in 12 departments, Study Mentors help you manage your time and responsibilities, Writing Fellows help you think well on paper, Q Fellows support you in courses that require math, and professional staff help you assess academic needs.

Disability Accommodations: If you are a student with a disability for which you may need accommodations, you should self-identify, provide appropriate documentation of your disability, and register for services with Disability Services at the Center for Teaching and Learning (CTL). 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 Christen Davis, Coordinator of Disability Services, at ctl@hws.edu or x 3351.

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. Here are my tentative regular office hours but note that I am often available outside these times and that your office visits are certainly not restricted to my regular office hours!

         MWF 9:45–10:45 AM
         Tuesday 11:00‐12:00

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

There is a Web page for this course at http://math.hws.edu/eck/cs229/index_s20.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 Topics Sections
Jan. 22, 24 Propositional Logic. 1.1,1.2
Jan. 27, 29, 31 Logic Circuits; Predicate Logic. 1.3,1.4,1.5
Feb. 3, 5, 7 Proof; Mathematical Induction. 1.6,1.7,1.8
Feb. 10, 12, 14 Recursion and Induction; Sets.
 1.9,2.1,2.2
Feb. 17, 19, 21 More on Sets and Functions. 2.3,2.4
Feb. 24, 26, 28 Counting and Infinity.
Test on Wednesday, Feb. 26. 		2.6
Mar. 2, 4, 6 Languages; Regular Expressions 3.1,3.2
Mar. 9, 11, 13 Practical Regular Expressions; FSAs.
 3.3,3.4
Spring Break, March 14–22
Mar. 23, 25, 27 More on Finite State Machines. 3.5,3.6
Mar. 30; Apr. 1, 3 Pumping Lemma; Context-free Grammars. 3.7,4.1
Apr. 6, 8, 10 Parsing; Pushdown Automata. 4.3,4.4
Apr. 13, 15, 17 Non-context-free Grammars.
Test on Wednesday, Apr. 15 		4.5
Apr. 20, 22, 24 General Grammars; Turing Machines. 4.6,5.1
Apr. 27, 29; May 1 Computability.
 5.2,5,3
May 4 Wrap-up and Review.  
May 9 Final Exam: Saturday, May 9, 8:30 AM