CPSC 229: Foundations of Computation
Department of Mathematics and Computer Science Hobart and William Smith Colleges Fall, 2007. Instructor: David J. Eck (eck@hws.edu) Monday, Wednesday, Friday, 10:10 -- 11:05. Room Napier 202. Course Handout: http://math.hws.edu/eck/courses/cpsc229_f07.html Textbook: http://math.hws.edu/FoundationsOfComputation
Fifteenth Week and End-of-Term: December 3, 5, 7, and 12
In the final week of the term, we will cover topics from Chapter 5, on Turing Machines and computability. Since we are running out of time, we will not do anything with Turing Machines except to learn about what they are and how they "compute." We will than discuss the general topic of computability, and will use Turing Machines to define a non-recursively-enumerable language. The final homework, Homework #10, is due on Wednesday, December 5.
The final exam for this course is on Wednesday, December 12, at 1:30 PM. There is an information sheet for the exam. That sheet also has a list of my office hours for the remainder of the semester.
Fourteenth Week: November 26, 28, and 30
We will work quickly through the major points of Chapter 4 this week, omitting most of the proofs. Here is an outline of the reading for the week:
- Section 4.1: We will cover this section in full, except for the proof that regular languages are context free and the proofs that certain grammars generate certain languages.
- Section 4.3: Only the idea of parse trees will be covered from this section. We will not cover parsing or LL(1) and LR(1) grammars.
- Section 4.4: We will cover the Pumping Lemma for Context-Free Languages and some of its applications, but not its proof.
- Section 4.5: We will cover this entirely.
Here is the final homework assignment that will be collected and graded:
Please note that the final exam for this course is scheduled for Wednesday, December 12, at 1:30 PM.
Thirteenth Week: November 19
There is a test on Monday, November 19. An information sheet is available
There is no class on Wednesday or Friday of this week, because of Thanksgiving break.
Twelfth Week: November 12, 14, and 16
We should finish Chapter 3 on Monday, when we will cover the Pumping Lemma and use it to show that certain languages are not regular. On Wednesday we will begin Chapter 4 and the study of context free grammars. There is a homework assignment due on Friday:
Don't forget that there is a test next Monday.
Eleventh Week: November 5, 7, and 9
This week we will continue the study of regular expressions, DFAs, and NFAs. Each of these defines a class of languages. Our goal is to show that, in fact, they all define exactly the same class of languages, namely the regular languages. We will show how to convert an NFA into an equivalent DFA and how to convert a regular expression into an NFA. We will discuss the problem of converting a DFA into a regular expression, but will not give a complete algorithm for doing so. By the end of the week, we might get started on the "pumping lemma," which provides a way to prove that certain specific languages are not regular. The reading is Sections 3.5 and 3.6 and possibly beginning Section 3.7.
Here is the homework assignment that is due this Friday:
Tenth Week: October 29 and 31; November 2
We will continue with Chapter 3 this week. After finishing up Section 3.2 (regular expressions), we will move on to Section 3.4 (deterministic finite automata). Hopefully, we will get started on Section 3.5 (non-deterministic finite automata) by Friday. One of our major goals is to understand how regular expressions, DFAs, and NFAs all describe the same class of langauges. Homework #7 is due on Friday, and a new homework assignment will be available at that time.
Ninth Week: October 22, 24, and 26
There is a test on Monday. On Wednesday and Friday, we will be working on regular expressions, which are covered in Sections 3.2 and 3.3 of the textbook. On Friday, we will probably meet in the Math/CS computer lab to work on regular expressions and to begin a programming assignment on using regular expressions in Java.
Advising week is coming up soon. To provide you with more information about some of the courses that will be offered next term, several faculty members will do short presentations about the courses that they will teach. The presentation session is scheduled for 7:00 to 8:00 PM on Thursday, October 25, in Napier 201 (with refreshments at 6:45).
Here is the homework assignment:
On Friday, we will meat in the Math/CS computer lab on the third floor of Lansing hall, and you will start on the computer/programming part of the homework. You will need the following handout on regular expressions:
Regular Expressions on the Computer
Eighth Week: October 17 and 19
There is no class on Monday of this week, because of Fall break. At the end of last week, we just got started on Section 3.1. On Wednesday, we will finish that section. On Friday, we will review for the the test. If there is time, we might begin Section 3.2.
The second test of the term is next Monday, October 22. Here is an information sheet for the test:
Information sheet for the second test
Homework #6 is due on Friday. Because of the test, there is no new homework due next week.
Seventh Week: October 8, 10, and 12
This week, we will complete all the material that we will do from Chapter 2. After finishing up functions on Monday, we will move on to counting and infinity. By the end of the week, we should have started Chapter 3, which coveres formal languages, regular expressions, and finite automato.
Originally, a test was scheduled for Friday, October 19. However, we have decided to move that test to Monday, October 22. The next homework will be due on the 19-th:
Next week, there is no class on Monday, because of Fall break.
Sixth Week: October 1, 3, and 5
We will spend the week working with sets, functions, and counting. The material is from Chapter 2, Sections 1 through 4 and Section 6. We will finish these sections by early next week. We will not cover everything in these sections, and we will skip Chapter 2, Sections 3, 7, and 8 entirely so that we can move on quickly to Chapter 3 next week.
The homework for this week includes a Java programming exercise in which you are asked to use the standard class java.util.BitSet to implement the Sieve of Erastothenes. Here's the homework:
Fifth Week: September 24, 26, and 28
We will cover proof by mathematical induction this week, and will look briefly at its application to proving the correctness of recursive algorithms. The reading is Chapter 1, Sections 8 and 9, but we will cover this material rather lightly. In particular, we will not do anything with summation notation, and we will not look at any binary tree algorithms. I will not have anything at all to say about Chapter 1, Section 10. By the end of the week, we should start Chapter 2, on sets and functions. Here is the homework for this week:
Fourth Week: September 17, 19, and 21
There is a test this week on Friday, September 21. The test covers Chapter 1, Sections 1 through 7.
Information Sheet for the First Test
We will continue our study of mathematical proof this week, starting with proof by contradiction (Section 1.7.) Although this will finish up the material that will be on Friday's test, we will go on to proof by induction (Section 1.8) on Wednesday.
There is a short homework assignment due on Wednesday:
Third Week: Setember 10, 12, and 14
Because we never got to Section 1.5 last week, the homework from last week will be collected on Friday instead of on Wednesday.
This week, We will be working on Chapter 1, Sections 5 and 6. While Section 5 looks at the idea and techniques of formal proof, Section 6 introduces informal proofs as they are actually written in mathematics.
Don't forget that the first test is coming up at the end of next week. And remember that there is a department picnic on Thursday at 5:30.
Second Week: Setember 3, 5, and 7
The reading for the second week of the term is Chapter 1, Sections 4 and 5. Section 4 introduces predicate logic, which uses predicates such as R(x) [with a meaning such as "x is red"] and quantifiers for all x, R(x) and there exists x, R(x) [with meaning such as "all x are red" and "there is an x that is red"]. In Section 5, we study formal deduction and the idea of valid arguments. An "argument" is a claim that some statement follows logically from a set of hypotheses. The argument is valid if the claim is true. One way to show the validity of an argument is with a "formal proof." Next week, we'll start looking at the more informal proofs that are used in mathematics.
Homework #2, due September 12 (PDF format)
First Week: August 27, 29, and 31
We begin the course with propositional logic and its relation to logic circuits, a topic that you might have already encountered in CPSC 120. Propositional logic studies the basic Boolean operators AND, OR, and NOT. These mathematical operators correspond to certain simple electronic circuits that are the basic building blocks of computers, and the rules of propositional logic determine how the simple building blocks are connected together into logic circuits that can perform complex computation. The reading for the week is Chapter 1, Sections 1, 2, and 3.
Homework #1, due September 5 (PDF format)