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