Data Structures: Hash Functions and Tries

Hash Functions and Methods

• Hash functions map data to numerical values, crucial for data structures like hash tables.
• Division Method: Divides the key by the table size, taking the remainder.
• Folding Method: Splits the key into parts and sums them.
• Mid-Square Method: Squares the key and extracts a portion of the middle digits.

Hash Table Operations

• Linear Probing: Inserts data sequentially until an empty slot is found.
• Quadratic Probing: Inserts data using quadratic computations to find open slots.
• Comparing Linear vs. Quadratic Probing: Quadratic is generally more efficient, reducing collisions and improving search time.

Trie Data Structures

• Standard Tries: Each node represents a character.
• Compressed Tries: Compresses chains of characters into single nodes.
• Suffix Tries: Stores all suffixes in a Trie structure for substring searching.
• Constructing Suffix Trie: Demonstrates step-by-step suffix trie construction for a given string.

Longest Prefix Suffix Array (LPS)

• LPS Array: Stores the length of the longest proper prefix of the pattern which is also a suffix of the pattern.
• Finding LPS Array for a Pattern: Explicitly shows step-by-step LPS array construction.

Graph Algorithms

• Bellman-Ford Algorithm: Solves the single-source shortest path problem in graphs, considering negative edge weights.
• Ford-Fulkerson Algorithm: Computes the maximum flow in a graph.
• Dijkstra's Algorithm: Determines the shortest path between nodes in graphs that have positive weights.

Dynamic Programming

• Longest Path Problem (DP): Explanation of whether a dynamic programming solution exists for the longest path problem in a graph.
• Justification for or against DP Applicability: Justification of the usage of DP for the longest path problem.
• Use Case: Illustrative counter-example where Bellman-Ford is needed rather than DP for solving the longest path problem.

Data Structures

• Skip Lists: Introduce skip lists, a data structure similar to linked lists, that improve upon standard linked lists in terms of search, insertion, and deletion efficiency.
• Advantages: Advantages and disadvantages over traditional linked lists and other data structures.

Union-Find Data Structure

• Determine Connected Components: Explains uses for determining same connected components in a graph
• Dynamic Connectivity: Describes implementation of efficient dynamic connectivity in a graph.
• Social Network Analysis: Illustrates how the Union-Find structure is used in social network analysis by applying it to connection determination.

String Matching Algorithms

• KMP Algorithm: Explanation and analysis of the KMP algorithm (Knuth-Morris-Pratt)
• Mismatch Handling: Describing the handling of mismatches during pattern searching.
• Applications: Exploiting KMP for all pattern occurrences.

Additional Algorithms

• Greedy Algorithms: Discuss whether a greedy algorithm can be used to find the optimal solution for the shortest path problem.
• Hash Table: Summarizes linear probing and quadratic probing in hash tables, highlighting their comparative efficiency.

Additional Concepts

• Real World Applications: Explains application, advantages, and disadvantages over other structures.