## 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:

• Mark Rozanov

• Noam Mazor

### Reception

Iftach: Sunday 10:00-11:00 (only after coordinating via email)

Mark: Monday 16:00-17:00 (only after coordinating via email)

Noam: Wednesday 16:00-17:00

### 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.

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

• 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

Textbook:

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

Reference books:

• 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. 23 Administratrivia. Introduction. Finite automata. Regular languages. Closure properties: Union. Chapter 1, Section 1.1. Administratrivia, Lecture 1, Recitation 1
2 oct. 30 Non-Deterministic Finite Automata (NFA). Closure properties of Regular Languages. Regular expressions and their equivalence with finite automata via generalized NFAs. Chapter 1, Sections 1.1-1.3  Lecture 2, Recitation 2
3 Nov. 6 Two approaches for proving a language is non-regular: (1) Myhill-Nerode theorem (2) the pumping lemma. Computational questions stemming from finite automata. Sipser, Sections 1.4, 2.1-2.2. Hopcroft and Ullman, Section 3.4. Lecture 3
4 Nov. 13 Context free languages. Chomsky normal form of a CFG. Checking Membership.  Sipser, Section 2.1  Lecture 4
5 Nov. 20 Pumping lemma for CFGs. Push Down Automata. Sipser, Sections 2.1, 2.2, 2.3. Lecture 5
6 Nov. 27 Closure properties of CFLs. Algorithmic properties about CFLs. The equivalence theorem: CFLs vs. PDAs. Sipser, Sections 2.1, 2.2, 2.3. Lecture 6
Dec. 1

### Mid Term

7 Dec. 4

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

Sipser, Sections 3.1,3.2,3.3  Lecture 7
8 Dec. 12 Non-Deterministic TMs. Encoding of TMs. A universal TM. The Halting /Acceptance problems are undecidable. Sipser, Sections 3.2, 3.3, 4.1, 4.2. Lecture 8
9 Dec. 18 Mapping reductions. Rice theorem and friends. Sipser, Sections 5.1, 5.3. Lecture 9
10 Dec. 25 Reductions using controlled executions and computation histories. Linear Bounded Automata. RE Completeness.  Sipser, Sections 5.1, 5.3.  Lecture 10
11 Jan. 1 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.  Sipser, Sections 7.1. - 7.4. Lecture 11
12 Jan. 8 NP-completeness of SAT, CLIQUE, INDSET,  Clique Sipser, chapter 7.4 and 7.5. Lecture 12
13 Jan. 15 NP-completeness of Hamiltonian Path/Cycle  and SubsetSum. Sipser, chapter 7.4 and 7.5. Lecture 133SAT to HamPath

### Date and time

Friday December 1, 9:00
Duration: 1.5 Hours

### Material

Everything about regular and context-free languages.

• ### Exams

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).

### Websites

Fall 2017

Spring 2016

Spring 2015

Spring 2014

Spring 2013

Spring 2012

Spring 2011

### Videos

Videos, including Fall 2016 course by Iftach, can be found here.