Graph

Topics	Type	Date & Link	Activity
Terminology, DFS, BFS	Class 2	✅04/29	✅DFS; ✅Graph
BFS, MST, Kruskal	Class 1	✅05/01	✅BFS
Shortest Path	Class 2	✅05/06	✅Djikstra ; ✅Floyd ; ✅MST

BFS: 1 level at a time, explore all adjacent first

• A->B->E->D->C->F->G
• A->E->D->B->F->G->C
  

BFS:

• A->B->D->C->E->F
• A->D->B->C->E->F

Sorting

Topics	Type	Date & Link	Activity
Internal External	Class 1	✅05/08
Insert, Quick, Merge, Heap	Class 2	05/13	✅Heap ; ✅Merge ; ✅Insert ; ✅ Quick:PQ
Heap, Bucket, Radix	Class 1	✅05/15	✅Radix

Stable Sort: Preserve relative order

• Bubble
• Insertion
• Merge

Unstable

• Heap
• Quick

Will effect in multiple key scenario
MSD: K1->K2
LSD: K2->K1 (K2 must be stable sort)

Insertion & Quick

12, 11, 13, 5, 6, 7

Quick and heap are not stable sort

Merge Sort is good for large datasets. Heap sort is good for small datasets that need in-memory search.

Heap

LSD

Summary

External

How to choose?
Understand the characteristic of the dataset
Already sorted => Insertion, avoid quicksort

Hashing

Topics	Type	Date & Link	Activity
External Sort, Hashing Basic	Class 2	✅05/20	✅External ; ✅Hashing
Dynamic, Linear	Class 1	✅05/22	✅Dynamic ; ✅Linear

Increase retrieval
The file blocks are divided into equal-sized buckets

Performance:

• The main reason that collisions and overflows occur in a hash function = The hash function is not distributed uniformly.
• Check which is closer to uniform distribution. -> Hash
• Normal Distribution -> Tree

Dynamic Hashing: Double size of bucket + Double Number of bucket

• Convert to binary rep; pay attention to two digits
• Local Depth <= Global Depth
• Only distribute the component who has overflow problem

In dynamic hashing, what happens when a data bucket overflows?
The hash table is resized, and all keys are rehashed.
Linear Hashing grows one bucket at a time.

Dynamic Hashing => Normal
Linear Hashing => Uniform, Forest Fire, prevention before blocking

Splitting Strategy:

• Controlled Growth: Instead of splitting only when a bucket overflows, Linear Hashing splits buckets in a controlled manner to ensure a balanced and predictable growth of the hash table. The next pointer 𝑁 determines which bucket to split next.
• Incremental Expansion: The hash table expands incrementally by splitting buckets one at a time. This approach ensures that the number of buckets increases gradually, and the rehashing of records happens progressively rather than in large, disruptive steps.
• Uniform Distribution: By splitting buckets sequentially based on the next pointer, Linear Hashing aims to maintain a more uniform distribution of records across buckets. This avoids the problem of having some buckets disproportionately larger than others.

Overflow Handling in Linear Hashing:

• Overflow Mechanism: When a bucket overflows, the overflow records are temporarily handled by creating overflow pages or chaining. However, this is a short-term solution.
• Scheduled Splits: The systematic splitting according to the next pointer eventually catches up with and alleviates the overflows by redistributing records more evenly across the new set of buckets.

Why Not Split Overflowing Pages Directly?

1. Avoiding Rehashing Overhead: If splitting were triggered directly by overflow, it could lead to frequent, unpredictable rehashing, increasing computational overhead and causing performance issues due to the non-uniform expansion.
2. Predictability: The sequential splitting determined by the next pointer provides a predictable pattern of expansion, which is easier to manage and optimize.
3. Consistency in Load Distribution: Directly splitting overflowing pages could result in uneven distribution and uneven load across buckets, as it addresses only localized overflows rather than ensuring a uniform distribution over the entire hash table.

AVL