CPSC 229, Foundations of Computation, Spring 2020

This course ended
on May 9, 2020

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

Homework
Homework 1 Due January 29	Homework 2 Due February 7	Homework 3 Due February 17	Homework 4 Due February 24
Homework 5	Lab/Homework 6	Homework 7	Homework 8
Homework 9	Homework 10	Final Exam

Ninth Week and Beyond...

Because of the COVID-19 pandemic, we are moving to entirely on-line teaching. The main hub for the course will be on Canvas. Students should check there for further updates and assignments.

See the syllabus revisions: Part 1 and Part 2.

Eighth Week: March 9, 11, and 13

The reading for the week is Section 3.3 from the textbook and a handout on regular expressions that was handed out in class on Friday. We will talk about this material in class on Monday, and you will need to be familiar with it before class on Wednesday.

On Wednesday, March 11, class will meet in the Rosenberg 009 computer lab. You will be working on a lab about regular expressions. That lab will also be Homework #6. It will be due after Spring break.

We will probably get a start on Section 3.4, Finite Automata, on Friday.

Seventh Week: March 2, 4, and 6

After finishing up a few points about infinity from Section 2.6, we will be ready to start Chapter 3 on Monday. This is the start of the second part of the course, where we will cover topics that are usually called "automata theory", "formal language theory", and "theory of computability." These topics are the basis of theoretical computer science. We will use material from the first part of the course — logic, functions, and sets — but we really be concerned with formal languages and automata, which provide very abstract models for programming languages and computers.

The reading for the week is Chapter 3, Sections 1 and 2. Section 2.1 introduces abstract "languages", and Section 2.2 covers the category of abstract languages known as regular languages.

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.