Introduction to the Theory of Computing 2 (BMEVISZAA04)

2020 Spring semester

Monday, 14.15-16.00, QBF 09

Rita Csákány
Office: IB 137/a
Office hours: Monday 4-6 pm. in IB 137/a, or by arrangement

Tuesday, 8.15-10.00, E403,  instructor:  Padmini Mukkamala, e-mail:
Friday, 12.15-14.00, E403,   instructor:  Rita Csákány

There will be one midterm during the semester, and two possibilities
to repeat it (you have to register in the neptun only for the second one).
To obtain a signature, you have to reach at least 40% on the midterm.
The final grade is based 40% on the midterm and 60% on the oral exam.

May 8, Friday, 8-10 am.
First repeat: May 25, Monday
Second repeat: June 3, Wednesday


(Some of the) Topics of the class

Lecture 6:  notes, video
Lecture 7:  notes
Lecture 8:  notes

Exercise sets and solutions:

  • Exercise-set 1. ,  HW: 5/b, 6, 11, 13, 14  Solutions
  • Exercise-set 2. ,  HW Tuesday: 1/d, 2, 10, 16, Friday: 1/d, 3, 10, 11, 15, 16  Solutions
  • Exercise-set 3. ,  Solutions
  • Exercise-set 4. ,  Solutions
  • Exercise-set 5. ,  Solutions
  • Exercise-set 6. ,  Solutions
  • Exercise-set 7. ,  Solutions
  • Exercise-set 8. ,  Solutions
  • Exercise-set 9. ,  Solutions
  • Exercise-set 10. ,  Solutions
  • Exercise-set 11.,  Solutions
  • Exercise-set 12.
  • Exercise-set 13.
  • Online materials:

  • Graph Theory slides
  • R. Diestel: Graph Theory

  • Midterms from previous years:

    midterm, repeat, second repeat
    2018: midterm, repeat, second repeat
    first midterm, repeat, second repeat; second midterm, repeat, second repeat
    2016: first midterm, repeat, second repeat; second midterm, repeat, second repeat
    2015: first midterm, repeat, second repeat; second midterm, repeat, second repeat

    List of Questions on the exam from last year

    Final Exams:
    The exam consists of two parts, but you can get a grade for your accomplishment after the first part already.

    The maximum points for the final grade is 100.
    From this you can obtain 40 points on the midterm, and 60 on the final exam.
    The points for the midterm are obtained by multiplying your midterm points by 0,8.
    The final grade is calculated as follows:
    below 40 points: fail (1), from 40 points: pass (2), from 55 points: satisfactory (3), from 70 points: good (4), and from 85 points: excellent (5).

    The first part of the final exam contains 10 multiple choice questions in the Moodle. You'll have 30 minutes to answer them. You have to answer these questions in order, you cannot go back and correct your previous answers. These questions will check the knowledge of basic notions, definitions, theorems and algorithms, you won't need proofs to solve them.
    If you have less than 6 correct answers, then you failed the exam, otherwise for 6 correct answers you get 24 points, for 7 correct answers you get 27,8 points and for 8 or more correct answers you get 30 points for this part of the exam.
    At this point you can finish the final exam with the points you obtained for this part, and you must do it if you have less than 6
    correct answers.

    If you have at least 6
    correct answers, then after the first part you'll have 15 minutes to decide whether you want to continue the final exam or not. You'll have to signal your decision in the Moodle.

    If you decide not to accept the final grade obtained based on the first part of the final exam, then you can continue with the second part. For this you'll have to solve 3 more complicated questions involving proofs. Each such question is worth 10 points.
    The solutions for this part have to be uploaded in the Moodle as one pdf file, similarly to the midterm. You'll have 60 minutes to accomplish this part, including the uploading of the file.
    If you achieve less then 10 points (out of 30) in this part, then your final grade will be one worse than the one based on the first part of the final exam.
    Otherwise your points for the final exam will be the sum obtained for the two parts.