cop3503_review.md

COP 3503 Review

Hash tables

Linear (and quadratic) put and get

public class LinearHashTable {
  void put(DataStruct ds) {
    // For the test, we don't have to worry about table expansion.
    int hv = getHashValue(ds.getKey());

    while(list[hv % tableSize] != null &&
        !list[hv % tableSize].getKey().equals(ds.getKey())) {
      hv++;
      // q++; <-- for quadratic
    }

    list[hv % tableSize] = ds;;
    // list[hv + q * q % tableSize] <-- for quadratic
  }

  DataStruct get(String key) {
    int hv = getHashValue(key);

    while(list[hv % tableSize] != null &&
        !list[hv % tableSize].getKey().equals(key)) {
      hv++;
    }

    return list[hv % tableSize];
  }
}

Table Expansion

In order to expand the table, you expand it to twice its size rounded up to the next prime.

Huffman

Helpful YouTube video

Initialization:

1. Add DataStructs to PriorityQueue
2. Ensure you implement Comparable
3. Build the tree

# Building the tree
while(queue.size > 1)
   pop left
   pop right

   create tree from left and right
   add root of tree to queue

4. Make compression table

Compression:

1. Go through data
2. Look up bit sequence for each symbol
3. Print bit sequence

Decompression

1. Get one bit at a time
2. Walk tree
3. Encounter a leaf
4. Output the value

Graphs

Graph will be undirected

• Listing result of breadth-first search
• Listing result of depth-first search
• Creating an adjacency matrix
• Topological sort
• Dijkstra's algorithm
• Kruskal