Grading: There will be one midterm exam (25%), a final exam (35%). 2 classworks (15% each), and 10 quizzes (1% each).
Quizzes: At least 10 quizzes, every Friday unless otherwise announced.
Classworks will be announced, we expect to hold 2 classworks total. Classworks will be open notes unless we switch to a full online schedule depending on the course of the pandemic.
Midterm and final exams are closed notes, closed book.
Passing Grade: No predetermined grade to pass the course.
FZ Policy: [(Classworks' Average x 0.3) + (Midterm x 0.25)] should be at least 18 (out of 55).
Makeup Policy: Medical report holders will be entitled for the midterm make up, and ONLY ONE classwork makeup in the last week of the semester. Classwork makeup will be comprehensive, and both midterm and classwork makeups will definitely be more difficult. We will give no makeups for the quizzes.
Week  Topic  Lecture Notes  LaTeX Source  Notes (tentative) 
1  Introduction & Finite Automata  0intro.pdf
intro
slides 
0intro.tar.gz  
2  Finite Automata  1dfa.pdf dfaMod.c 
1dfa.tar.gz  
3  Finite Automata  2nfa.pdf 
2nfa.tar.gz  
4  Regular expressions and languages  3re.pdf 
3re.tar.gz  
5  Contextfree grammars and languages  
6  Contextfree grammars and languages  4cfg.pdf  4cfg.tar.gz  
7  Contextfree grammars and languages  5pda.pdf 
5pda.tar.gz 
Classwork 1 
8  Pushdown automata  Midterm 

9  

10  Turing machines  6tm.pdf  6tm.tar.gz  
11  Decidability, Reducibility  


12  Complexity theory and NPcompleteness  7decidability.pdf 8reducibility.pdf 
7decidability.tar.gz 8reducibility.tar.gz 
Classwork 2 
13  Complexity theory and NPcompleteness  

14  Complexity theory and NPcompleteness  CookLevinTheorem.pdf 9complexity.pdf 
The following is on the cover pages of your midterm and final exams. Most students do not read this *valuable* information, but everyone SHOULD. These rules apply to classworks as well:
The rules 4 and 5 above point out the fact that this course is a FORMAL, THEORY course. All proofs should be presented as formal expressions, the same way discussed in class. Long paragraphs/sentences of trying to explain a possible answer does not mean that you will receive any credit. This is not a humanities course, do not write essays to answer the questions.
Let us reiterate