Hash Table and Hash Function Quiz

Hash Table and Hash Function

• A hash table is a data structure that maps keys to indices of a backing array using a hash function.
• Linear probing is a collision resolution technique that searches for the next available slot in the array.
• If the end of the array is reached, the search wraps around to the beginning of the array.
• Quadratic probing is another collision resolution technique that uses a quadratic formula to find the next available slot.

Hash Table Examples

• Example 1: Inserting keys (11, 85, 77, 10, 35) into a hash table with a table size of 10.
• The hash function is key modulo table size.
• Collisions are resolved using quadratic probing.
• Example 2: Inserting keys (99, 28, 88) into a hash table with a table size of 10.
• The same hash function and collision resolution technique are used.

Double Hashing

• Double hashing is a technique that uses two hash functions to probe for an available slot.
• The first hash function determines the initial index, and the second hash function determines the increment for the probe sequence.
• The increment should never be zero, and all cells in the table should be probed.

Quicksort

• Quicksort is a sorting algorithm that uses a partitioning strategy to divide the array into smaller subarrays.
• The partitioning strategy involves swapping the pivot element with the last element, and then moving a "wall" of elements smaller than the pivot to the left and a "wall" of elements larger than the pivot to the right.
• The algorithm repeats the partitioning process until the entire array is sorted.

External Sorting

• External sorting is a technique used when the input data does not fit into main memory.
• Previous algorithms, such as Shellsort and Quicksort, require that the input fit into main memory.

Dijkstra's Algorithm

• Dijkstra's algorithm is a graph search algorithm used to find the shortest path between nodes in a graph.

Huffman's Algorithm

• Huffman's algorithm is a greedy algorithm used to construct an optimal prefix code.
• The algorithm maintains a forest of trees, where each tree represents a character in the input data.
• The algorithm repeatedly selects the two trees of smallest weight, combines them into a new tree, and updates the weights of the remaining trees.

Divide and Conquer

• Divide and Conquer is a algorithm design paradigm that breaks down a complex problem into smaller sub-problems.
• The algorithm solves each sub-problem recursively, and then combines the solutions to the sub-problems to form the solution to the original problem.