Introduction to the Theory of Computing 1.

2023 Fall semester

Lecturer Rita Csákány
E-mail: csakany_at_cs.bme.hu
Office: IB 137/a
Office hours: to be announced

Classes:

Lectures:   Monday 12:15 - 14:00, QBF08
                  Tuesday 12:15 - 14:00, QBF08
Practices: Wednesday 10:15 - 11:45, R506
                  Wednesday 12:15 - 13:45, IB147
                  Tuesday 14:15 - 15:45, E403

Midterms:

first midterm: November 3, Friday, 8:00 - 10:00
first retake of the first midterm: November 17, Friday, 8:00 - 10:00
second midterm: December 1, Friday, 8:00 - 10:00
first retake of the second midterm: December 11, Monday, 8:00 - 10:00
second retake of (both) midterms: December 18, Monday, 10:00-12:00

Grading

There will be two midterms during the semester, each containing 6 questions worth 10 points each.
To obtain a signature students cannot miss more than 30% of the practice classes and have to achieve at least 40% (i.e. at least 24 points) on each of the two midterm tests or on one of their retakes.
On the second retake students can repeat only one (but either one) of the two midterms.
On the first retakes students can repeat a midterm to improve their grade as well. In this case the points obtained on the retake are considered, regardless whether it is better or worse than the original midterm. The only exception is that a signature obtained cannot be lost by writing a bad retake.
The final exam will be oral.
The final grade will be based 40% on the points from the two midterms and 60% on the oral exam.

Syllabus

Lecture notes

Additional material:

Primality testing: Fermat test, Miller-Rabin test
Public key cryptosystems: RSA, original paper