CPSC 229:
Foundations of Computation

   
   Department of Mathematics and Computer Science
   Hobart and William Smith Colleges

   Sprng 2021.

   Instructor:  David J. Eck.

   Monday, Wednesday, Friday, 12:10–1:10 PM.
   Room Coxe 008.

Everything on this syllabus is tentative until the start of classes. Even after classes start, changes and adaptation might be necessary because of the pandemic. However, we will try to cover all of the material listed in the syllabus, no mater what form the class takes.

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.

The text was written by David Eck and a now-retired professor, Carol Critchlow. A copy is available in PDF format at

http://math.hws.edu/eck/cs229/s21/FoundationsOfComputation.pdf

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 that are not part of CPSC 229. 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 fifth 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 computer science 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 parts of 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.

Homework assignments will be turned in online. Instructions for turning in computer programs will be included in the assignment. For other assignments, you will turn in your work in Canvas in the form of a PDF file. You will probably want to scan handwritten solutions into a PDF, but it is also possible to use a word processor or LaTeX to write your solutions.

The assignments for each week will be collected the following week. The general policy is that homework will not be accepted late, but you can appeal for an exception with sufficient cause. Under no circumstances will homework be accepted after sample solutions are posted.

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. You should never turn in a duplicate of someone else's work. I reserve the right to ask you to come to my office hours to explain your work.

Tests

I am hoping to be able to give tests in person and on paper. If that becomes impossible, the tests will either be given online through Canvas, at the scheduled time, or they will be changed to take-home tests of some kind. (A take-home test gives you more time to work on the test and has a different kind of question than would be given on a timed test.)

There will be two in-class tests, which will be given on Friday, March 5, and on Wednesday, April 14. The final exam for the course will take place at the time scheduled by the Registrar's office: Wednesday, May 5, 1:30 PM. The final exam will cover material from the entire term, with some emphasis on material that is covered after the second test.

Grading

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

            First Test:        20%
            Second Test:       20%
            Final Exam:        20%
            Assignments:       40%

Final grades might be "curved" to some extent, but cutoffs for letter grades will not be lower than the following: 90-100: A; 80-89: B; 65-79: C; 55-64: D; 0-54: F. Grades near a cutoff get a + or -.

Attendance Policy

I assume that you understand the importance of attending class, and you should always plan to be in class, if possible. However, because of the pandemic, I will not take attendance, and attendance is not required. In fact, if you are sick, you should not be in class. Technology permitting, classes will be streamed on Zoom and also recorded and posted on Canvas.

About Office Hours

The Colleges' administration advises against having in-person meetings with students in Faculty offices. Since my office is large, however, it might be possible for me to meet there with one person at a time. (This is assuming that classes don't go entirely remote.) However, in-person meetings would be by appointment only, since we can't have groups of people waiting in the hall. It might also be possible to meet somewhere other than my office. If you would like to try to schedule an in-person meeting, you should contact me.

I will schedule a few open, drop-in office hours on Zoom. I will also set up times for individual or group appointments on Zoom. Appointments will be made using the Calendar feature in Canvas. Details will be announced, and Zoom links for office hours will be posted on Canvas.

Of course, email is always a good way to contact me. My email address is eck@hws.edu. I welcome comments and questions by email, and I will usually respond to them fairly quickly.

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, 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: 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

Tentative Schedule

Here is a tentative weekly schedule of topics for the course. We will try to keep approximately to this schedule, but the actual reading assignmantes will be posted each week on the course web page, http://math.hws.edu/eck/cs229/

Dates Topics Sections
Jan. 25, 27, 29 Propositional Logic. 1.1,1.2
Feb. 1, 3, 5 Logic Circuits; Predicate Logic. 1.3,1.4,1.5
Feb. 8, 10, 12 Proof; Mathematical Induction. 1.6,1.7,1.8
Feb. 15, 17, 19 Recursion and Induction; Sets.
 1.9,2.1,2.2
Feb. 22, 24, 26 More on Sets and Functions. 2.3,2.4
Mar. 1, 3, 5 Counting and Infinity.
Test on Friday, March 5. 		2.6
Mar. 8, 10, 12 Languages; Regular Expressions. 3.1,3.2
Mar. 15, 17, 19 Practical Regular Expressions; FSAs.
 3.3,3.4
Mar. 22, 24, 26 More on Finite State Machines. 3.5,3.6
Mar. 29, 31; Apr. 2 Pumping Lemma; Context-free Grammars. 3.7,4.1
Apr. 5, 7, 9 Parsing; Pushdown Automata. 4.3,4.4
Apr. 12, 14, 16 Non-context-free Grammars.
Test on Wednesday, April 14 		4.5
Apr. 19, 21, 23 General Grammars; Turing Machines. 4.6,5.1
Apr. 26, 28, 30 Computability.
 5.2,5,3
May 5 Final Exam: Wednesday, May 5, 1:30 PM