My introduction to theoretical computer science. There will be mostly algorithm design and you will see some pretty complicated, but very useful, algorithms. The complexity part of the course is about how to investigate which problems can be solved (in reasonable time) with the help of computers, which problems take an unreasonably long time and which cannot be solved with a computer at all. Problems that are too difficult to solve accurately can sometimes be solved approximately.
Decomposition, greedy algorithms, dynamic programming, local and exhaustive search. Algorithm analysis. Approximation algorithms and heuristics. Applications with algorithms for problems on sets, graphs, arithmetic, cryptography and geometry. Implementation of algorithms.
Review of hash tables and heaps; balanced trees, Bloom filters, persistent data structures Use and implementation of data structures. Computability and complexity: The concept of reduction, the complexity classes P (polynomial time) and NP (non-deterministic polynomial time). NP-complete problems, undecidable problems. Coping with computationally intractable problems.