|
The course described on this page ended December 18, 2008 |
CPSC 229: Foundations of Computation
Department of Mathematics and Computer Science Hobart and William Smith Colleges Fall, 2008. Instructor: David J. Eck (eck@hws.edu) Monday, Wednesday, Friday, 12:20 -- 1:15 PM. Room Stern 204. Course Handout: http://math.hws.edu/eck/courses/cpsc229_f08.html Textbook: http://math.hws.edu/FoundationsOfComputation
Final Exam: December 18
The final exam for this course takes place at 1:30 PM on Thursday, December 18. An information sheet is available.
Week 15: December 8, 10, and 12
For the last week of classes, we will continue to discuss Turing Machines and computability. The reading is Chapter 5, Sections 2 and 3.
The final homework assignment, Assignment 9, is due on Wednesday.
Week 14: December 1, 3, and 5
For the last two weeks of the course, we will be taking a look at the general theory of computing and computability. We will start by looking at general grammars. Although these are similar to context-free grammars, they actually represent a form of computation that is equivalent to a computer. This will only become clear after we study Turing machines and computability in Chapter 5.
The reading for the week is Sections 4.5 and 5.1.
Week 13: November 24
There is a test on Monday, which will cover Chapter 3, Sections 3 through 7 and Chapter 4, Sections 1 through 4. An information sheet is available for the test.
There is no class on Wednesday or Friday because of the holiday. Happy Thanksgiving!
Week 12: November 17, 19, and 21
We will continue with Chapter 4 this week. We will cover Sections 4.2 through 4.4. However, form Section 4.3, we will certainly skip LR parsing and will probably skip LL parsing. The main thing that you need to know from that section is parse trees. In Section 4.4, we will not do the proof of the Pumping Lemma for Context-Free Languages, but we will cover the statement of the Lemma and its applications.
Assignment 8 is due on Friday.
Week 11: November 10, 12, and 14
We will finish Chapter 3 this week with the Pumping Lemma for Regular Languages and the proof that certain languages, such as {anbn | n is an integer}, are not regular. Then we will begin Chapter 4 and Context-Free Grammars (CFGs). A CFG is another way of specifying a language. CFGs are more powerful than regular expressions, and many languages that are not regular can be specified by CFGs.
Assignment 7 is due on Friday.
Week 10: November 3, 5, and 7
We will continue with Chapter 3 this week, covering Sections 3.5 and 3.6, and possibly starting Section 3.7. We will be looking at non-deterministic finite-state automata and showing that they are actually equivalent to DFAs.
Assignment 6 is due on Friday.
Week 9: October 27, 29, and 31
On Monday, October 27, class will meet in the Math/CS computer lab in Lansing 310 to work on this assignment:
This assignment is due next Monday, November 3. (There will be another, regular homework assignment this week, which will be due on the following Wednesday or Friday.)
The reading for the week is Sections 3.3, 3.4, and 3.5 in the textbook. Section 3.3 covers material for the computer lab, which is also covered in more detail in the handout about regular expressions on the computer. In Section 3.4 and Section 3.5, we begin looking at "automata" and the languages that they define. I don't expect that we will actually finish Section 3.5 until next Monday.
Week 8: October 20, 22, and 24
There is a test this Friday, October 24. An information sheet about the test is available.
We will cover Section 3.2 this week. This section defines regular expressions and how they are used to specify languages. If we have time, we might start Section 3.3, which discusses regular expressions on the computer. Homework 5 is due on Wednesday.
There will be a handout on regular expressions on the computer. Information from this handout will be used in a computer lab next week.
Week 7: October 15 and 17
There is no class on Monday of this week because of Spring break.
After finishing up a few loose ends about functions, we move on to Chapter 3. This week, we cover Section 3.1, which introduces a lot of basic definitions and notations concerning formal languages. Remember that the second test is coming up next week, on Friday, October 24. Here is the homework for the week:
Week 6: October 6, 8, and 10
The reading for the week is Section 2.4 and Section 2.6. We will do only the basic definitions from Section 2.4 (ordered pair, cross product, function, and the definition of a function as a set of ordered pairs). From Section 2.6, we will concentrate mostly on infinite sets, countability, and uncountability, but basic results on cardinality of finite sets are also important.
Week 5: September 29; October 1 and 3
There is a test on Monday of this week. After that, we will continue on the topic of sets. You should read Sections 2.1, 2.2, and 2.3. However, we will cover 2.2 and 2.3 rather lightly. In particular, we won't do a lot with the Boolean algebra of sets.
In addition to the normal homework, there is a programming assignment this week. On Friday, class will meet in the computer lab, Lansing 310, and you will have a chance then to start work on the programs. The programs cover two Java classes that represent sets, BitSet and HashSet. Sample programs that use these classes, BitSetSample and HashSetSample, will be handed out in class.
Programming Assignment 1, Due October 10.
Week 4: September 22, 24, and 26
Although a test was originally scheduled for Friday, we have moved that test to Monday of next week. The test will cover Chapter 1, Sections 1 through 9. We will finish up that material in class by Wednesday. After that, we will go on to Chapter 2, but anything that we cover from Chapter 2 will not be on the test.
Because of the test, no homework will be due next week.
Week 3: September 15, 17, and 19
This week will be about mathematical proof. Compared to formal proofs, mathematical proofs are less structured. They are generally written in English prose (plus mathematical notation), and they leave out steps that are considered ``obvious.'' But, in theory, it should be possible to convert any valid mathematical proof into a formal proof. We will look at various proof techniques, and will introduce some mathematical objects to practice them on. We will cover Sections 1.6 and 1.7 and get a start on Section 1.8.
Here is the homework for the week:
Week 2: September 8, 10, and 12
We move on to two more aspects of formal logic this week: predicate logic and formal proofs. The reading is Chapter 1, Sections 4 and 5. Here is the homework for the week, which is due next Wednesday:
Week 1: September 1, 3, and 5
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. Here is a link to a PDF file containing the assignment: