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.
Nondeterministic and randomized decision trees. Communicational complexity
(deterministic and nondeterministic). Randomized communicational complexity. Interactive and zeroknowledge proofs. Cryptography.
RSA code. Informational complexity. Kolmogorov complexity, entropy, coding,
generating and testing pdeusorandom 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 