Algorithms and Data Structures 1000-213aASD

1. Algorithm design methods: divide and conquer, dynamic programming, greedy algorithms, backtracking, branch and bound, randomization
2. Algorithm analysis: computational models (Random Access Machine, decision trees), time and space complexity, worst-case and average complexity, amortized cost analysis, probabilistic analysis, lower bounds (problem complexity versus algorithm comoplexity)
3. Sorting and selection: sorting by comparisons (InsertionSort, QuickSort, HeapSort, MergeSort), lower bound for sorting, selection (Hoare's algorithm and ,,magic fives' algorithm''), radix and lexicographical sorting, external sorting, priority queues (binary heaps, binomial and Fibonacci queues
4. Searching: binary search, dictionaries, binary search trees, balanced trees (AVL-trees, red-black trees), external search, hashing, radix search
5. Find-Union Problem: definition, data structures, amortized cost, applications
6. Graphs: representation, graph traversal methods (depth-first search, breadth-first search, topological sorting), biconnected and strong-connected components, minimal spanning trees, path problems (Dijkstra's algorithm and its implementations), maximum matchings (algorithm of Hopcroft and Karp), maximal flow (maximal flow and minimal cut, algorithm of Ford and Fulkerson, Dinic's algorithm)
7. Libraries of algorithms: LEDA, STL