algo CTS

Mathematical preliminaries: Exponentiation and logarithms, numerical series, notation conventions, graphs

Recursive algorithms: advanced applications of recursion, computational induction, algorithmic principle “backtracking”

Algorithm analysis: correctness, termination, running time analysis, asymptotic notation

Efficient sorting: heapsort, mergesort, quicksort, lower bound for comparison sorts, linear sorting algorithms

Abstract data-types and their implementation: stacks, queues, double-ended queues, priority queues, amortized analysis

Search trees: binary search trees, AVL-trees, B-trees, red-black trees, splay trees, tries.

Hash tables: hash function, collision resolution, separate chaining, open addressing, linear and quadratic probing, double hashing

Graph algorithms: Representation of graphs, breadth-first search, depht-first search, cycle detection, topological sorting, shortest paths, minimal spanning trees, maximum flow

(optional) Limits of efficient computability: complexity classes P and NP, NP-completeness