Introduction to the Theory of Computing 1.

2024 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, IB027
                  Tuesday 12:15 - 14:00, IB025
Practices: Wednesday 10:15 - 11:45, R506, instructor: Hilal Hama Karim, e-mail: hilalothman_at_yahoo.com
                  Wednesday 12:15 - 13:45, R508, instructor: Rita Csákány
                  Wednesday 14:15 - 15:45, QBF10, instructor: Rita Csákány

Midterms:

first midterm: October 25, Friday, 8:00 - 10:00, IB028
first retake of the first midterm: November 15, Friday, 8:00 - 10:00
second midterm: November 26, Tuesday, 18:00 - 20:00
first retake of the second midterm: December 9, Monday
second retake of (both) midterms: December 16, Monday, Q2

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