## CPSC 229: Foundations of Computation

Department of Mathematics and Computer Science Hobart and William Smith Colleges Spring 2020. Instructor: David J. Eck (eck@hws.edu) Syllabus: http://math.hws.edu/eck/courses/cpsc229_s20.html Textbook PDF: Foundations of Computation, by Carol Critchlow and David Eck Monday, Wednesday, Friday, 12:15–1:15 PM Room Gulick 2001. Office Hours: MWF 9:45–10:45 AM Tuesday 11:00–12:00 (I am available at other times. See my complete schedule.)

Homework | |||

Homework 1 Due January 29 Answers |
Homework 2 Due February 7 Answers |
Homework 3 Due February 17 Answers |
Homework 4 Due February 24 |

### Sixth Week: February 24, 26, and 28

There is a test this Wednesday, February 26. A study guide was handed out in class on Friday. Also available:

Sample Answers to Sample Test Questions

Aside from the test, we will be looking at Section 2.6, about counting and infinity.

### Fifth Week: February 17, 19, and 21

Last week, we only just started Chapter 2 by looking at some basic notations and definitions for sets. We will continue with Chapter 2 and hopefully complete Sections 1 to 4 this week. Topics include set operations, the Boolean algebra of sets, the bitwise operations in Java and how they relate to sets, and functions. It is possible that we will not get to Section 2.4 (functions) until Monday. After that, we will skip Section 2.5.

There is a test coming up next week on Wednesday, February 26. It will cover Chapter 1 and Chapter 2, Sections 2.1 to 2.4.

### Fourth Week: February 10, 12, and 14

We did not make it to Section 1.8 last week, so we will start this week with that section, covering mathematical induction. We will also look at how induction relates to recursion, which is covered in Section 1.9. We will not cover Section 1.10 at all. We will move on to Chapter 2, hopefully by Wednesday. You should read Sections 2.1 and 2.2, which cover sets and operations on sets. Note that in Chapter 2, we will only cover Sections 1 through and 6, and we will not cover everything in those sections.

The due date for Homework 3 has been moved from February 14 to Monday, February 17.

### Third Week: February 3, 5, and 7

It turns out that we finished Section 1.5 last week, so we will move on directly to the topic of mathematical proof. We will cover Sections 1.6 and 1.7 and at least get a start on Section 1.8. We will be talking about proof techniques, including how to prove "for all" and "there exists" statement, proof by contradiction, and mathematical induction.

### Second Week: January 27, 29, and 31

The reading for the week is Chapter 1, Sections 3, 4, and hopefully starting 5. Section 1.3 covers logic circuits, which are an essential topic in computing, but not an important part of this class. We will do some basic examples, and you really only need to read the first four pages of the section. Section 1.4 covers predicate logic, including the "quantifiers" for-all and there-exists. Section 1.5 introduces the idea of formal proofs in propositional logic. I do not expect to finish Section 1.5 this week, if we get to it at all.

### First Week: January 22 and 24

Welcome to the course!

You should download the PDF of the textbook and start reading Chapter One. We will cover Sections 1.1 and 1.2 from that chapter this week. These sections introduce propositional logic and Boolean algebra.

You should also carefully read the syllabus for the course!

The PDF version of the textbook is free. You will not need a printed copy, but if you would like to have one, you can order a copy from lulu.com at this link.