| This course ended on May 5, 2021 |
CPSC 229: Foundations of Computation
Department of Mathematics and Computer Science Hobart and William Smith Colleges Spring 2021. Instructor: David J. Eck (eck@hws.edu) Syllabus: http://math.hws.edu/eck/courses/cpsc229_s21.html Textbook PDF: Foundations of Computation, by Carol Critchlow and David Eck Monday, Wednesday, Friday, 12:10–1:10 PM Room Coxe 8.
| Homework and Answers to Tests | |||
| Homework 1 Due February 3 Answers |
Homework 2 Due February 10 Answers |
Homework 3 Due February 17 Answers |
Homework 4 Due February 24 Answers |
| Homework 5 Due March 3 Answers |
Sample Answers for First Test |
Homework 6 Due March 17 Answers |
Homework 7 Due March 24 Answers |
| Homework 8 Due March 31 Answers |
Homework 9 Due April 12 Answers |
Sample Answers for Second Test |
Homework 10 Due May 1 Answers |
Final Exam: Wednesday, May 5
The final exam for this course takes place at 1:30 on Wednesday, May 5. A study guide is available:
Fourteenth Week: April 26, 28, and 30
The reading for the last week of the semester is Sections 5.2 and 5.3, which cover general questions of computability, including The Church-Turing Thesis and the unsolvability of the Halting Problem.
Homework 10 is due by noon on Saturday, May 1 and will not be accepted late.
Thirteenth Week: April 19, 21, and 23
We started looking at general grammars, Section 4.6, last Friday. We will continue with general grammars on Monday. After that, we will be moving on to Turing machines, Section 5.1.
Twelfth Week: April 12, 14, and 16
There is test on Wednesday, April 14. Click here for the study guide
We will review for the test on Monday, and will go over some of the problems from the study guide. On Friday, we should start Section 4.6, which covers general grammars.
Homework 9 is due on Monday this week. It can be turned in late until noon on Sunday, April 18, but it would be a good idea to get it done before the test. There will be no new assignment this week.
Eleventh Week: April 5, 7, and 9
The reading for the week is Sections 4.3 and 4.4, which cover parsing, parse trees, and pushdown automata. We will, however, not cover LR(1) parsing from Section 4.3, and we will not be putting much emphasis on pushdown automata.
There is a test next week, on April 14, which will cover Chapter 3 and Sections 4.1 through 4.3. Homework 9 is due on Monday, April 12. The next homework assignment will be available some time after the test.
Tenth Week: March 29 and 31; April 2
The reading for the week is Sections 3.7, 4.1, and 4.2, although we probably need to continue with 4.2 next week. Section 3.7 covers the Pumping Lemma for Regular Languages, which can be used to prove that certain languages are not regular. Section 4.1 introduces our next category of language, context-free languages, which are defined by context-free grammars. Context-free languages can be used to specify the basic syntax of most programming languages (but not all common syntax rules). Section 4.2 covers BNF, a notation equivalent to context-free grammars which is often used for programming languages.
Homework 8 is due as usual by midnight on Wednesday for full credit. However, it can be turned in late until class time on Monday, April 5, with a 10% penalty. The next homework assignment will not be available until April 5 or later.
Ninth Week: March 22, 24, and 26
The reading for the week is Sections 3.5 and 3.6. We will cover Nondeterministic Finite-State Automata and the relationship between finite automata and regular languages. It turns out that regular expressions, DFAs, and NFAs all define the same category of languages.
Eighth Week: March 15, 17, and 19
We continue with Chapter 3. The reading for the week includes Section 3.3, which covers practical regular expressions, and Section 3.4, which introduces DFAs (Deterministic Finite-State Automata). Also included in the reading for the week is a web page about practical regular expressions. The new assignment this week will include some computer work with regular expression.
Seventh Week: March 6, 8, and 10
We move on to Chapter 3 this week. Chapter 3 starts with the general idea of a formal language, then covers regular expressions, finite automata, and the relationship between them. This is a major turning point in the course; we have finished with the purely mathematical part and are beginning that part about theoretical computer science. The reading for the week is Sections 3.1 and 3.2.
Sample answers for the first test are available.
There was no new assignment last week, and no work is due this week. The last time for turning in Homework 5 late was noon on Sunday, March 7.
Sixth Week: March 1, 3, and 5
There is a test on Friday, March 5. A study guide is available.
We will cover Section 2.6 this week, which covers counting, infinity, and countable and uncountable sets. However, this material is not on the test.
Homework 5 is due on Wednesday. Because of the test, there will not be a new homework assignment this week.
Fifth Week: February 22, 24, and 26
We will continue with Chapter 2, covering sets and functions. The reading for the week is Sections 2.2, 2.3, and 2.4. Looking ahead, note that the only other section that we will cover from Chapter 2 will be Section 2.6.
Fourth Week: February 15, 17, and 19
We did not get to Section 1.8 last week, so that section is first up on Monday. It covers a proof technique called mathematical induction. The reading for the week also includes Section 1.9 and Section 2.1. Section 1.9 talks about using induction to prove the correctness of recursive algorithms. Since not everyone in the class has worked with recursive programs, this is not something that I will ask you to do on homework or tests. However, we will also look at some other examples of proving program correctness.
We will then skip Section 1.10 and move on to Chapter 2, which covers sets and functions. Section 2.1 covers the basics of sets and set notation. Note that we will be skipping large parts of this chapter.
Third Week: February 8, 10, and 12
The reading for the week is Sections 1.6, 1.7, and 1.8. The topic is mathematical proof, including various proof techniques such as direct proof, counterexample, proof by contradiction, and induction. At the beginning of the week, we still need to spend some time on formal proof (Section 1.5), and it is likely that we will still be working on induction (Section 1.8) early next week.
Homework 2 is due by the end of the day on Wednesday. It can be turned in up until noon on Saturday, but if it is turned in after midnight on Wednesday without a good reason, there will be a 10% lateness penality.
Second Week: February 1, 3, and 5
The reading for the week is Sections 1.3, 1.4, and 1.5. We have already started 1.3, which covers logic circuits, and we will not spend much more time on that. Section 1.4 covers predicate logic, and Section 1.5 covers logical deduction. These are important topics that will take some time to cover, but hopefully we will get through them by the end of the week.
The first homework is due before midnight on Wednesday, but it will be accepted late until Saturday morning. Since this is the first assignment, there will be no penalty for turning it in late, but starting with the second assignment, there will be a 10% penalty for work turned in late, unless there is some good reason for it being late.
First Week: January 25, 27, and 29
Welcome to the course!
You should download the PDF of the textbook (or read it in your web browser), 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.
The first homework will be due Wednesday of next week. You will need to submit your solutions in PDF form. If you do not know how to scan your work to PDF, see these instructions.