Contents (hide)

Course Schedule

Day Time Room
Tuesday 10:00-12:00Building 34, Room 207
Wednesday12:00-14:00Building 90, Room 237


Name Web page E-mail Office Office hours
Amos Beimel amos.beimel at Building 37, Room 115 Tue. 14-16
Ofer Neiman neimano at cs dot bgu dot ac dot il Building 37, Room 215 Thu. 12-14


  1. S. Arora, B. Barak. Complexity Theory: A Modern Approach., Cambridge University Press, 2009.

Other Textbooks

  1. M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
  2. C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
  3. J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computations. Second Edition, 2001.
  4. M.R. Garey and D.S. Johnson. Computers and Intractability, a guide to NP-completeness. 1979.

Grading Policy

Final exam, 80%. Students MUST PASS the exam to pass the course.
The exam is with no supplementary material.
Homework assignments, 20%. There will be about 5-6 homework assignments. These assignments do not include any programming.

There will be only one exam in the course (no MOED B).

You may hand in the exercises either by yourself or with one other student. Students whose partner has a valid reason not to hand in some assignment must still hand in the assignment. You may not hand in the assignments in groups larger than two. Cheating will not be tolerated. Cases of suspected cheating may result in the grade 0 on assignments and will be processed by the university disciplinary committee (see the section below on Academic Dishonesty ).

Academic Dishonesty

Cheating in university courses is regarded as a serious offense. To avoid any possible misunderstanding please read the following carefully.

Academic dishonesty includes any act of obtaining, soliciting or making available to others, material related to homework assignments. If you commit any of the above then you are guilty of academic dishonesty. If your partner commits any of the above and you submit the assignment jointly then you are just as guilty of academic dishonesty. If you choose to work with a partner then you are both personally responsible for what you submit together. Claiming that you were not aware of the fact that your partner copied the assignment from somebody else will not absolve you of any responsibility.

To eliminate any doubts, we make no distinction between the two (or more) sides of the cheating. If we suspect that Bob and Alice have copied an exercise one from the other, we see no way they could have done this without cooperation. It is your own responsibility to make sure that nobody can copy your files. Be discreet.

We will not tolerate academic dishonesty in this course. If you are suspected of academic dishonesty then a complaint will be filed with the university disciplinary board (va'adat mishma'at) and a detailed report placed in your academic records. The minimal penalty for this type of offense is a grade of zero in the course. You might also be expelled from the university.

We keep records of submitted homework assignments and reserve the right to check for academic dishonesty anytime after you have submitted an assignment.

Please do not cheat!