CPSC 229: Foundations of Computation, Spring 2018

This course ended on
May 5, 2018

CPSC 229: Foundations of Computation

      Department of Mathematics and Computer Science
      Hobart and William Smith Colleges

      Spring 2018.

      Instructor:  David J. Eck  (eck@hws.edu)

      Monday, Wednesday, Friday, 9:05–10:00 AM
            Room Gulick 2001

      Course Handout:  http://math.hws.edu/eck/courses/cpsc229_s18.html

Homework
Homework 1 Due January 26	Homework 2 Due February 2	Homework 3 Due February 9	Homework 4 Due February 16
Homework 5 Due March 5	Homework 6 Due March 9	Homework 7 Due March 28	Homework 8 Due April 6
Homework 9 Due April 20		TM Lab and Homework 10 Due April 27

Fifteenth week: April 30

The final exam is at 7:00 PM on Saturday, May 5. A study guide was handed out in class. We will spend Monday on questions about the exam.

Here are my answers to the sample questions number 1 through 13 from the final exam study quide.

My slightly revised office hours for this week are as follows (although I will actually be availalbe at other times as well):

      Wednesday, May 2:   2:00 to 4:00
      Thursday, May 3:    1:00 to 2:30 and 3:00 to 3:50
      Friday, May 4:      1:00 to 4:20
      Saturday, May 5:   11:00 to 2:00
      Sunday, May 6:     12:00 to 1:20

Fourteenth week: April 23, 25, and 27

In the last full week of classes, we will finish up Chapter 5, on Turing machines and computability. We will look at two new types of language: the recursive languages and the recursively enumerable languages (which are that same as the Turing-decidable and the Turing-acceptable languages). We will see that not all problems can be solved by computation. In particular, we will end the semester by proving the computational unsolvability of the Halting Problem.

Thirteenth week: April 16, 18. and 20

Class on Friday of this week will be in Rosenberg 009 for a lab on Turing Machines.

The reading for the week is Section 5.1, which introduces Turing machines.

Twelfth week: April 9, 11, and 13

There is a test this week, on Wednesday, April 11. A study guide was handed out in class on Friday, along with some practice problems. Also available are sample answers to the practice problems.

Aside from the test, we will spend as much time as necessary for review on Monday. We will then continue with the topic of general grammars, Section 4.6, which we began briefly last Friday.

Eleventh week: April 2, 4 and 6

The reading for the week is Sections 4.3, 4.4, and 4.5. Section 4.3 covers parsing and parse trees, including LL(1) and LR(1) grammars. However, we will not cover LR(1) grammars or the "shift-reduce" parsing method that goes along with them. Section 4.4 covers pushdown automata, and Section 4.5 covers the Pumping Lemma for Context-free Languages. Again, we will not cover these sections in full detail. It is possible that we might begin Section 4.6, on general grammars, before the end of the week.

There is a test next Wednesday, April 11, covering Section 3.1 through 4.3.

Tenth week: March 26, 28, and 30

We move on to Chapter 4 this week. Chapter 4 covers formal grammars. Like regular expressions, grammars let you generate and recognize languages, but they are more powerful. The chapter covers two types of grammars: context-free grammars (CFGs) and general grammars. We begin this week with context-free grammars. We will cover at least Sections 4.1 and 4.2 this week. Section 4.1 covers the basics of CFGs. Section 4.2 is about an equivalent notation known as Backus-Naur Form (BNF). BNF is often used to specify the context-free syntax of programming languages. We should also be able to start Section 4.3, which covers parsing, by Friday.

For more discussion of BNF and expression parsing, with working Java examples, see Section 9.5 in my Java textbook. In particular, SimpleParser2.java implements the example from Friday's class.

Ninth week: March 12, 14, and 16

Next week is Spring break! Have fun!

The goal is to finish Chapter 3 this week, so that we come back from break and start right into Chapter 4. The reading is Sections 3.6 and 3.7. In 3.6, we see how to find an NFA that recognizes the language generated by a given regular expression. At that point, you should believe that regular expressions, NFAs, and DFAs are equivalent in that they all define the same set of languages. We will also be able to show that the union of two regular languages, the complement of a regular language, and the reverse of a regular language are all regular. In Section 3.7, we cover the Pumping Lemma for regular languages, and we use it to show that certain languages are not regular.

Eighth week: March 5, 7, and 9

Our next topic is Finite State Automata (FSAs). We will be looking both Deterministic Finite Automata (DFAs) and Nondeterministic Finite Automata (NFAs) and the relationship between them. The reading is Sections 3.4 and 3.5.

Seventh week: February 26 and 28; March 2

We will work on regular languages and regular expressions this week. The reading is Sections 3.2 and 3.3 plus a handout with more details about practical use of regular expressions on the computer. On Friday, the class will meet in Rosenberg 009 for a lab on regular expressions.

Sixth week: February 19, 21, 23

There is a test on Wednesday, February 21. A study guide was handed out in class last Friday.

My sample answers to the study guide questions are available.

We will review for the test on Monday, and might go on to new material on Monday if there is time. We have finished everything we are going to do from Chapters 1 and 2, and we will be moving on to Chapter 3, which languages, regular languages, regular expressions, and finite automata. The reading for the week is Section 3.1, which defines formal languages and basic operations on languages.

Fifth week: February 12, 14, and 16

We have already gotten a start on Section 2.3, which covers the bitwise logical and bit shift operators in Java. It also covers the idea that an N-bit binary number corresponds to a subset of {N-1, N-2, ..., 2, 1, 0} and how this relates to the bitwise operators. We will continue this on Monday.

We will also cover parts of Sections 2.4 (functions) and 2.6 (counting and infinity). We will not cover all of the material in those sections — but it certainly wouldn't hurt to read them!

There will be a test on material from chapters 1 and 2 next Wednesday, February 21. After the test, we will be moving on to Chapter 3 and to things that are more directly relevant to computer science.

Fourth week: February 5, 7, and 9

We will finish with mathematical induction. Last week, we only got started on Section 1.8. We will finish that section by covering summation notation and the second form of induction ("strong induction"). We will also look at how this all applies to proving the correctness of recursive algorithms, which is covered in Section 1.9. After that, we will move on to Chapter 2. We will go over the basic material on sets and set operations, from Sections 2.1 and 2.2.

Third week: January 29 and 31; February 2

The reading for the week is Sections 1.6, 1.7, and 1.8. These sections are about "mathematical proof," that is, the more informal (though still rigorous) version of proof that is used in mathematics. Section 1.6 covers proof in general, while 1.7 and 1.8 cover specific types of proof: proof by contradiction and proof by induction.

Here is the handout on "Proof Moves" from Wednesday's class.

Second week: January 22, 24, and 25

We will cover Sections 1.3, 1.4, and 1.5 from the textbook, although we are actually doing them in the order 1.5, 1.4, 1.3. These sections, cover logic circuits and their relationship to propositional logic; predicate logic and the quantifiers "for all" and "there exists"; and logical deduction and formal proofs.

I have written up a solution to the nine-coins problem that we discussed in class on Friday.

First week: January 17 and 19

Welcome to the course!

The textbook for this course is Foundations of Computation. You do not need to purchase a copy of the book; copies will be handed out on the first day of class. A PDF version is available on-line. The reading for the first week of the course is Sections 1.1 and 1.2.