Complexity of Algorithms
(Topic outline)
1.1 Finite automata
1.2 Turing machines
1.3 Random Access Machines
1.4 Boolean functions and circuits
1.5 Clocked circuits
1.6 Cellular automata
Exercises
2.1 Regular languages
2.2 Recursive and
recursively enumerable languages
2.3 Other algorithmically
undecidable problems
2.4 Logically undecidable problems
Exercises
3.1 Time and space
3.2 Polynomial time I: Arithmetic
3.3 Polynomial time II: Graph Theory
3.4 Polynomial space: games
3.5 Other important complexity classes
Exercises
Exercises
5.1 Non-deterministic
Turing machines
5.2 The complexity
of non-deterministic algorithms
5.3 Languages in NP
5.4 NP-completeness
5.5 Other NP-complete problems
Exercises
6.1 Verifying a
polynomial identity
6.2 Prime testing
6.2 Randomized complexity
classes
Exercises
7.1 Infomation (Kolmogorov)
complexity
7.2 Self-limiting
information complexity
7.3 The notion of a random sequence
7.4 Kolmogorov complexity
and data compression
Exercises
8.1 Classical methods
8.2 Pseudo-random numbers
8.3 One-way functions
Exercises
9. Parallel algorithms
8.1 Parallel random access machines
8.2 The class NC
Exercises
10. Decision trees
9.1 Algorithms decision trees: sorting and searching
9.2 Non-deterministic decision trees
9.3 Lower bounds on the depth of decision trees
Exercises
11. Communication complexity
10.1 Communicaton matrix and protocol-tree
10.2 Non-deterministic communication complexity
10.3 Randomized protocols
Exercises
12. The complexity of algebraic computations
12.1 Multiplication and inversion of large matrices
12.2 Finite Fourier transform and computing with polynomials
12.3 Lower bounds on the number of operations
12.4 Algebraic complexity classes
Exercises
13. Circuit complexity
13.1 Circuit and formula complexity
13.2 Lower bounds on bounded-depth and monotone circuits
Exercises
14. Cryptography
14.1 A classical problem: one-time pads
14.2 Passwords and signatures
14.3 Public key cryptography
Exercises