Assignments
This page will be updated as we progress through the course.
Reading
Please read the assigned reading before the class date listed.
| 8/23 |
Sipser Chapter 0. This chapter introduces you to the topic and provides a review of math topics that will used in this course. As you read, please make notes of things that you feel less comfortable with. |
| 8/26 |
Sipser Chapter 1 intro and section 1.1 |
| 8/28 |
Sipser Chapter 1 section 1.2 |
| 9/2 |
Sipser Chapter 1 section 1.3 |
| 9/6 |
Sipser Chapter 1 section 1.4 |
| 9/11 |
Sipser Chapter 2 section 2.1 |
| 9/16 |
Sipser Chapter 2 section 2.2 |
| 9/27 |
Sipser Chapter 3 section 3.1 |
| 10/2 |
Sipser Chapter 3 section 3.2 |
| 10/16 |
Sipser Chapter 4 |
| 10/21 |
Sipser Chapter 5 intro and section 5.1 |
| 10/23 |
Sipser section 5.3 |
| 10/25 |
Sipser section 7.1 |
| 11/4 |
Sipser section 7.2 |
| 11/6 |
Sipser section 7.3 |
| 11/8 |
Sipser section 7.4 |
Projects
Homework
| 8/26 |
Sipser exercises: 0.1 parts a and d; 0.2 parts a, b, and e; 0.3 all parts; 0.8 |
| 8/28 |
First Finite Automata, download JFLAP |
| 8/30 |
Nondeterministic Finite Automata |
| 9/2 |
Sipser exercise 1.16 part b. Perform the conversion by hand and turn in a hard copy of the state diagram in class |
| 9/4 |
Regular Expressions |
| 9/9 |
Pumping Lemma |
| 9/16 |
Sipser exercises: 2.1, 2.3, 2.4 parts a, b, and c, 2.14 |
| 9/18 |
Pushdown Automata |
| 9/30 |
Sipser exercises: 3.1, 3.2, and 3.5 |
| 10/21 |
Turing Machines and Graphs |
| 10/23 |
Proof of Undecidability |
| 11/4 |
Time Complexity |