This document explains all the uploaded Jupyter Notebook (.ipynb) files step by step.
It is written in
exam / viva-friendly language, focusing on logic, purpose, and flow of code, not just Python syntax.
1️⃣ Assignment1_MedianofMedians.ipynb
📌 Problem Goal
Find the k-th smallest element in an unsorted array using the Median of Medians algorithm, which
guarantees O(n) worst‑case time complexity.
🔹 Core Idea
Instead of choosing a random pivot (like QuickSelect), this algorithm: 1. Divides the array into groups of 5 2.
Finds the median of each group 3. Finds the median of those medians 4. Uses it as a good pivot for
partitioning
This ensures balanced partitioning every time.
🔹 Important Functions
insertion_sort(arr, left, right)
• Used only for small arrays (≤5 elements) • Counts comparisons • Faster than merge/quick sort for tiny
arrays
select_kth(arr, k)
Wrapper function that: • Calls recursive select() • Tracks total comparisons
select(left, right, k)
Main recursive logic: 1. If size ≤ 5 → directly sort and return answer 2. Split array into groups of 5 3. Store
each group’s median 4. Recursively find median of medians 5. Partition array around that pivot 6. Recurse
on left or right side
partition(left, right, pivot)
• Moves elements < pivot to left • Elements > pivot to right • Returns final pivot index
1
🔹 Why It Was Slow Earlier
• Global variables • Repeated modulo loops • Deep recursion • Unnecessary array slicing
✅ Final Result
• Runs fast even for 50,000 elements • Guaranteed O(n) time • Correct comparison counting
2️⃣ LongIntegerMultAssign_2.ipynb
📌 Problem Goal
Multiply very large integers that cannot fit into standard data types using Divide and Conquer.
🔹 Algorithm Used
Karatsuba Multiplication
Instead of 4 multiplications, it uses only 3, reducing complexity.
🔹 Key Idea
For numbers X and Y:
X = a·10ⁿ + b
Y = c·10ⁿ + d
Compute: • ac • bd • (a+b)(c+d)
Final formula:
ac·10²ⁿ + ( (a+b)(c+d) − ac − bd )·10ⁿ + bd
🔹 Important Functions
karatsuba(x, y)
• Base case: single digit multiplication • Splits numbers recursively • Applies Karatsuba formula
2
🔹 Time Complexity
• Naive: O(n²) • Karatsuba: O(n^1.585)
✅ Why This Is Important
• Used in cryptography • Used in big integer libraries • Faster than traditional multiplication
3️⃣ Huffman_Encoding-[Link]
📌 Problem Goal
Compress text using Huffman Coding, a lossless compression algorithm.
🔹 Core Concept
• Characters with higher frequency → shorter codes • Characters with lower frequency → longer codes •
No code is a prefix of another (prefix‑free)
🔹 Important Components
Counter(text)
• Counts frequency of each character efficiently
Node class
• Represents tree nodes • Stores frequency, character, left, right
build_huffman_tree(text)
1. Create min‑heap of nodes
2. Remove two smallest nodes
3. Merge them
4. Repeat until one root remains
generate_codes(root)
• Traverses tree • Left edge → 0 • Right edge → 1 • Stores binary code for each character
3
huffman_encode(text)
• Converts text into binary string
huffman_decode(encoded, root)
• Traverses tree using bits • Reconstructs original text
🔹 Files Used
• [Link] → binary output • [Link] → decoded original text
Example:
Text: aaabbcc
Encoded: 00010101111
🔹 Why Old Version Was Slow
• Character‑by‑character loops • Recursive traversal • No Counter usage
✅ Optimized Version
• Uses heap efficiently • Iterative traversal • Fast even in Python 3.10
4️⃣ OptimalBinary_ST_4.ipynb
📌 Problem Goal
Construct an Optimal Binary Search Tree (OBST) that minimizes expected search cost.
🔹 Inputs
• Keys with successful search probabilities • Dummy keys with unsuccessful search probabilities
🔹 Core Idea
Use Dynamic Programming to minimize:
4
Expected Cost = Σ (probability × depth)
🔹 Tables Used
Cost Table e[i][j]
• Minimum expected cost from key i to j
Weight Table w[i][j]
• Sum of probabilities
Root Table root[i][j]
• Stores root that gives minimum cost
🔹 Algorithm Steps
1. Initialize base cases
2. Compute cost for increasing chain lengths
3. Try every key as root
4. Choose minimum cost root
🔹 Time Complexity
• O(n³) (standard OBST DP)
✅ Why This Matters
• Used in compiler design • Used in databases • Minimizes average search time
🎯 Final Summary Table
Assignment Algorithm Technique
Median of Medians Selection Divide & Conquer
Long Integer Multiplication Karatsuba Divide & Conquer
Huffman Encoding Compression Greedy + Heap
5
Assignment Algorithm Technique
Optimal BST Search Tree Dynamic Programming
If you want: ✔ PDF version ✔ Viva answers ✔ Flow diagrams ✔ Time‑complexity proofs ✔
Handwritten‑style notes
Just tell me what you need next.