Here we list the concepts and paradigms that we require and some specific examples and/or algorithms that we assume are familiar to you.
For the ease of readability some items do occur several times, e.g., spanning tree algorithms under design methods and graph algorithms.
You can refresh your knowledge here.
Algorithmic Design Methods
- Greedy. Minimum spanning tree (Kruskal and Jarník/Prim).
- Divide and Conquer. Mergesort, quicksort, convex hull.
- Dynamic Programming. Longest increasing subsequence, knapsack, matrix multiplication.
- Backtracking and Recursion. Maximum independent set, 8-Queens problem.
- Basic. Array, list, stack, queue, hash table, binary search tree, bitmask.
- Priority queues. Binary heap.
- Union Find. constant Find operation (using arrays), constant Union operation (using trees), path compression heuristic.
- Sorting and Searching. Mergesort, quicksort, heapsort, insertion sort, bubble sort, radix sort, bucket sort, binary search.
- Graph algorithms. Graph Traversal (depth-first-, breadth-first-search, connected components), minimum spanning tree, single source shortest path (Dijkstra), bipartite matching, maximum flow (Ford/Fulkerson and Edmonds/Karp).
- Graph notions. Hamiltonian cycle, Eulerian walk, traveling salesman tour, coloring, network flow, clique, independent set, topological sorting.
- Geometry algorithms. segment and line properties, convex hull.
- Number theoretic algorithms. Greatest common divisor (Euclid), powers of an element, modular arithmetics.
Analysis of Algorithms
- Big O notation.
- Analysing time/space complexity. nested for-loops, the recursion-tree method.
- NP-hardness. 3-SAT, Traveling salesmen problem.