Sequence Algorithms |
Comments |
Sorting (swap) |
Bubble / Insertion Selection / Shell |
O(n*n) |
Sorting (divide & conquer) |
Merge / QuickSort |
O(n log n) |
Searching |
Linear Search |
O(n) |
Binary Search |
O(log n) |
Hashing h(key) => ref |
Division Method Multiplication Method |
Collision Resolution
Separate Chaining
Linear Probing
Quadratic Probing
Double Hashing
|
Tree Algorithms |
Comments |
Traversals (Depth-First (stack)) |
Pre-/In-/Post-Order |
NLR /
LNR /
LRN
|
Breadth-First Traversal (Q) |
Nearest Neighbours |
Balancing Algorithms (AVL-trees) |
Single / Double Rotations |
Digraph Algorithms |
Comments |
Shortest Path |
Dijkstra |
Single Source Shortest Path (result: vector) |
Floyd |
All Pairs Shortest Path (result: matrix) |
SPT Shortest Path Tree |
modified Dijkstra |
result: tree (2 vectors) |
Transitive Closure |
Warshall |
+ cycle testing |
Topological Sort (DAG)
reverse order (dfs/postorder dfn)
source removal
|
Partial Ordering |
Strong Components (SC) |
dfs(G)+number; reverse Gr; dfs(Gr) => DFSF; each tree = SC |
Cycle Detection |
Warshall or (DFSF + Back Edges) |
Graph Algorithms |
Comments |
Minimum-cost Spanning Tree (MST) |
Prim |
Partition: U and V-U
(cheapest (x,y,c): x in U, y in V-U; y to U) |
Kruskal |
Partition: V1, V2, ..., Vn
(connect Vx, Vy - cheapest (x,y,c) in PQ) |
Articulation Point |
Root >=2 children; low(some child(v)) >= dfn(v) |
Travelling Salesman Problem (TSP) |
similar to Kruskals => Hamilton Circuit (degree(v)=2) |
Cycle Detection |
DFSF + Back Edges |
Digraph / Graph Algorithms |
Comments |
Searching |
Depth-First (Stack) |
Depth-First Spanning Forest |
Breadth-First (Q) |
Nearest Neighbours |