Exam preparation:
This 3 hour exam is OPEN book (but no electronic devices).
Go through the list of all algorithms that were covered, making sure:
- you understand how they work (you can apply the algorithm to
a small problem on paper, you could code it if asked to)
- you understand what their complexity is
(e.g. MergeSort is O(NlogN))
- you understand their potential constraints
(e.g. no negative weights for Dijkstra's algorithm)
Also be prepared to "invent" an algorithm for a given
programming problem: supply (very) high-level pseudo code
and a complexity estimate.
Here is a list of the main algorithms and concepts covered:
Complexity
Correctness
Verification / Halting problem
Knuth-Morris-Pratt
Boyer-Moore
Rabin-Karp
suffix tries
regular expressions
Segdewick
Thompson
Pattern search
Regex parsing/compiling
Deques
Shannon-Fano, Huffman, arithmetic coding
LZ77 / LZ78 / LZW
PPM
Burrows Wheeler transform
Greedy Method
Divide-and-conquer
Master method (be able to apply it)
Dynamic programming
Longest common subsequence
pseudo-polynomial knapsack
Graph data structures
Depth-first search
Breadth-first search
MST
Prim-Jarnik
Kruskal
Baruvka
Union-find
Shortest path
Dijkstra
Bellman-Ford
in a Dag
all-pairs
Digraphs
Strong connectivity
Floyd-Warshall
Topological sorting
DFS for biconnected components
Ford-Fulkerson
k-approximation for NP problems
Backtracking
Branch-and-bound
GSAT / WalkSAT