| This courses ended December 16, 2010 |
CPSC 229: Foundations of Computation
Department of Mathematics and Computer Science Hobart and William Smith Colleges Fall, 2010. Instructor: David J. Eck (eck@hws.edu) Monday, Wednesday, Friday, 3:00 -- 3:55 PM. Room Eaton 110. Course Handout: http://math.hws.edu/eck/courses/cpsc229_f10.html
Fifteenth Week and End Of Term: December 6, 8, 10
The final exam for this course is scheduled for Thursday, December 16, from 7:00 to 10:00 PM in our usual classroom. An information sheet about the final exam is available. You can also review the information sheets from the first test, the second test, and the third test.
The final week of the semester covers Turing machines and computability. The reading is all of Chapter 5, Sections 1 through 3.
Fourteenth Week: November 29; December 1 and 3
As we head towards the end of the semester, we will be finishing up Chapter 4 and moving on to Chapter 5 by Friday. The theme for this last part of the course is the nature of computation and its limits. This week, we will be looking in particular at general grammars (Section 4.6), and we will start in on Turing machines (Section 5.1).
Twelfth and Thiteenth Weeks: November 15, 17, 19, and 22
There is a test on Friday, November 19. For the rest of these two weeks, we will look at parse trees and parsing (Section 4.3) and the Pumping Lemma for context-free languages (Section 4.5). If we have time, we might look briefly at Pushdown Automata (Section 4.4). However, none of these topics will be covered in as much depth as in the textbook. There is no class on November 24 or 26 because of Thanksgiving break. After break, we will start Section 4.6, General Grammars.
Have a great Thanksgiving!
Eleventh Week: November 8, 10, 12
We finish up Chapter 3 this week and start Chapter 4. We will cover the Pumping Lemma and how to use it to show that a given language is not regular. Then we will move onto Context-Free Grammars and context-free languages. We will see that there are many languages that are context-free but are not regular.
There is a test scheduled for Friday of next week. (It was originally scheduled for Wednesday, but we agreed to move it.) An information sheet for the test is available.
Tenth Week: November 1, 3, 5
We will spend the week on DFAs and NFAs, Sections 3.4, 3.5, and starting 3.6. NFAs (Nondeterministic Finte Automata) will be introduced. We will see how to construct a DFA that accepts the same language as a given DFA, and how to construct an NFA that accepts the language generated by a given regular expression.
There is a lab and programming assignment due on Friday.
Ninth Week: October 25, 27, 29
We will finish up regular expressions and start in on DFAs (Deterministic Finite Automata). For regular expressions on the computer, you should read Section 3.3 as well as the handout. You should also read Section 3.4, which introduces DFAs.
On Wednesday, the class will meet for a computer lab in Lansing 310. The lab handout also includes some programming exercises about using regular expressions in Java. A sample program, GetWords.java, is available.
Eighth Week: October 18, 20, and 22
There is a test this week on Wednesday. A review sheet is available.
On Monday, after dealing with any questions about material that will be on the test, we will move on to Section 3.2, which introduces regular languages and regular expressions. By Friday, we should start Section 3.3, which covers practical regular expressions and their applications to computing and programming. There will be a handout about regular expressions on the computer.
Seventh Week: October 13 and 15
After tying up a few loose ends from Chapter 2, we will begin Chapter 3. Section 3.1 covers the basic ideas of formal languages: alphabets, strings, languages, and operations o languages. By Friday, we should start Section 3.2, which covers regular expressions and regular languages.
There is a test on Wednesday of next week, which will cover through Section 3.1. This includes the homework that is due next Monday.
Sixth Week: October 4, 6, and 8
We will finish with Chapter 2 this week -- however much of it we cover is all we will be doing. We will at least look at some of the basic material on functions (Section 2.4), and we will cover almost all of Section 2.6 on counting, cardinalities, infinity, and diagonal arguments.
Fifth Week: September 27 and 29; October 1
We begin Chapter 2 this week. We will cover as much of Chapter 2 as we can do this week and next week. After Fall Break, we will move on to Chapter 3, which is the beginning of material more directly relevant to computer science. The reading for this week is Sections 2.1, 2.2, and 2.3. These sections cover sets and set operations. Section 2.3 introduces Java bitwise operators, which can be used -- among other uses -- to implement sets of natural numbers.
The first programming assignment of the semester is about programming with sets in Java. It is due on October 8.
Fourth Week: September 20, 22, and 24
There is a test on Wednesday. An Information Sheet about the test is available.
On Monday, I will answer any questions about the test. After that, if there is any time, we will continue with Mathematical Induction (Sections 1.8 and 1.9). On Friday, we will definitely finish up Induction and Chapter 1. Note that we will not cover Section 1.10. If time permits, we might move on to Chapter 2 (Sets and Functions).
Because of the test, there is no new homework assignment this week.
Third Week: September 13, 15, and 17
We will spend the week learning about and doing proofs. A sheet of "Proof Moves" will be handed out, summarizing some of the techniques that can be applied to prove various types of statements. We will cover some general proof techniques, and then we will move on to proof by contradiction and (possibly by Friday) proof by mathematical induction. The reading for the week consists of Sections 1.6, 1.7, and beginning 1.8.
Reminder: There is a test coming up next week, on Wednesday. It will cover Chapter 1, Sections 1 through 7.
Second Week: September 6, 8, and 10
We continue with Chapter 1. We will cover Sections 1.4 and 1.5, and we will begin Section 1.6 by the end of the week. The material covered will include predicate logic, valid arguments, and formal proofs. By Friday, we will be ready to work on more informal mathematical proofs.
First Week: August 30; September 1 and 3
Printed copies of the textbook will be handed out on the first day of class.
The reading for the week is Chapter 1, Sections 1, 2, and 3. These sections cover propositional logic and their application to logic circuits. The first homework assignment will be handed out in class on Wednesday and is due on Wednesday of next week.