Starting the second week, the course will have an unusual lecture schedule. There will be two lectures each Monday, and two lectures each Wednesday. One lecture per day will take place as normal, at 9:00AM in 1109 SC. The second lecture will be held at 2:00PM in 1304 SC. You are not required to attend the extra lectures, but feel free to attend if able and ask questions.
All of the lectures will be recorded, and you are required to watch each of the lectures! (It's part of the homework.) Ideally, you should watch each lecture before the next scheduled lecture occurs; look at the Lecture # to see when. Note that the first week will not be recorded.
Since you are watching lectures at home, the homeworks will be somewhat easier. Instead of lecture on Tuesdays and Thursdays, there will be a Problem Solving Session (PSS) in which we work on the homework for the class. This will be somewhat similar to the 'sections' that usually accompany CS theory courses. In each PSS, you will work on and get answers to some of the problems that are due in the homework that week. As a result, there will be less homework problems that you need to tackle on your own.
Be careful not to fall too behind in lecture! The Summer course moves fast and CS373 usually requires a lot of time and work to understand. In particular, the Problem Solving Sessions will not be as useful to you if you are not up to date with the material!
The sections each week will cover different material as necessary.
HW: hw0(pdf,tex), hw1(pdf,tex), hw2(pdf,tex),hw3(pdf,tex), hw4(pdf,tex), hw5(pdf,tex)
Lectures: GNFA/Regex=regular notes, Suffix class definition correction, DFA minimization/Myhill Nerode notes, Pumping lemma game, Rice's theorem proof, Reduction proof outline
Exams: Sp11 Practice Midterm 1, Midterm 1 solutions, Fa10 Practice Midterm 2, Practice unrecognizable problems(solutions), Midterm 2 solutions, FA09 mock midterm 2 (w CFLs),FA09 midterm 2 (w CFLs), Sp10 mock final (solutions)
| Date | Lecture # | Lecture Topic | Resources | Assignments |
| Week 1 | ||||
| 6/13 Mon | 01 | Motivation and Problems | ||
| 6/14 Tue | 02 | Problems and languages, Finite states | ||
| 6/15 Wed | 03 | DFA formalism, finite languages are regular | HW0 assigned [tex] | |
| 6/16 Thu | 04 | DFA constructions, nondeterminism | ||
| 6/17 Fri | section | |||
| Week 2 | ||||
| 6/20 Mon | 05 | 9AM: NFA formalism | HW0 due, HW1 assigned [tex] | |
| 06 | 2PM: The power of NFAs: equivalence | |||
| 6/22 Wed | 07 | 9AM: Subset construction, NFA examples, finite is regular (revisited) | ||
| 08 | 2PM: Regular closure properties with NFAs | |||
| 6/24 Fri | section | HW1 due;
HW2 assigned [tex only] | ||
| Week 3 | ||||
| 6/27 Mon | 09 | 9AM: Regular Expressions | ||
| 10 | 2PM: Regex equivalence | [notes] | ||
| 6/29 Wed | 11 | 9AM: Homomorphism, Nonregularity, DFA structure: pumping lemma | ||
| 12 | 2PM: More pumping lemma | |||
| 7/01 Fri | section | HW2 due; HW1 corrections due | ||
| Week 4 | ||||
| 7/04 Mon | INDEPENDENCE DAY (NO CLASS) | |||
| 7/05 Tue | Midterm Review | |||
| 7/06 Wed | 9AM: MIDTERM 1 (in class) | |||
| 13 | 2PM: DFA structure: Myhill-Nerode theorem | |||
| 7/07 Thu | 14 | DFA minimization | [notes] | |
| 7/08 Fri | section | |||
| Week 5 | ||||
| 7/11 Mon | 15 | 9AM: Programs with Infinite memory, Turing machines | HW3 assigned [tex only], HW2 corrections due | |
| 16 | 2PM: TM Formalism, Decidability, Recognizability | |||
| 7/13 Wed | 17 | 9AM: Regular languages are decidable, TM Examples | ||
| 18 | 2PM: More TM examples, Church-Turing thesis, TM variants | |||
| 7/15 Fri | section | HW3 due; HW4 assigned [tex only] | ||
| Week 6 | ||||
| 7/18 Mon | 19 | 9AM: Nondeterminism, Countable sets, Undecidability | ||
| 20 | 2PM: Halting problem, Reductions for undecidability | |||
| 7/20 Wed | 21 | 9AM: Unrecognizability, Mapping reductions | ||
| 22 | 2PM: Mapping reduction examples, Rice's theorem | [notes] | ||
| 7/22 Fri | section | HW4 due; HW3 corrections due | ||
| Week 7 | ||||
| 7/25 Mon | 9AM: Midterm review | |||
| 23 | 2PM: Grammars, Chomsky Hierarchy | |||
| 7/26 Tue | MIDTERM 2 (in class) | |||
| 7/27 Wed | 24 | 9AM: Context free grammars | ||
| 25 | 2PM: Pumping lemma for CFLs | | ||
| 7/28 Thu | 26 | Normal Forms | HW5 assigned [tex only]
| |
| 7/29 Fri | section | HW4 corrections due | ||
| Week 8 | ||||
| 8/01 Mon | 27 | 9AM: Restricted infinite memory: Pushdown Automata | ||
| 28 | 2PM: PDA/CFG equivalence, CFLs are decidable | |||
| 8/03 Wed | 29 | 9AM: The end and more | ||
| 8/04 Thu | Final Review/Homework Solutions | HW5 due | ||
| 8/05 Fri | FINAL EXAM: 1:00-3:00 PM | |||