CMP 338 Summary

1. binary search
2. stacks and queues
   1. definitions
   2. linked list implementation
   3. array implementation and dynamic resizing of arrays
3. disjoint union/find
   1. array implementation
   2. map/set implementation and lazy map initialization
   3. weight balanced unions
   4. path compression on finds
4. sorting algorithms
   1. comparison sorts
      1. insertion sort
      2. merge sort
      3. quicksort
         • selection algorithms
           1. quick select
           2. linear select
      4. heap sort and priority queues
   2. radix sorts
      1. key-indexed counting
      2. LSD (least significant digit) string sort
      3. MSD (most significant digit) string sort
      4. three-way string quicksort
5. symbol tables
   1. unordered symbol tables
      1. operations
         • void put(Key k, Value v)
         • Value get(Key k)
         • void delete(Key k)
           (assume: delete(Key k) {put(k, null);})
         • boolean contains(Key k)
         • boolean isEmpty()
         • int size()
         • Iterable keys()
      2. sequential search symbol tables
      3. hash tables
         1. Java hashCode() and hash methods
            • consistant with Equals()
         2. collision resolution
            1. separate chaining (closed-addressing)
            2. linear probing (open-addressing)
               • array resizing
   2. ordered symbol tables
      1. operations
         • all unordered symbol table operations
         • Key min()
         • Key max()
         • Key floor(Key k)
         • Key ceiling(Key k)
         • int rank(Key k)
         • Key select(int n)
         • void deleteMin()
         • void deleteMax()
         • Iterable<Key> keys(Key lo, Key hi)
      2. binary search trees
      3. 2/3 trees
      4. left-leaning red/black trees
         1. Node rotateLeft(Node n)
         2. Node rotateRight(Node n)
         3. void flipColors(Node n)
         4. void put(Key k, Value v)
         5. void delete(Key k)
   3. symbol tables with String keys
      1. operations
         • all ordered symbol table operations
         • String longestPrefixOf(String s)
         • Iterable<String> keysWithPrefix(String s)
         • Iterable<String> keysThatMatch(String pattern) // periods in pattern match any char
      2. tries
      3. ternary search tries (TST's)
6. graph algorithms
   1. kinds of graph
      1. undirected
      2. directed
      3. directed acylic graphs (DAG's)
      4. edge-weighted undirected graphs, directed graphs, DAG's
   2. implementations
      1. array based
      2. map/set based
   3. depth-first search
   4. breadth-first search
   5. topological sort
   6. minimum spanning tree (undirected graphs)
      1. Prim
      2. Kruskal
   7. shortest path
      1. breadth-first search (undirected graphs)
      2. Dijkstra (edge-weighted directed or undirected graphs with non-negative edge weights)
      3. topological sort (edge-weighted DAG's)
      4. Belman-Ford (edge-weighted directed graph, no reachable negative cycles)
7. intrastring search
   1. substring search
      1. brute force
      2. Knuth-Morris-Pratt
      3. Boyer-Moore
      4. Rabin-Karp (fingerprint)
   2. matching regular expressions
8. data compression
   1. run-length coding
   2. Huffman coding
   3. Lemple-Ziv coding
   4. arithmetic coding
9. dynamic programming
• minimum edit distance
10. P and NP
    • What does it mean for a problem to be in P?
    • What does it mean for a problem to be in NP?
    • What does it mean for a problem to be NP-complete?