# Graph
| Topics | Type | Date & Link | Activity |
| ----------------------- | --------- | ----------- | -------- |
| *Terminology, DFS, BFS* | `Class 2` | ✅[04/29](https://365nthu.sharepoint.com/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/stream.aspx?id=%2Fsites%2F2024CS2351DataStructuresbyYi-ShinChen%2FShared%20Documents%2FGeneral%2FRecordings%2F240429_DS_Graph-20240429_101324-Meeting%20Recording%2Emp4&referrer=StreamWebApp%2EWeb&referrerScenario=AddressBarCopied%2Eview%2E2ff6b288-32a8-4d82-af2e-0f9f18d4b1ee) | ✅[DFS](https://365nthu.sharepoint.com/:x:/r/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/Doc2.aspx?action=edit&sourcedoc=%7B66237ce2-a075-43b0-b6b9-211d3c6c8bc2%7D&wdOrigin=TEAMS-WEB.teamsSdk_ns.rwc&wdExp=TEAMS-TREATMENT&wdhostclicktime=1717082887726&web=1); ✅[Graph](https://365nthu.sharepoint.com/:x:/r/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/Doc2.aspx?action=edit&sourcedoc=%7Bdd7e52a0-e4a8-4771-80ff-f01e4132ae33%7D&wdOrigin=TEAMS-WEB.teamsSdk_ns.rwc&wdExp=TEAMS-TREATMENT&wdhostclicktime=1717082892866&web=1)
|*BFS, MST, Kruskal*| `Class 1` | ✅[05/01](https://365nthu.sharepoint.com/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/stream.aspx?id=%2Fsites%2F2024CS2351DataStructuresbyYi-ShinChen%2FShared%20Documents%2FGeneral%2FRecordings%2F240501_DS_Graph-20240501_090455-Meeting%20Recording%2Emp4&referrer=StreamWebApp%2EWeb&referrerScenario=AddressBarCopied%2Eview%2E26bd2499-7b4b-4c7c-9a95-6f6e3a68d2f6) | ✅[BFS](https://365nthu.sharepoint.com/:x:/r/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/Doc2.aspx?action=edit&sourcedoc=%7Bbaadf352-d1cf-484a-b5b1-d192dbf4e4ce%7D&wdOrigin=TEAMS-WEB.teamsSdk_ns.rwc&wdExp=TEAMS-TREATMENT&wdhostclicktime=1717083245108&web=1) |
|*Shortest Path*| `Class 2` | ✅[05/06](https://365nthu.sharepoint.com/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/stream.aspx?id=%2Fsites%2F2024CS2351DataStructuresbyYi-ShinChen%2FShared%20Documents%2FGeneral%2FRecordings%2F240506_DS_Graph-20240506_101535-Meeting%20Recording%2Emp4&referrer=StreamWebApp%2EWeb&referrerScenario=AddressBarCopied%2Eview%2Ec970f8f6-988c-461a-83e8-375af37ddb59) | ✅[Djikstra](https://365nthu.sharepoint.com/:x:/r/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/Doc2.aspx?action=edit&sourcedoc=%7B4c138a95-86c1-479e-9431-cdf8cb1543b9%7D&wdOrigin=TEAMS-WEB.teamsSdk_ns.rwc&wdExp=TEAMS-TREATMENT&wdhostclicktime=1717083255386&web=1) ; ✅[Floyd](https://365nthu.sharepoint.com/:x:/r/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/Doc2.aspx?action=edit&sourcedoc=%7Bf8c7b065-2dbb-4385-a062-3726dbc62fa9%7D&wdOrigin=TEAMS-WEB.teamsSdk_ns.rwc&wdExp=TEAMS-TREATMENT&wdhostclicktime=1717083258868&web=1) ; ✅[MST](https://365nthu.sharepoint.com/:x:/r/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/Doc2.aspx?action=edit&sourcedoc=%7B8afcfac3-ce14-4f5b-886f-422d3b4e9fd3%7D&wdOrigin=TEAMS-WEB.teamsSdk_ns.rwc&wdExp=TEAMS-TREATMENT&wdhostclicktime=1717083262274&web=1)

**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](https://365nthu.sharepoint.com/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/stream.aspx?id=%2Fsites%2F2024CS2351DataStructuresbyYi-ShinChen%2FShared%20Documents%2FGeneral%2FRecordings%2F240513_DS_Sorting-20240513_101524-Meeting%20Recording%2Emp4&referrer=StreamWebApp%2EWeb&referrerScenario=AddressBarCopied%2Eview%2Ea92d98e6-c797-4a42-b6f3-7ac3850fe641) | ✅[Heap](https://docs.google.com/forms/d/e/1FAIpQLSf4zAj4UDjyaU6_NqsfKLrh7bHKTVbqpmMi0hmrLEU2gklLQA/viewform) ; ✅[Merge](https://docs.google.com/forms/d/e/1FAIpQLSdthJ07BfEpsVJm3_oAcwk-p-POMtDwebFwuK9k8dpsn8z8IA/viewform) ; ✅[Insert](https://docs.google.com/forms/d/e/1FAIpQLSfTJoQSq8XSaRd9UlB0xzHKxdrB2xWlvYqmKr7W-lxihKariA/viewform) ; ✅ Quick:PQ |
|*Heap, Bucket, Radix* |`Class 1`| ✅[05/15](https://365nthu.sharepoint.com/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/stream.aspx?id=%2Fsites%2F2024CS2351DataStructuresbyYi-ShinChen%2FShared%20Documents%2FGeneral%2FRecordings%2F240515_DS_Sorting-20240515_090518-Meeting%20Recording%2Emp4&referrer=StreamWebApp%2EWeb&referrerScenario=AddressBarCopied%2Eview%2Ecbfe8630-4f8b-49b1-90ee-159cc8e00b82) | ✅[Radix](https://docs.google.com/forms/d/e/1FAIpQLScw1uyRcxuU_iphnnI3D9FZZOeaQGyWMAwDzy_MMuPUSpeadw/viewform)

:::info
**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**

:::warning
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

:::info
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](https://365nthu.sharepoint.com/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/stream.aspx?id=%2Fsites%2F2024CS2351DataStructuresbyYi-ShinChen%2FShared%20Documents%2FGeneral%2FRecordings%2F240520_DS_Hashing-20240520_101444-Meeting%20Recording%2Emp4&referrer=StreamWebApp%2EWeb&referrerScenario=AddressBarCopied%2Eview%2Eaa34afe5-0b31-4cf3-b921-a1425822ce6f) | ✅[External](https://365nthu.sharepoint.com/:x:/r/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/Doc2.aspx?action=edit&sourcedoc=%7B7332b9d2-0ae3-4f85-9539-64a04cb58494%7D&wdOrigin=TEAMS-WEB.teamsSdk_ns.rwc&wdExp=TEAMS-TREATMENT&wdhostclicktime=1717263330912&web=1) ; ✅[Hashing](https://365nthu.sharepoint.com/:x:/r/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/Doc2.aspx?action=edit&sourcedoc=%7B9f9a102f-7410-464b-bcaa-48e9238bd228%7D&wdOrigin=TEAMS-WEB.teamsSdk_ns.rwc&wdExp=TEAMS-TREATMENT&wdhostclicktime=1717263337147&web=1) |
|*Dynamic, Linear* | `Class 1` | ✅[05/22](https://365nthu.sharepoint.com/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/stream.aspx?id=%2Fsites%2F2024CS2351DataStructuresbyYi-ShinChen%2FShared%20Documents%2FGeneral%2FRecordings%2F240522_DS_Hashing-20240522_090557-Meeting%20Recording%2Emp4&referrer=StreamWebApp%2EWeb&referrerScenario=AddressBarCopied%2Eview%2E19203c2c-c1d2-430b-8033-c97642d89447) | ✅[Dynamic](https://365nthu.sharepoint.com/:x:/r/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/Doc2.aspx?action=edit&sourcedoc=%7Bd8ba8331-2402-4b41-a177-cc0cf80d3dde%7D&wdOrigin=TEAMS-WEB.teamsSdk_ns.rwc&wdExp=TEAMS-TREATMENT&wdhostclicktime=1717263348347&web=1) ; ✅[Linear](https://365nthu.sharepoint.com/:x:/r/sites/2024CS2351DataStructuresbyYi-ShinChen/_layouts/15/Doc2.aspx?action=edit&sourcedoc=%7B8244d1f0-a322-4c48-bd77-61a514e29f6b%7D&wdOrigin=TEAMS-WEB.teamsSdk_ns.rwc&wdExp=TEAMS-TREATMENT&wdhostclicktime=1717263351723&web=1)


:::info
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