Schedule

This table will be updated to include important lecture materials as they become available. For the other resources, please check out the sharif courseware webpage.

Part 0: Introduction
DateLecturerTopicSlidesNotes
1403/07/01 (Sun) Moeini Jam
  • Introduction
 [Lecture Set 0]

Part 1: Set Theory
DateLecturerTopicSlidesNotes
1403/07/03 (Tues) Moeini Jam
  • Preliminaries: Set Theory
[Lecture Set 1]
1403/07/08 (Sun) Moeini Jam
  • Preliminaries: Set Theory

Part 2: Regular Languages
DateLecturerTopicSlidesNotes
1403/07/10 (Tues) Moeini Jam
  • Deterministic Finite Automata (DFA), Regular Languages
 [Lecture Set 2]
1403/07/15 (Sun) Moeini Jam
  • Operations on Regular Languages, Proof by Construction, Proving Correctness
1403/07/17 (Tues) Moeini Jam
  • Non-deterministic (NFA) and Alternating Finite Automata (AFA)
 [Lecture Set 3]
1403/07/22 (Sun) Moeini Jam
  • Regular Expressions, Kleene’s Theorem and its Proof
1403/07/24 (Tues) Moeini Jam
  • The Myhill-Nerode Theorem, Hopcroft's Minimization Algorithm
 [Lecture Set 4]
1403/07/29 (Sun) Moeini Jam
  • Proof of The Myhill-Nerode Theorem
1403/08/01 (Tues) Moeini Jam
  • Pumping Lemma for Regular Languages, Proving Irregularity with Closure Properties

Part 3: Context-free Languages
DateLecturerTopicSlidesNotes
1403/08/06 (Sun) Moeini Jam
  • Grammars, Context-free Languages, Derivation Trees
 [Lecture Set 5]
1403/08/08 (Tues) Moeini Jam
  • Grammars with Ambiguity, Proof of Unambiguity, Chomsky Normal Form
1403/08/13 (Sun) Moeini Jam
  • CYK Procedure, Non-deterministic Pushdown Automata (NPDA)
 [Lecture Set 6]
1403/08/15 (Tues) Moeini Jam
  • Instantaneous Description, PDAs and CFGs Equivalence
1403/08/20 (Sun) Moeini Jam
  • Pumping Lemma for CFLs, Closure Properties, Deterministic PDA

Part 4: Turing-recognizable (Recursively Enumerable) Languages
DateLecturerTopicSlidesNotes
1403/08/22 (Tues) Moeini Jam
  • Turing-recognizable Languages
 [Lecture Set 7]
1403/08/27 (Sun) Moeini Jam
  • Operations on Turing Machines
1403/08/29 (Tues) Moeini Jam
  • Multi-tape and Non-deterministic TMs, Classification of Problems
1403/09/04 (Sun) Moeini Jam
  • The Definition of Algorithms, The Church-Turing Thesis, Universal TM
1403/09/06 (Tues) Moeini Jam
  • Turing-decidable Languages, Transducer Turing Machines
 [Lecture Set 8]
1403/09/11 (Sun) Exam
  • Midterm Exam
1403/09/13 (Tues) Moeini Jam
  • Computable Functions, Reduction, Decidable Problems
1403/09/18 (Sun) Moeini Jam
  • Undecidable Languages, Proof of Undecidability

Part 5: Context-Sensitive Languages
DateLecturerTopicSlidesNotes
1403/09/20 (Tues) Moeini Jam
  • Linear-Bounded Automata (LBA) and Context-sensitive Languages
 [Lecture Set 9]
1403/09/25 (Sun) Moeini Jam
  • Decidable, Undecidable and Open Problems regarding LBAs

Part 6: Complexity Theory, Supplementary Subjects
DateLecturerTopicSlidesNotes
1403/09/27 (Tues) Moeini Jam
  • Complexity Theory, Time Complexity
 [Lecture Set 10]
1403/10/02 (Sun) Moeini Jam
  • The Classes P and NP, The P vs. NP Question
1403/10/04 (Tues) Moeini Jam
  • NP-Completeness, SAT Problem, The Cook–Levin Theorem
1403/10/09 (Sun) Moeini Jam
  • SAT Solvers (Optional)
1403/10/30 (Sun) Exam
  • Final Exam