|
This course ended December 16, 2015 |
CPSC 229: Foundations of Computation
Department of Mathematics and Computer Science
Hobart and William Smith Colleges
Fall, 2015.
Instructor: David J. Eck (eck@hws.edu)
Monday, Wednesday, Friday, 12:20 -- 1:15 PM.
Room Eaton 111.
Course Handout: http://math.hws.edu/eck/courses/cpsc229_f15.html
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 at the first class meeting, and it is due on Wednesday of next week. (It is already posted at the top of this page.)
Second Week: September 7, 9, and 11
The reading for the week is Chapter 1, Sections 4 and 5. We move on this week from propositional logic to predicate logic. We will spend Monday and Wednesday on Section 4, which covers predicate logic. On Friday, we will look at the ideas of formal proof and valid arguments.
Sample answers for homework #1 are available. Note that there is also a link to the answers in the table at the top of this page. A link to sample answers will be added to that table after each homework assignment is collected.
Third Week: September 14, 16, and 18
There is a test coming up next week, on Wednesday, September 23. It will cover Sections 1.1 through 1.7. For this week, you should read Sections 1.6 and 1.7. We should begin Section 1.8 on Friday, but Section 1.8 will not be on the test. Homework #3 will cover sections 1.6 and 1.7. Because of the test, it will be due on Monday of next week.
A table of "Proof Moves" will be handed out in class on Wednesday. It summarizes the proof techniques that are discussed in Sections 1.6 and 1.7.
Fourth Week: September 21, 23, and 26
There is a test this week, on Wednesday, September 23. The test covers Sections 1.1 to 1.7. A review sheet was handed out in class last Friday.
On Monday, I will answer any questions on the material that will be covered on the test. In any remaining time, we will start on Section 1.8, which covers mathematical induction. We will continue with mathematical induction on Friday.
Next week, we will move on to Chapter 2. Although I might say a few words about Sections 1.9 and 1.10 in class, you will not be responsible for that material.
There is a short homework assignment on Section 1.8, which is due Wednesday of next week.
Fifth Week: September 28 and 30; October 2
On Monday, I will have just a little more to say about mathematical induction. That will finish as much as we are going to do in Chapter 1. We will start Chapter 2 on Monday.
We will spend the next two weeks on topics from Chapter 2. This week, we will concentrate on sets, which are covered in Sections 2.1, 2.2, and 2.3. You should learn all the basic definitions in Section 2.1. We will cover only a few formulas from the "Boolean algebra of sets" in Section 2.2. Section 2.3 talks about programming with sets using Java's bitwise operations. A couple of the homework exercises for this week will be programming problems based on that material.
Sixth Week: October 5, 7, and 9
The reading for the week is Chapter 2, Sections 4 and 6. We will only do parts of Section 2.4, and we will be moving quickly on from Chapter 2 to Chapter 3 by the end of the week. We will start Section 3.1 on Friday.
Topics for this week include the definition of a function from one set to another set, the idea of one-to-one correspondence and cardinality of a set, and infinite sets. We will see that there are different "sizes" of infinity. The main distinction for us is between countably infinite sets and uncountably infinite sets.
Seventh Week: October 14 and 16
There is no class on Monday, October 12, because of Spring break.
The reading for the week is sections 3.1 and 3.2, which cover formal languages and regular expressions.
Programming Assignment 1 is due on Friday, October 16. I will expect to be able to collect it for grading on Saturday morning.
Homework 6 will be distributed in class on Wednesday. It is due in class next Monday, October 19.
The second test is coming up on Wednesday of next week, covering mathematical induction, sets, functions, infinity, languages, and regular expressions.
Eighth Week: October 19, 21, and 23
There is a test on Wednesday, October 21. A study guide was handed out in class on Friday, October 16.
We finished the material that will be covered on the test last Friday. On Monday of this week, I will answer questions about the test. We will then begin talking about regular expressions as they are actually used on computers. This is the topic of Section 3.3, and there will be a handout on Monday with more detail. You should read both before the lab on Friday.
On Friday, the class will meet for a lab session in Rosenberg 009 to do some practical work with regular expressions. There will be a computer assignment that you will work on during class, and there will be a programming assignment that will be due in a week or two. The programming assignment will be about using regular expressions in Java.
The instructions for the lab are available.
Ninth Week: October 26, 28, and 30
This week we turn from formal languages to abstract machines. In particular, we will be working this week with "finite automata." The reading for the week is Sections 3.4 and 3.5.
The lab and programming assignment from October 23 are due at the end of this week. You should copy your programs to the homework folder in /classes/cs229 by the end of the day on Friday. I will collect and print the programs on Saturday morning. You can turn in a hard copy of your answers to the lab exercises in class on Friday, or you can submit them in a text document to the homework folder, along with your programs.
Tenth Week: November 2, 4, and 6
We will continue studying regular expressions and finite automata. After doing some more examples of converting NFAs to DFAs, we will cover the algorithm for converting a regular expression into an NFA. We will note, without going through the construction in detail, that a DFA can be converted to a regular expression. Thus, regular expressions, DFAs, and NFAs all define the same class of languages. After that, we will turn to the Pumping Lemma for Regular Languages, which provides a way to prove that a language is not regular. That will complete Chapter 3. The reading for the week is Sections 3.6 and 3.7. It is possible that we be able to start Chapter 4 on Friday.
Eleventh Week: November 9, 11, and 13
We begin a new chapter and a new topic this week: Context-Free Grammars (CFGs). The reading for the week is Chapter 4, Sections 1 and 2. We might cover part of Section 3 on Friday.
There is a test coming up on Wednesday of next week. Because of the test, this week's homework is due next Monday, November 16 Tuesday, November 18 at 2:00 PM.
Twelfth Week: November 16, 18, and 20
There is a test on Wednesday, November 18. A study guite is available.
Homework 9 can be turned in any time up until 2:00 PM on Tuesday. Sample solutions will be published on the web at that time. Note: There was an error on the original homework sheet: The third rule for grammar c) was stated as S --> SbA, but it should have been S --> bSA. This has been corrected in the homework sheet that is lined to this page.
In lecture this week,w e will continue with Chapter 4. We will cover a selection of topics from Sections 4.3, 4.4, and 4.5. However, we will skip a lot of the material in those three sections so that we can move quickly to the things that will occupy us for the reset of the semester: general grammars, Turning machines, and computability.
Thirteenth Week: November 23
Monday is the only class day this week. Happy Thanksgiving!
On Monday, we will cover pushdown automata, which are discussed in the book in Section 4.4. We will only cover the basic idea. We will not use the formal definition, and we will not cover deterministic pushdown automata.
Note that from Section 4.3, we covered only parse trees and left derivations. We did not cover LL(1) or LR(1) languages, and we did not talk about parsing methods.
From Section 4.5, you will only be responsible for a few facts, including: Some examples of languages that are not context-free; the fact that the intersection of two context-free languages is not necessarily context-free; the fact that the complement of a context-free language is not necessarily context-free, and the fact that the intersection of a regular language and a context-free language is context-free.
Fourteenth Week: November 30; December 2 and 4
We will finish Chapter 4 and begin Chapter 5 this week. The reading is Sections 4.6 and 5.1.
We are beginning to think about the concept of "computability" in general. Section 4.6 covers general grammars, while Section 5.1 introduces Turing Machines. General grammars and Turing machines are two very different ways of expressing computations, but we will see that they are in some sense equally powerful. And, in fact, no more general concept of computability is known (although the status of quantum computing is not yet completely clear).
Fifteenth Week: December 7, 9, and 11
In this last week of classes, we will consider the general idea of computability. We will define the class of recursive languages and the class of recursively enumerable languages using Turing Machines. Then, we ask whether there are recursively enumerable languages that are not recursive. To answer that question, we use a numbering of all (up to equivalence) Turing Machines that can work with languages over the language {0,1}. If the TM's are numbered To, T1, T2, ..., then the language K = {n | Tn halts on input n} is recursively enumerable but not recursive. This fact is due to the famous result known as the Halting Problem. We should complete this material on Wednesday and have Friday for review.
The reading for the week is the rest of Chapter 5, that is, Sections 5.2 and 5.3.
Final Exam: December 15
The final exam is Tuesday, December 15, at 7:00 PM in our regular classroom. A study guide for the exam is available and was handed out in class on December 9.
Office Hours for Exam Week:
Monday, December 14: 11:00 AM – 3:00 PM
Tuesday, December 15: 11:00 AM – 3:00 PM
Thursday, December 17: 11:00 AM – 3:00 PM
Friday, December 18: 11:00 AM – 1:15 PM