Topic outline

  • General Information

    Course Outline

    The course deals with fundamental questions of computer science:

    • What is a computer?
    • What can computers do (and what can they not do)?
    • Why are some problems computationally hard, while very similar ones are computationally easy?

    These questions were mostly raised during the 20th century, and they accompanied and guided the actual development of computers.

    Many of these and related questions were resolved, but some (especially those dealing with computational hardness) retained their status as key open problems into the 21st century.

     

    Formalities

    Lecturer:  Prof. Iftach Haitner

    Teaching assistants:

    • Yuval Moskovitch

    • Mark Rozanov

    • Noam Mazor 

    Reception

    Iftach: TBA

    Yuval: TBA

    Mark: Sunday 10-11, Shreiber 010

    Noam: TBA

    Prerequisites

    Formal prerequisite: Extended introduction to CS.

    If you're a non-CS student and you wish to take this course, you are encouraged to contact the instructors.

    Grade

    In any case, one has to pass the exam in order to pass the course.

    Final grade computation:

    • Effective Midterm Grade = max{Final Exam, Midterm Exam}

    • Effective HW Grade = average of best 5 out of 6 (non-submission and late submission are 0).

    • Final Grade = 0.75*Final Exam + 0.15* Effective Midterm +0.10 * Effective HW

    Reading

    Textbook:

    • M. Sipser, Introduction to the Theory of Computation, PWS Publishing Co., 1997 (second edition, 2005).

    Reference books:

    • C. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Co., 1994.

    • H. Lewis and C. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1981.

    • J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Co., 1979.

    • אוטומטים ושפות פורמליות, האוניברסיטה הפתוחה, 1991.‏
    • Course Plan

      The course roughly consists of four parts:

      1. Lectures 1-3: Languages and automata theory: Regular languages.
      2. Lectures 4-6: Languages and automata theory: Context-free languages.
      3. Lectures 7-10: Computability theory.
      4. Lectures 11-13: Introduction to complexity theory.

      Detailed Schedule

      Lecture Date Lecture topics Textbook references
      1 Oct. 15 Administratrivia& Introduction Admin&Intro. Finite automata. Regular languages. Closure properties: Union. DFA1.   Chapter 1, Section 1.1.
      2 oct. 22 Non-Deterministic Finite Automata (NFA). Closure properties of Regular Languages. Regular expressions and their equivalence with finite automata via generalized NFAs. DFA2. Chapter 1, Sections 1.1-1.3 
      3 Oct. 29 Two approaches for proving a language is non-regular: (1) Myhill-Nerode theorem (2) the pumping lemma. Computational questions stemming from finite automata. DFA3.   Sipser, Sections 1.4, 2.1-2.2. Hopcroft and Ullman, Section 3.4.
      4 Nov. 5 Context free languages. Chomsky normal form of a CFG. Checking Membership. CFL1 Sipser, Section 2.1 
      5 Nov. 12 Pumping lemma for CFGs. Push Down Automata. CFL2 Sipser, Sections 2.1, 2.2, 2.3.
      6 Nov. 19 Closure properties of CFLs. Algorithmic properties about CFLs. The equivalence theorem: CFLs vs. PDAs. CFL3 Sipser, Sections 2.1, 2.2, 2.3.
      7 Nov. 26

      Turing Machines, Formal definition, Multi-tape TMs, RAMs, Church-Turing thesis. TM1

      Sipser, Sections 3.1,3.2,3.3 
      8 Dec. 3

      Non-Deterministic TMs. Encoding of TMs. A universal TM. The Halting /Acceptance problems are undecidable. TM2

      Sipser, Sections 3.2, 3.3, 4.1, 4.2
      Dec. 9 Midterm
      9 Dec. 10 Mapping reductions. Rice theorem and friends.TM3 Sipser, Sections 5.1, 5.3.
      10 Dec. 17 Reductions using controlled executions and computation histories. Linear Bounded Automata. RE Completeness. TM4 Sipser, Sections 5.1, 5.3. 
      11 Dec. 24 Deterministic and non-deterministic time classes. The classes P and NP and examples of languages in each. The class coNP. Verifiability. Polynomial time reductions. NP-completeness. NP1 Sipser, Sections 7.1. - 7.4.
      12 Dec. 31 NP-completeness of SAT, CLIQUE, INDSET,  Clique. NP2 Sipser, chapter 7.4 and 7.5.
      13 Jan. 7 NP-completeness of Hamiltonian Path/Cycle  and SubsetSum.  NP3 and Ham-reduction
      Sipser, chapter 7.4 and 7.5.
    • Midterm

      Date and time

      Sunday, December  9, 12:00
      Duration: 1.5 Hours

      Material

      Everything about regular and context-free languages.

    • Homeworks

      Exercises should be submitted electronically through the Moodle site

      The submission should be in a .pdf file with the name [id]_ex[ex#] (e.g. 12345678_ex1.pdf)

      Most important: No personal extension (except for MILUIIM).

      Grades Will be available within two weeks in Moodle. You can appeal your grade within a week from the grades publication date.