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.


Location and Hours

Please check the course schedule.


  • Homepage|dmuhcan#ztiwohsreD muhcaN .forP
  • Homepage|ruosnam#ruosnaM yahsiY .forP

Teaching Assistants

  •|norodnaed#noroD naeD
  • moc.liamg|lavuysom#hctivoksoM lavuY
  • moc.liamg|09anfad#hedaS anfaD

Reception (only after coordinating via email).

Nachum: Monday 16-17
Yishay: by e-mail coordination
Dafna: Sunday 16-17
Dean: Thursday 17-18 (Shenkar physics 304)
Yuval: Wednesday 12-13


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.


The HW consists 10% of the final grade. You may not transfer HW grades from previous semesters.
The midterm consists 10% of the final grade, or 20% if the midterm grade is higher than the final exam grade.
In any case, one has to pass the exam in order to pass the course.

Note Final Grade Computation:

  • EffectiveMidterm = max{FinalExam, MidtermExam}
  • EffectiveHW = average of best 5 out of 6 (non-submission and late submission are 0).
  • Final Grade = 0.7*Final Exam + 0.1*MidtermExam + 0.1*EffectiveMidterm + 0.1*EffectiveHW



  • 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.‏
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License