Algorithmics
Content (tentative)
- Algorithms, summation, design patterns: step-by-step processing (linear effort), calculation with constant effort, reduction principle: sorting by insertion, sorting by selection, problem complexity, algorithm analysis: asymptotic complexity of an algorithm (O-notation)
- Sorting by divide-and-conquer, algorithm analysis, design pattern divide-and-conquer: mergesort, quicksort, omega and theta notation, heaps as data structures, heapsort
- Sorting by distribution, counting sort, multi-criteria sorting using stable sorting methods, radix sort, bucket sort, repetition: lists, cellars, queues
- Priority queues, implementation with binary heaps, binomial heaps and Fibonacci heaps, amortized analysis
- Selection, K-least element
- Sets, self-organizing data structures, binary search trees, iterators and navigation structures, equilibrium, splay trees, red-black trees, AVL trees
- Sets of character strings, Tries, PATRICIA Tries
- Disjoint sets, Union-Find data structures
- Association of objects, hash tables, dynamic hashing (collision lists, linear probing, quadratic probing, double hashing), static hashing, family of universal hash functions
- Graphs, operations on graphs, graph representations, breadth-first and depth-first search, context components, shortest paths, single-source shortest test paths (Dijkstra's algorithm, A* algorithm, Bellman-Ford algorithm), All-Pairs-Shortest-Paths, Transitive Hull, Minimal Spanning Tree (Kruskal's Algorithm, Jarnik-Prim Algorithm), Network Flows (Ford-Fulkerson Algorithm, Edmonds-Karp Algorithm), Bipartite Matching
- Search graphs for games, minimax search, search space construction, alpha-beta pruning for search space pruning
- Dynamic programming, greedy methods, optimization problems, sequence alignment (longest-common-subsequence, LCS), knapsack problem, planning and arrangement problems, change determination, completeness of algorithms
- String alignment, Exact algorithms (Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp, suffix trees and fields), Approximate string alignment through dynamic programming