homework introduction syllabus textbook grading exams news excuses teaching staff


  Weeks
Date
 Topics   Sections
Homework Problems
  Extra Problems
1
Sep 6  Mathematical Preliminaries
1.1 - 1.5
 Homework #1.  
2
Sep 13  DFA and NFA
2.1, 2.5
 2.1,2.4,2.10,2.11,3.1,3.3, 4.1, 5.1, 5.2  2.6, 3.6, 4.2, 5.2
3
Sep 20  Regular and Nonregular Languages
3.1 - 3.4
 1.1, 1.4, 2.1- 2.3, 3.1, 4.1, 4.3  1.3, 2.7, 3.2, 4.2
4
Sep 27  Properies of Regular Languages
4.1 - 4.4
 1.1,1.2,1.4,2.2,2.3,2.5,3.2,3.4,4.1,4.2  1.3, 2.11, 4.3
5
Oct 4  Contex-Free Languages
5.1, 5.2
 1.1-1.3,1.5,1.7,2.1,2.2  1.8, 2.3
6
Oct 11  Applications of CFL
5.3, 5.4
 3.2, 3.3, 3.4, 4.1, 4.5, 4.7  4.4
7
Oct 18  Pushdown Automata  6.1 - 6.4  1.1, 2.1, 2.2, 2.6, 3.2, 3.5, 4.1 - 4.3  2.3, 3.7, 4.4
8
Oct 25  Midterm Exam
   
9
Nov 1  Properties of CFL
7.1 - 7.3
 1.2 - 1.6, 1.11, 1.12, 2.1, 2.2, 3.2, 3.4  1.7, 2.3, 3.3
10
Nov 8  Turing Machines
8.1 - 8.3
 1.1, 2.1 - 2.3, 3.1, 3.2  
11
Nov 15  Extensions of the Basic TMs
8.4, 8.5
 4.1 - 4.6, 5.1  4.9, 4.10, 5.2
12
Nov 22  Undecidability
9.1 - 9.4
 1.1 - 1.3, 2.1 - 2.4, 3.2 - 3.6, 4.1, 4.2  3.8
13
Nov 29  P and NP classes
10.1 - 3
 1.1 - 1.3, 1.5, 1.7, 2.1, 2.2, 3.1, 3.3  
14
Dec 6  Final Exam