| General Information |
You are not allowed to use material outside of the prescribed textbook and our handouts in class to solve the homeworks or exams. That especially means solutions from previous quarters and solutions posted on the web from other universities, but also includes looking up answers in other textbooks. (If you happen to be browsing another book to enrich your understanding, and run across one a solution to one of our homework problems, please let Prof. Dill know.)
It is ok to receive hints and debugging help from the TAs, Prof. Dill, or other students, or to have general discussions about problem solving strategies and write-ups, but you must indicate clearly on your assignment any assistance you received. Any assistance received (both from human and from inanimate sources) that is not given proper citation may be considered a violation of the Honor Code.
In any case, you are responsible for understanding and being able to
explain all of the statements in your assignments and examinations.
Solutions must be written up independently of
other students.
Assigned sections should be read (at least quickly) before the lecture.
| Course Calendar |
| Lec# | Date | Description |
| 1 | Tue, Sep 22 | Read all of Chapter 1 to review discrete math basics and make
sure you know their notation. Part of the lecture focuses on Section
1.5.
Lecture: Content and motivation for the course, administrative issues, and basic concepts: alphabets, strings, languages, problems. |
| 2 | Thu, Sep 24 | Read sections 2.2 and 2.3.1-2.3.4. Sections
2.1 and 2.4 are worth reading
for applications of finite automata, but not essential for the
lecture. Lecture topics: Deterministic and non-deterministic finite automata (DFAs and NFAs) |
| 3 | Tue, Sep 29 | Read section 2.5, 3.1 Lecture: NFAs with epsilon transitions, regular expression syntax and semantics HW1 Assigned |
| 4 | Thu, Oct 1 | Read section 3.2 Lecture: Equivalence of regular expressions and finite automata |
| 5 | Tue, Oct 6 | Read sections 4.1, 4.2 Lecture: Proofs of non-regularity: Pumping lemma and closure properties. HW1 Due HW2 assigned |
| 6 | Thu, Oct 8 | Read sections 4.3, 4.4 Lecture: Decision properties of regular languages Equivalence & minimization |
| 7 | Tue, Oct 13 | Read sections 8.2, 8.3, and 8.4 (8.1 is optional) Lecture: Turing Machines, TM Programming tricks HW 2 Due HW 3 Assigned |
| 8 | Thu, Oct 15 | Read sections 8.5, 8.6, 9.1, and 9.3 Lecture: Restricted TMs, recursively enumerable vs. recursive problems, undecidability. |
| 9 | Tue, Oct 20 | HW 3 Due HW 4 Assigned Read section 9.3 Lecture: More undecidable problems. |
| 10 | Thu, Oct 22 | Read notes on web page, if I can get them posted in time. Lecture: Regular languages and Presburger arithmetic |
| 11 | Tue, Oct 27 | HW4 Due No new homework this week -- prepare for midterm Read sections 10.1, 10.2 (but not 10.2.3), and 10.3 Lecture: P and NP, SAT, CSAT, and 3SAT. |
| 12 | Thu, Oct 29 | Read section 10.4. Lecture: More NP-complete problems. |
| MIDTERM | Tue, Nov 3 | Midterm covers up through HW 4 HW 5 Assigned |
| 13 | Thu, Nov 5 | Read sections 5.1, 5.2, 5.4, 7.1, and 7.2 Lecture: Context-free grammars, context-free languages, and ambiguity |
| 14 | Tue, Nov 10 | HW5 Due HW6 Assigned Read sections 6.1, 6.2, 6.3 (except 6.3.2, which is optional), and 6.4 Lecture: Push-down automata |
| 15 | Thu, Nov 12 | Read sections 7.3 and 7.4 Lecture: Closure and decision properties of CFLs. |
| 16 | Tue, Nov 17 | Read: 11.1-11.3 HW6 due HW7 Assigned Lecture: Co-NP and PSPACE |
| 17 | Thu, Nov 19 | Read subsection 10.2.3 Cook's Theorem |
| Freedom! | Tues/Thu, Nov24/Nov 26 | Thanksgiving Recess |
| 18 | Tue, Dec 1 | HW7 Due More decidability |
| 19 | Thu, Dec 3 | Review for final |
| Final | Wednesday, Dec 9, 2009. | 12:15 PM -- 3:15 PM |