discipline

Pure Math

subject

Computer Science

lecturers

Vince Grolmusz

credits

2

period

2

curriculum

Randomized algorithms. Prime test. Computing the volume. Decision trees. Lower bounds for the depth of decision trees. Non-deterministic and randomized decision trees. Communicational complexity (deterministic and non-deterministic). Randomized  communicational complexity.  Interactive and zero-knowledge proofs. Cryptography. RSA code. Informational complexity. Kolmogorov complexity, entropy, coding, generating and testing pdeuso-random bits. Parallel algorithms, addition and multiplication. Brent's theorem. Applications of matrix multiplication. Models for parallel computation. Randomized parallel algorihms. 

literature

T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algortihms, MIT, 1990.

Form of tuition

Lectures

mode of assessment

oral exam