| Week | Topics covered | Notes from Class, and Announcements | Material, Homework, Assignments | |
|---|---|---|---|---|
| Week 1: Jan 7-9 | Course Administrivia; What is a computer; brief overview of the course |
Jan 7: Intro; Jan 7: Review; Lec Jan 9: Finite Automata intro Lec Jan 9: Sets closed under an operation solutions to recursive definitions And we started on the next set of slides, to be posted later. | Read Chapter 0. Homework: 0.1 c; 0.2 b,e,f; 0.3 e; 0.4; 0.5, 0.6 a-c;, 0.7 a-c; 0.8; 0.9; 11 b. | |
| Week 2: Jan 14-16 | Finite Automata: DFAs and NFAs. Regular operations on languages |
Tutorial Jan 14: recursive definition concat Tutorial Jan 14: DFAs, Sample problems Lec Jan 14: Defn Computation -- FAs Lec Jan 14: NFA marked up version Lec Jan 16: closure of RL under union, concat, *; intro to r.e.'s (and marked up) |
Assignment 1 Due Jan 21 at beginning of the tutorial. (Note: the Assignment says Jan 20 midnight, but it will be accepted without penalty till your tutorial the next day) | |
| Week 3: Jan 21-23 | Closure of RL under ⋅, ∪, *. Introducing regular expressions. |
Lec Jan 21: r.e.'s, FAs, algorithms
(and marked up version) Tut Jan 21: r.e.'s, FAs Pumping Lemma |
Do Excercises 1.9 and 1.10, and 1.14(b), 1.16, and 1.17, 1.18. Pp58-66 of the text are relevant. | |
| Week 4: Jan 28-30 | Pumping Lemma to prove that a language is not regular. Using closure theorems to help prove a language is not regular. |
Tutorial: Pumping Lemma
Lec Jan 28: Pumping Lemma more examples Lec Jan 28: Pumping Lemma: Primes |
Assignment 2
and
solutions
Due Feb 3 (Tuesday) at midnight SNOWDAY Due Thurs in class. 10% penalty for handing it in on 1 day late. 20% for 2 days late. 100% penalty after that. Homework is the questions in the Tutorial: Pumping Lemma, and questions 1.19, 1.20 in the text. |
|
| Week 5: Feb6 (Snowday Feb 4) | Introduction to Context Free Languages: Context-free Grammars. Ambiguous grammars. |
Context-Free Languages: Intro More CFLs Chomsky Normal Form CFL -- proving correct for a language; Intro to PDAs |
||
| Week 6: Feb 11-13 |
CFG: Proving that a given grammar generates a particular language.
Intro to PDAs |
CFG Correctness; PDA intro
A sample test on Regular languages and further FAs for practicing conversion and the Solutions A sample test on CFLs, which covers some material that won't be on the test -- Do 2 a-b, 3, 4, 5, 6, 7. Solutions to be published after the tutorial. Sample Test 2 Solutions Pre-Quiz Tutorial on Pumping Lemma |
Pumping Lemma Quiz Feb 13. 15 minutes in class. | |
| Week 7: Feb 18-20 | Study Days | |||
| Week 8: Feb 25-27 |
Tue: Proving a language is not Context-Free Thu: Midterm 1 |
Chomsky Normal Form PDAs Parsers Bottom Up Parsers Non-CF languages |
||
| Week 9: Mar 4-6 | Countably infinite sets; Uncountability. The rockinest proof you ever did see. Intro to Turing Machines |
First Tutorial problems on counting Countability of infinite sets Tutorial: Countably infinite sets Intro to Turing Machines |
Assignment 3 Due Tue March 18, and the Solutions . |
|
| Week 10: Mar 11-13 | Turing Machines, cont'd. |
TMs, transducers, multitape, nondeterministic TMs: determinism; Universal TM TMs: Enumerator TM |
Tutorial homework: Enumeration Problems, and Tutorial Homework: Give transition diagrams for TMs that:
|
|
| Week 11: Mar 18-20 | TMs: non-determinism, Universal TM, Enumerator TM, Simulating a real computer. |
Tut: Decidable, Recognizable Decidability Undecidability |
Assignment 4 Due April 1 Assignment 4 Hints Solutions A4 |
|
| Week 12: Mar 25-27 | Tue: Proving languages are undecidable or unrecognizable
Tutorial Undecidability Questions Theorem 4.22 More undecidability Reduction Techniques Decidability Problems (Rich) |
|||
| Week 13: Apr 1-3 |
Tue: April 1 Complexity cont'd. |
Complexity Tue tutorial: A decidability problem and some graph algorithm problems Thu: April 3 Midterm 2 (Solutions); Sample Test and Solutions |
Assignment 5 to appear here, due April 11. To be returned to you on April 14 (if you submit hardcopies, you must pick them up from 3:30-4:45 Mon April 14, or make an arrangement for Tue April 15.) | |
| Week 14: Apr 8-10 |
Tue: Complexity Theory cont'd
Thurs: 15 minute quiz on NP and NP-completeness (Solutions. |
Tutorial problems on SAT, 3SAT 3SAT reduces to CLIQUE Poly Time Reductions Poly time Hamilton path/cycle problems |
Assignment 5, and
Solutions
|
|
| Exam Week: Apr 14-18 |
April 14 3:30: Office Hour in 315/218 (maybe in a classroom) April 15 noon to 1:00: Office Hour in 315/218 April 16 9-12: Exam |
Practice Final Practice Final solutions Exam Topics BunnyHop Complexity HamPath is NPc | ||