Design and Analysis of Algorithms 2026

Lecture 10: QuickSort, Randomization, QuickSelect & Deterministic Selection

1. QuickSort – Core Idea

QuickSort works using:

A partition procedure
A pivot element
Recursive calls on left and right subarrays

Algorithm Structure

If p < r:

Partition the array
Get pivot index q
Recursively sort:
- Left side → p to q-1
- Right side → q+1 to r

2. Partition Procedure (Key Mechanism)

Last element chosen as pivot
All elements ≤ pivot moved to left
All elements > pivot moved to right
Pivot placed in final correct position

Important Observations

Two indices move through array:
- j scans elements
- i tracks boundary of smaller elements
Swap occurs only when needed
Pivot is swapped at the end

Time Complexity of Partition

Always O(n)
Single linear pass
No nested loops

3. Best Case vs Worst Case of QuickSort

Worst Case

Occurs when:

Pivot always smallest or largest element
One side size = n−1
Other side size = 0

Recurrence:
T(n) = T(n−1) + O(n)

Result:

O(n²)

Best Case

Occurs when:

Pivot divides array evenly

Recurrence:
T(n) = 2T(n/2) + O(n)

Result:

O(n log n)

4. What if Partition is Uneven but Not Worst?

Example:

10% on one side
90% on the other side

Recurrence:
T(n) = T(n/10) + T(9n/10) + O(n)

Analysis shows:

Still O(n log n)

Important Insight:
Even moderately unbalanced partitions still give n log n.

5. Randomized QuickSort

Instead of choosing fixed pivot:

Pick random index between p and r
Swap with last element
Run normal partition

Why Randomization?

Avoids consistently bad input cases
Makes worst-case behavior extremely unlikely
Expected time complexity = O(n log n)

6. Randomized Selection (QuickSelect)

Problem

Find the k-th smallest element in an array.

Examples:

k = 1 → smallest element
k = n → largest element
k = n/2 → median

Naive Approach

Sort array → O(n log n)
Then pick k-th element

Too expensive.

QuickSelect Idea

Partition the array
Get pivot index q
Compare k with pivot position

Three Cases

If k = pivot position → Done
If k < pivot position → Recurse on left side
If k > pivot position → Recurse on right side (adjust k)

Important:
Only one recursive call is made.

Worst Case

T(n) = T(n−1) + O(n)

→ O(n²)

Expected Case (Randomized)

T(n) ≈ T(9n/10) + O(n)

Result:

Expected time = O(n)

Major Result:

k-th smallest element can be found in linear time (expected)

7. Understanding Expected Time

Random pivot likely splits reasonably
Probability of extremely bad splits is very small
Uses expectation and probability analysis

Students should revise:

Expectation
Harmonic series
Basic probability

8. Deterministic Selection (Median of Medians)

Goal:
Achieve guaranteed O(n) time (not expected)

Algorithm Idea

Divide array into groups of 5
Sort each group (constant time per group)
Extract medians of each group
Recursively find median of medians
Use that as pivot

Why Groups of 5?

Ensures strong pivot guarantee
Guarantees enough elements eliminated each step
Leads to worst-case linear time

Recurrence

T(n) = T(n/5) + T(7n/10) + O(n)

Result:

O(n)

This is the first deterministic linear-time selection algorithm.

9. Connection to Sorting

If we can:

Find median in O(n)
Partition around it

Then sorting becomes:

T(n) = 2T(n/2) + O(n)

Which gives:

O(n log n)

Lecture 10 - Recording

Lecture 11: Randomized Analysis, Deterministic Selection & Counting Sort

Review of QuickSort and Randomization

QuickSort uses partitioning to divide the array around a pivot element.
Worst case occurs when the pivot splits the array very unevenly (for example: 1 element on one side and the rest on the other side).
Best case occurs when the pivot splits the array roughly in half.

Key observations:

Even if the split is not perfectly balanced (e.g., 25%–75%), the overall complexity remains O(n log n).
Randomization is used to reduce the probability of repeatedly choosing bad pivots.

Randomized Pivot Selection

Instead of always choosing a fixed pivot:

Generate a random index between p and r.
Swap that element with the last element.
Run the normal partition algorithm.

Benefits:

Avoids adversarial input cases.
Makes worst-case behavior extremely unlikely.
Expected running time remains O(n log n).

Handling Duplicate Elements in QuickSort

If the dataset contains many repeated values:

Standard QuickSort may perform poorly because partitions become unbalanced.

Improvement:

Use three-way partitioning:

Elements less than pivot
Elements equal to pivot
Elements greater than pivot

This prevents unnecessary recursive calls on repeated values and significantly improves performance when duplicates exist.

Randomized Selection (Finding the k-th Smallest Element)

Problem:

Find the k-th smallest element in an unsorted array without fully sorting it.

Examples:

k = 1 → smallest element
k = n → largest element
k = n/2 → median

Algorithm idea:

Partition the array.
Check the pivot index.
Recurse only on the side that contains the desired element.

Key property:

Only one recursive branch is explored.

Expected running time:

O(n)

Deterministic Selection (Median of Medians)

Goal:

Guarantee linear time selection without randomness.

Main idea:

Divide the array into groups of 5 elements.
Sort each small group.
Extract the median of each group.
Recursively find the median of those medians.
Use that value as the pivot.

Important property:

This pivot guarantees that a significant fraction of elements are discarded each step.

Worst-case recurrence:

T(n) = T(n/5) + T(7n/10) + O(n)

Result:

O(n) deterministic time.

Prune and Search Technique

Median-of-medians follows a strategy called Prune and Search.

Steps:

Perform some preprocessing in linear time.
Discard a large fraction of the input.
Recursively solve the smaller problem.

Because the problem size shrinks geometrically, the total time remains linear.

Lower Bound of Comparison Sorting

Previously shown:

Any comparison-based sorting algorithm requires at least:

Ω(n log n) comparisons.

However, if additional information about the data range is known, faster sorting may be possible.

Counting Sort

If the values lie within a known range (for example 1 to n):

Sorting can be done without comparisons.

Algorithm steps:

Create a count array to store frequency of each value.
Compute prefix sums to determine final positions.
Build the output array using these positions.

Key properties:

Time complexity: O(n + k)
(where k is the range of values)
Stable sorting algorithm.

Prefix Sum (Accumulation Technique)

The prefix sum step transforms the count array into cumulative counts.

This allows us to determine:

How many elements are ≤ a given value.
The exact final index where each element should be placed.

This idea is also useful in many problems such as range queries and frequency analysis.

Lecture 11 - Recording

Lecture 12: 2D Maxima & Skyline Problem

2D Domination — Definition

A point P dominates point Q if P.x > Q.x and P.y > Q.y
In 1D, domination is simple — larger value wins
In 2D, if one point is larger in X but smaller in Y, neither dominates the other — they are incomparable

2D Maxima — Problem Statement

Given n points in 2D, find all maximal points
A point is maximal if no other point dominates it
Maximal points form a staircase shape when visualized

Brute Force — O(n²) Approach

For each point, compare it against every other point
If no point dominates it, add it to the solution set
Sort the solution set to reconstruct the staircase line
Simple but inefficient for large inputs

Divide & Conquer — O(n log n) Approach

Find the median X-coordinate using Randomized Select — O(n)
Partition points into left and right halves — O(n)
Recursively compute maxima for both halves
Merge step: Right-side maxima are always included; left-side points are kept only if their Y-value is greater than the leftmost Y of right maxima
Recurrence: T(n) = 2T(n/2) + O(n) → solves to O(n log n)

Sweep Line Algorithm — O(n log n) / O(n) if pre-sorted

Sort points by X-coordinate, then sweep a vertical line left to right
Maintain a running solution set (staircase)
When a new point arrives, remove all previous points with smaller Y (they are now dominated)
Amortized analysis shows total cost is O(n) after sorting
Right-to-left variant is cleaner — rightmost point is always maximal; only compare Y-values going backward

Skyline Problem — Real-World Application

Used in fighter jets, satellite imagery, radar systems
Each building is represented as: (x_start, x_end, height)
Goal: Compute the visible skyline silhouette from a set of overlapping buildings
Differs from 2D Maxima — buildings have width, so points cannot simply be deleted when a building ends

Skyline — Sweep Line with Multimap

Convert each building into two events: (x_start, +height) and (x_end, −height)
Sort all events by X
Use a Multimap / Multiset (backed by AVL tree) to track active building heights
On start event → insert height; on end event → delete height
Current maximum height in the map defines the skyline at that X
Each insertion/deletion costs O(log n) → Total: O(n log n)

Skyline — Divide & Conquer Approach

Divide buildings into two halves
Recursively compute skyline for each half
Merge the two skylines by taking the maximum height at each X-coordinate
Merge step runs in O(n) → Recurrence solves to O(n log n)

Lecture 12 Recording

Lecture 13: Sorting Lower Bound, Counting Sort, Radix Sort & Bucket Sort

Lower Bound of Comparison-Based Sorting — Ω(n log n)

Any comparison-based sorting algorithm must make at least Ω(n log n) comparisons
An array of n elements has n! possible arrangements; sorting means finding one specific ordering
This is modeled as a decision tree — every algorithm must traverse its height
Height is minimized when the tree is balanced → minimum height = log(n!) ≈ n log n
Proof: lower half of the sum log(n!) is bounded below by n/2 × log(n/2), which gives Ω(n log n)

Counting Sort — O(n + k)

Works only when element values fall within a known range [1, k]
Does not contradict the Ω(n log n) lower bound — it exploits range information, not comparisons
Steps: build a frequency (counts) array C of size k, then compute prefix sums (cumulation)
After cumulation, C[i] tells the last valid position in output array B for value i
Traverse input array A in reverse order, place each element at C[A[i]], then decrement C[A[i]]
Reverse traversal is what makes it a stable sort — equal keys retain their original order
Complexity: O(n + k); if k >> n, performance degrades significantly

Stability in Sorting Algorithms

A sort is stable if equal-key records maintain their original relative order
Counting Sort is stable — due to reverse traversal
Bubble Sort is stable — equal elements are never swapped
Insertion Sort and Merge Sort are also stable
Selection Sort and QuickSort are not stable by default
Exam note: Reversing the traversal direction in Counting Sort removes stability

Radix Sort — O(d × (n + k))

Sorts integers by processing one digit at a time, from least significant to most significant
Each pass uses a stable sort (Counting Sort) on digits 0–9
The digit range is always [0, 9] regardless of number size — so k = 10 per pass
Total complexity: O(d × n) where d = number of digits per number
This is not comparison-based — it compares digits, not full numbers
If numbers have d = log n digits, complexity approaches O(n log n); if d = n, it becomes O(n²)
Application: sorting dates — first by day, then month, then year (least to most significant)

Sorting n Numbers in Range [0, n²−1] in Linear Time

Counting Sort fails here — k = n² means O(n²) space and time
Solution: represent each number as a pair (quotient, remainder) by dividing by n
Both quotient and remainder fall in [0, n−1] — a manageable range
Apply Radix Sort: first sort by remainder, then by quotient (stable sort each pass)
Total complexity: 2 × O(n + n) = O(n) — linear time achieved

Bucket Sort — Expected O(n)

Designed for floating-point numbers uniformly distributed in [0, 1)
Create n buckets, each representing a sub-interval of [0, 1)
Each element a[i] goes into bucket ⌊n × a[i]⌋ and is inserted in sorted order within that bucket
After all insertions, concatenate all buckets into final sorted array
Insertion into a bucket costs O(size of bucket); merging all buckets costs O(n)
Expected time is O(n) due to uniform distribution — few collisions per bucket
Stability requires inserting at the end (or traversing in reverse for the final pass)

Lecture 13 Recording

Lecture 14: Randomized Algorithms - Hiring Problem and Randomized Quicksort

Random Variable, Expectation, PDF, Indicator Random Variable
Hiring Problem
1. - Randomizing an array of n size
  - Its analysis
    1. - Harmonic Series
        Its lower bound
        Its upper bound
Analysis of Randomized Quicksort
1. - Its analysis
  - The discussion on the variance of Randomized QuickSort i.e. O(n) and what is the meaning its repurcussion with
    1. - ChevbeChev relationship

Lecture 14 Recording

Lecture 15: Graph Theory — Introduction, Representations & Depth First Search

Historical Motivation — The Königsberg Bridge Problem

Euler (1700s) posed the famous Königsberg Bridge Problem: can you cross every bridge exactly once and return to your starting point?
He modeled land regions as vertices and bridges as edges — inventing the field of Graph Theory
This path (visiting every edge exactly once) is called an Eulerian Path
Graph Theory was dismissed as mathematics for ~50 years before becoming the core of Computer Science

What is a Graph?

A graph G consists of V (vertices) and E (edges)
Vertices represent entities (regions, users, locations); edges represent connections between them
A maze, a social network, a city map — all are naturally modeled as graphs
Graphs allow compact representation: instead of storing infinite spatial points, store only meaningful connections

Directed vs Undirected Graphs

Undirected graph: edges are bidirectional — if A connects to B, B connects to A (e.g., Facebook friendships)
Directed graph: edges have direction — a connection from A to B does not imply B to A (e.g., Twitter follows)
Adjacency matrix of an undirected graph is always symmetric

Graph Representations

Adjacency Matrix:

An n × n matrix where entry (i, j) = 1 if an edge exists between vertex i and j
Space complexity: O(n²)
Checking if an edge exists: O(1)
Finding all neighbors of a vertex: O(n) — must scan entire row

Adjacency List:

An array/hash table where each entry points to a linked list of neighbors
Space complexity: O(n + E)
Finding all neighbors: O(degree of vertex)
Far more memory-efficient for sparse graphs

Facebook vs Twitter — Real World Design

Facebook's friendship graph has ~2 billion users; storing it as an adjacency matrix requires ~4 × 10¹⁸ bytes — completely infeasible
Adjacency list reduces this to roughly 2 billion × average friends (~200) — fits on a single hard drive
Key operations and their costs in adjacency list representation:
- Add friend: O(1) — insert at front of both lists
- Remove friend: O(degree of i + degree of j) — must search the list
- New user sign-up: O(n) — vector resizing; use a hash table to reduce this
- Delete account: O(n) — requires rebuilding matrix in adjacency matrix form
Twitter is a directed graph — following is one-way; Facebook friendship is undirected

Connected Components

A connected component is a maximal subset of vertices where every pair has a path between them — like isolated islands in the graph
Goal: precompute connected component numbers (CCN) for all vertices so that reachability queries can be answered in O(1)
Query: given vertices i and j, are they reachable from each other? → simply check if CCN[i] == CCN[j]

Depth First Search (DFS)

DFS explores a graph by going as deep as possible before backtracking — analogous to in-order tree traversal (LRN)
Each vertex stores: visited (boolean), ccn (component number), clock_begin, clock_end
The visited flag prevents infinite loops in cyclic graphs

DFS Algorithm:

Initialize all vertices as visited = false, ccn = -1
For each unvisited vertex, call explore(v, cn)
Inside explore: mark visited → assign pre-clock → recursively explore unvisited neighbors → assign post-clock
A global clock counter increments on every pre/post visit
A global cn counter increments each time a new component starts

Computing Connected Components via DFS

Pass a component number cn into each explore call
Assign v.ccn = cn when a vertex is first visited
All vertices reachable within one DFS call share the same CCN
Increment cn only when starting a fresh explore from the outer loop — each fresh call = new component
Total time complexity: O(n + E) — linear in input size

Lecture 15 Recording

Lecture 16: DFS Applications — Edge Classification, DAGs & Topological Sort

Recap — Graph Representations

A graph G = (V, E): vertices represent entities, edges represent connections
Adjacency Matrix: O(n²) space; edge existence check in O(1); listing neighbors in O(n)
Adjacency List: O(V + E) space; edge existence in O(degree); listing neighbors in O(degree)
Use adjacency matrix when the graph is dense; adjacency list when it is sparse
DFS on adjacency list runs in O(V + E); on adjacency matrix in O(V²)

DFS with Parent Tracking — Path Finding

CLRS implementation assigns each vertex: discovery time (d), finish time (f), color, and parent (π)
Colors: White = unvisited, Grey = in progress, Black = fully explored
When exploring vertex u's neighbor v, set v.parent = u before the recursive call
After DFS from a source vertex, backtracking through parent pointers reconstructs the path from source to any reachable vertex
If a vertex has no parent assigned, no path exists from the source
Note: DFS paths are not necessarily shortest paths

Edge Classification in Directed Graphs

When DFS runs on a directed graph, every edge falls into one of four types:

Tree edges: edges actually used during DFS traversal — form the DFS forest
Back edges: edges pointing from a vertex to one of its ancestors — indicate a cycle
Forward edges: edges pointing to an already-fully-explored descendant — shortcut in the tree
Cross edges: edges between vertices in disjoint DFS subtrees — neither ancestor nor descendant

Detection using clock intervals:

Back edge: the destination's interval contains the source's interval
Cross edge: the two intervals are completely disjoint
Forward edge: the source's interval contains the destination's interval

Directed Acyclic Graphs (DAGs)

A DAG is a directed graph with no cycles
A linked list is a simple example of a DAG
Prerequisite course structures are DAGs — a cycle would make a degree impossible to complete
Maximum edges in a DAG with n vertices without creating a cycle: O(n²) — specifically n(n−1)/2
Every DAG must contain at least one source (no incoming edges) and one sink (no outgoing edges)

Finding Source and Sink Vertices

Using adjacency matrix:

Source: find a column that is all zeros → O(V²)
Sink: find a row that is all zeros → O(V²)

Using adjacency list:

Naive approach: for each vertex, check if it appears in any other vertex's list → O(V × (V + E))
Better approach: mark all vertices that appear as destinations; any unmarked vertex is a source → O(V + E)

Using DFS clock — elegant approach:

Run one DFS on the graph → vertex with maximum finish time is the source
Compute the reverse graph (transpose: swap all edge directions) → costs O(V + E)
Run DFS on reversed graph → vertex with maximum finish time in reversed graph is the sink of original
Total cost: O(V + E)

Topological Sort

Given a DAG with dependency constraints, find a valid linear ordering of vertices such that for every edge u → v, u comes before v
Real-world examples: course prerequisites, build systems, construction task scheduling, getting dressed in order

Algorithm — DFS-based Topological Sort:

Run DFS on the entire graph, computing finish times
As each vertex finishes, insert it at the front of a linked list
The final linked list gives the topological order
Total time: O(V + E) — a single DFS pass

Why it works:

Vertices that finish last are sources (no dependencies) — they go to the front
Vertices that finish first are sinks — they go to the back
The reverse finishing order naturally encodes the dependency ordering

Minimum Steps Topological Execution

To find the minimum number of steps (parallel stages) to complete all tasks:
- Find all current source vertices — these can be executed simultaneously in one step
- Remove them and their edges, then repeat
This is equivalent to finding the longest path in the DAG
Useful for: minimum semesters to complete a degree, parallel task scheduling

Lecture 16 Recording

Lecture 17: BFS, Shortest Paths & Strongly Connected Components

Recap — DFS & Topological Sort

DFS uses pre-visit (assign values before exploring children) and post-visit (assign values after all descendants finish)
Pre-visit is useful for passing information downward (e.g., parent pointers, distance from source, component numbers)
Post-visit is useful for computing values that depend on descendants (e.g., subtree heights, topological finish times)
Topological Sort: run DFS, insert each vertex at the front of a linked list when its finish time is computed → result is a valid dependency ordering in O(V + E)
Source vertex of a DAG always has the maximum finish time in DFS

Breadth First Search (BFS) — Ripple Effect

BFS is inspired by the ripple effect in water — all points on the same ring are equidistant from the center
Start by inserting the source vertex into a queue
Repeatedly dequeue a vertex, then enqueue all its unvisited neighbors
Vertices are colored: White = unvisited, Grey = in queue, Black = fully processed
Grey color prevents a vertex from being inserted into the queue twice — avoids duplicate processing
Continue until the queue is empty

CLRS Implementation:

Initialize all vertices: color = White, distance = ∞, parent = Nil
Set source: color = Grey, distance = 0, parent = Nil
Enqueue source, then process until queue is empty
For each dequeued vertex u, visit white neighbors v: set v.color = Grey, v.distance = u.distance + 1, v.parent = u, enqueue v
After processing u: set u.color = Black

BFS vs DFS for Shortest Paths

DFS can go arbitrarily deep in the wrong direction — not guaranteed to find shortest path
BFS expands layer by layer: first all vertices at distance 1, then distance 2, then distance 3, and so on
BFS always computes shortest paths from the source to every reachable vertex
Parent pointers set during BFS enable backtracking to reconstruct the full shortest path
Time complexity: O(V + E) — same as DFS

Grid Graphs — BFS Application

A grid graph stores only the grid values (V cells); edges are computed on the fly from neighbor coordinates
Neighbors of cell (i, j) are up to 8 surrounding cells — no need to store adjacency lists explicitly
BFS on a grid finds the shortest path from a source cell to a target cell
Parent pointers serve double duty as visited markers — if a cell's parent is set, it has been visited

Variants of the grid path problem:

Single source (e.g., person at position 2) to single target (e.g., bunker at position 3)
Multiple sources to multiple targets — naive approach costs O(n × (V + E))
Optimal approach: to find nearest target for every source in O(V + E) — this is a midterm exam question

Strongly Connected Components (SCCs)

Definition:

A subset S of a directed graph G is a Strongly Connected Component if for every pair of vertices u, v ∈ S, both a u → v path and a v → u path exist
A single vertex is always its own SCC
A simple linked list has n SCCs (one per node)
A cyclic linked list has exactly 1 SCC

Key observations:

If an SCC is "shrunk" to a single node, the resulting meta-graph is always a DAG
The reverse graph G^R has the same SCCs as the original G
The source SCC of G^R corresponds to the sink SCC of G

Kosaraju's Algorithm — Finding All SCCs

Algorithm:

Compute the reverse graph G^R
Run DFS on G^R to compute finish times (topological ordering)
Process vertices in decreasing finish time order, running explore on the original graph G
Each new explore call that starts a fresh component identifies a new SCC

Why it works:

The vertex with the highest finish time in G^R corresponds to a sink SCC of G
Running explore on the original G from that vertex visits only that SCC — edges out of it lead to already-visited vertices
Repeating this process peels off one SCC at a time in sink-to-source order

Time complexity: O(V + E)

O(V + E) to compute G^R
O(V + E) to run DFS on G^R for ordering
O(V + E) to run explore calls on G

Lecture 17 Recording

Lecture 18: Graph Traversals, DAG Properties & Shortest Paths

Review of Graph Basics & DFS

The lecture begins with a recap of reachability in graphs and how graphs are represented.
Focus on checking:
- Whether a path exists between two vertices
- Whether a direct edge exists
Depth First Search (DFS) is introduced as a key traversal method.
DFS explores nodes recursively:
- Mark node as visited
- Store pre-visit (start time)
- Explore all neighbors recursively
DFS helps in:
- Traversing the graph
- Extracting connected components
- Finding paths using parent tracking

Connected Components using DFS

A single DFS call explores one connected component.
To find all components:
- Run DFS on all unvisited vertices
Each DFS tree corresponds to a separate component.

Directed Acyclic Graphs (DAGs)

A DAG has no cycles.
Important properties:
- At least one source vertex (no incoming edges)
- At least one sink vertex (no outgoing edges)
Using DFS:
- The node with the largest finishing time is always a source

Graph Reversal Insight

Reversing a graph flips all edges.
Key idea:
- Sources become sinks
- Sinks become sources
Useful for advanced graph algorithms

Universal Sink Problem

A universal sink:
- In-degree = n−1
- Out-degree = 0
Naive approach:
- Check full matrix → O(n²)
Optimized approach:
- Eliminate candidates using row/column checks
- Achieve O(n) solution without scanning full matrix

Topological Sorting

Applicable only for DAGs
Used for dependency resolution
Key property:
- All edges go forward in ordering
Efficient method:
- Use DFS finishing times
- Insert nodes in reverse finish order
No explicit sorting required

Strongly Connected Components (SCC)

In directed graphs:
- u and v are strongly connected if:
  - u → v and v → u paths exist
If SCCs are compressed into single nodes:
- The resulting graph becomes a DAG

Kosaraju’s Algorithm (SCC)

Steps:
1. Run DFS and store finishing order
2. Reverse the graph
3. Run DFS in decreasing finish time order
Each DFS call gives one SCC
Efficient and widely used method

Breadth First Search (BFS)

Works in levels (layers)
Explores:
- Distance 1 → Distance 2 → Distance 3 …
Guarantees:
- Shortest path in unweighted graphs
Supports:
- Multi-source shortest paths by initializing queue with multiple nodes

Weighted Graphs & Shortest Path Problem

Edges can have weights (costs)
Goal:
- Minimize total cost from source to all vertices

From BFS to Dijkstra

BFS fails for weighted graphs
Idea evolution:
- Convert weights → multiple nodes (inefficient)
- Use alarm clock idea (priority-based processing)

Dijkstra’s Algorithm

Maintains:
- Distance array
- Parent pointers (for path reconstruction)
Uses:
- Min-Heap / Priority Queue
Process:
- Always pick node with smallest distance
- Relax its edges

Relaxation Concept

If a shorter path is found:
- Update distance
- Update parent
Core operation in shortest path algorithms

Time Complexity

Using heap:
- O((V + E) log V)

Limitation of Dijkstra

Fails with negative edge weights
Because:
- Once a node is processed, it is never revisited
- Negative edges can produce better paths later

Lecture 18 Recording

Lecture 19: Advanced Shortest Paths, Negative Weights & Bellman-Ford

Final Review of Graph Concepts

Lecture starts with a recap of:
- Graph representation (Adjacency Matrix vs List)
- DFS traversal and its applications
Important note:
- Time complexity of DFS = O(V + E)

DFS Applications (Quick Recap)

Connected Components
Source & Sink detection in DAG
Topological Sorting
Strongly Connected Components (SCC)

Flood Fill Concept (DFS Application)

Real-world analogy:
- MS Paint fill tool
- Minesweeper expansion
Idea:
- Start from a node and recursively fill all connected same-type neighbors
This is essentially DFS in disguise

BFS Recap

Works level-by-level (layered expansion)
Used for:
- Shortest path in unweighted graphs
Uses queue and guarantees minimum edges path

Weighted Graphs

Real-world graphs are always weighted
- Time, cost, fuel, distance, etc.
Key point:
- Weights are on edges, not nodes

Representing Weighted Graphs

Adjacency Matrix
- Store weight instead of 1
Adjacency List
- Store pairs: (neighbor, weight)

Why BFS Fails for Weighted Graphs

Trick:
- Convert weight into multiple dummy nodes
Problem:
- Extremely inefficient for large weights

Dijkstra’s Algorithm (Revisited)

Core Idea:

Use priority queue (min-heap)
Always process node with smallest distance

Key Operations:

Initialize:
- Distance = ∞
- Source distance = 0
Use Relaxation:
- Update distance if shorter path found

Complexity:

O((V + E) log V)

Limitation of Dijkstra

Does NOT work with negative edges

Why?

Once a node is removed from heap:
- It is never revisited
Negative edge may later produce a shorter path

Negative Edge Problem

Example insight:
- Later relaxation may improve already finalized node
This breaks Dijkstra’s correctness

Bellman-Ford Algorithm (Core of Lecture)

Key Idea:

Instead of greedy selection:
- Relax ALL edges repeatedly

Algorithm Steps

Initialize:
- Distance[source] = 0
- Others = ∞
Repeat (V - 1) times:
- For every edge (u → v):
  - Relax it

Because:

Maximum edges in shortest path = V - 1

Relaxation Rule

If:

- dist[u] + weight(u,v) < dist[v]

Then:

Update dist[v]
Set parent[v] = u

Time Complexity

O(V × E)

Negative Cycle Problem

Definition:

Cycle whose total weight < 0

Problem:

You can loop infinitely and reduce cost

So:

Shortest path does NOT exist

Detecting Negative Cycles

Run Bellman-Ford one extra iteration
If any value still updates:
- Negative cycle exists

DAG Shortest Path Optimization

If graph is DAG:

Do Topological Sort
Process nodes in that order
Relax edges once

Complexity:

O(V + E) (much faster than Bellman-Ford)

Longest Path in DAG

Modify relaxation:
- Use max instead of min
Works only in DAG

Important Insight

General Graph:
- Shortest path → Easy
- Longest path → Hard (NP-complete)
DAG:
- Both shortest and longest path → Efficient

Real-World Applications

GPS navigation (weighted shortest paths)
Network routing
Game scoring (negative edges = rewards)
Scheduling with dependencies
GIS systems & grid graphs

Lecture 19 Recording

Lecture 20: Advanced Shortest Paths, Negative Weights & Bellman-Ford

1. Motivation: Why do we care?

Goal: Multiply two polynomials fast
Naive method:
- Time = O(n²)
Problem:
- Too slow for large inputs (especially in AI / CNNs)

Key insight from lecture:

Convolution = Polynomial Multiplication
CNNs heavily rely on convolution → we MUST optimize this

2. Key Idea of the Lecture

Instead of multiplying directly:

Strategy:

Convert polynomial from coefficient form → sample form
Multiply in sample form (cheap)
Convert back to coefficient form

3. Polynomial Representations

(A) Coefficient Form

Example:

P(x) = 2 + 3x + 4x² - 5x³

Stored as:

[2, 3, 4, -5]

Multiplication cost → O(n²)

(B) Sample Form (Important!)

Represent polynomial using points:

(x₁, y₁), (x₂, y₂), ..., (xₙ, yₙ)

Key property:

n distinct points uniquely define polynomial

4. Why Sample Form is Powerful

Multiplication becomes:

C(xi) = A(xi) * B(xi)

Just multiply y-values:

Time = O(n)

Addition also:

C(xi) = A(xi) + B(xi)

Time = O(n)

5. The Real Problem

We need:

Coefficient → Sample (forward transform)
Sample → Coefficient (inverse transform)

Naive way:

Uses Vandermonde matrix
Cost = O(n²)

6. Target Goal

We want:

Conversion in O(n log n)

That’s exactly what FFT does

7. Full Optimized Pipeline

A(x), B(x) (coefficient form)
Convert to sample form (FFT)
Point-wise multiplication (O(n))
Convert back (Inverse FFT)

Total Complexity:

O(n log n)

8. Key Insight: Divide & Conquer Trick

The lecture introduces the core FFT trick:

Split polynomial into:

Even indices
Odd indices

A(x) = A_even(x²) + x * A_odd(x²)

This reduces problem size from n → n/2

9. Why this helps

Instead of computing directly:

Solve smaller subproblems
Combine results

This leads to recurrence:

T(n) = 2T(n/2) + O(n)

Result:

T(n) = O(n log n)

10. Important Concept: Evaluation Trick

Instead of evaluating full polynomial:

You compute:

A_even(x²)
A_odd(x²)

Then combine:

A(x) = A_even(x²) + x * A_odd(x²)

This is the core recursive idea of FFT

11. Important Insight from Lecture

Polynomial evaluation at one point:
- O(n) using Horner’s Rule
But we need:
- Evaluation at n points efficiently

FFT solves this smartly using special points (roots of unity — next lecture)

12. Complexity Comparison

Method Time

Naive multiplication O(n²)

Better algorithms O(n^(1+ε))

FFT O(n log n)

13. Important Theoretical Insight

Even if ε is very small:
- n^(1+ε) is still slower than n log n

So:

n log n < n^(1+ε)

14. Big Picture (Very Important)

This lecture builds:

Bridge between:

Algebra (polynomials)
Signals (convolution)
AI (CNNs)

15. Where this is used

Deep Learning (Convolutions)
Image Processing
Audio Processing
Signal Processing
Large integer multiplication

Lecture 20 Recording

Lecture 21: Dynamic Programming (DP) + Memoization

1. Starting Point: Problem with Recursion

Lecture starts with this idea:

We write a recursive solution
But it becomes very slow

Why?

Because of:
Repeated computations

Example (Catalan / Fibonacci-like):

Same values are recomputed again and again
Leads to exponential time

Key idea from lecture:

“Same subproblems are solved multiple times”

2. Core Idea Introduced

Avoid recomputation

Two ways:

(A) Memoization (Top-Down)

(B) Tabulation / DP (Bottom-Up)

3. Example 1: Catalan Numbers

Definition

Catalan numbers follow:

C(n+1) = Σ [ C(i) * C(n - i) ]
i = 0 to n

First Few Values

C0 = 1
C1 = 1
C2 = 2
C3 = 5
C4 = 14

Important Insight

To compute:

C5 → need C0, C1, C2, C3, C4

Meaning:

“To compute one value, you need all previous values”

Problem with Naive Recursion

Calls explode like a tree
Same values recomputed again and again

Time Complexity:

Exponential

4. Solution 1: Memoization (Top-Down DP)

Idea

Store already computed values in an array

Before computing, check:
if value exists → return it

Pattern

if(dp[n] != -1)

return dp[n];

dp[n] = compute(...);

return dp[n];

Key Insight

Recursion still exists, but repeated calls become table lookups

Result

Time reduces from exponential → O(n²) (for Catalan)

5. Important Implementation Detail

MUST pass array by reference

Otherwise:

Every recursive call gets a new copy
Memoization fails

Lecture explicitly warns about this

6. Solution 2: Bottom-Up DP (Tabulation)

Idea

Instead of recursion:

Build solution from smallest → largest

Approach

dp[0] = 1

for i = 1 to n:

dp[i] = 0

for j = 0 to i-1:

dp[i] += dp[j] * dp[i-1-j]

Key Insight

“No recursion at all”
“Everything is computed in order”

Complexity

Time = O(n²)

7. Big Concept: What is DP?

Definition (from lecture idea)

DP =
Solve problem by:

Breaking into subproblems
Storing results
Reusing them

Key Pattern

1. Identify subproblems
2. Find recurrence
3. Store results
4. Build solution

8. Example 2: Tiling Problem

Problem

Tile a 2 × n floor using:

2×1 vertical tiles
1×2 horizontal tiles

Recurrence

Look at last column:

Case 1:

Vertical tile → remaining:

2 × (n-1)

Case 2:

Two horizontal tiles → remaining:

2 × (n-2)

Final Formula

f(n) = f(n-1) + f(n-2)

This is Fibonacci 👀

Insight

Many DP problems are hidden Fibonacci-type problems

9. Recognizing DP Problems

Signs:

Overlapping subproblems
Recursive structure
Exponential recursion
Same values computed repeatedly

10. Top-Down vs Bottom-Up

Approach Idea

Memoization Recursion + cache

Tabulation Iterative build

11. Key Insight from Lecture

Almost 40% programming problems = DP

If your solution gives TLE → probably needs DP

12. Deep Concept Link

Lecture connects:

DP problems
→ can be seen as
Path problems in DAGs

13. Big Picture

Lecture 21 teaches:

Why recursion fails
How to optimize it
How to think in DP

Lecture 21 Recording

Lecture 22: Core Ideas

1. Maximum Sum Subarray (Kadane’s Algorithm)

Original Problem

Given an array → find subarray with maximum sum

Smart Trick (VERY IMPORTANT)

Instead of solving directly, lecture changes the problem:

Define:

dp[i] = max sum of subarray ending at index i

Why this works?

Because:

“Every optimal subarray must end somewhere”

So:

Compute answer for every index
Take maximum of all

Recurrence (MOST IMPORTANT)

At index i, two choices:

1. Extend previous subarray
2. Start new from i

So:

dp[i] = max(arr[i], dp[i-1] + arr[i])

Intuition

If previous sum is negative → discard it
If positive → extend it

Final Answer

max(dp[i]) over all i

Optimized Version (Kadane)

max_ending_here = arr[0]
max_so_far = arr[0]
for i = 1 → n:
max_ending_here = max(arr[i], max_ending_here + arr[i])
max_so_far = max(max_so_far, max_ending_here)

Time Complexity

O(n) (BEST POSSIBLE)

2. Longest Increasing Subsequence (LIS)

Problem

Find longest subsequence where:

a[i1] < a[i2] < a[i3] ...

Same DP Pattern

Define:

dp[j] = length of LIS ending at index j

Recurrence

Look at all previous elements:

dp[j] = max(dp[i] + 1) for all i < j where arr[i] < arr[j]

Code Idea

for j = 0 → n:

dp[j] = 1

for i = 0 → j-1:

if arr[i] < arr[j]:

dp[j] = max(dp[j], dp[i] + 1)

Final Answer

max(dp[j])

Key Insight

Only look backwards, never forward

Parent Trick (VERY IMPORTANT)

To reconstruct sequence:

Store:

parent[j] = index from which dp[j] came

Then:

Start from max index
Trace back using parent array

Time Complexity

O(n²)

Deep Insight from Lecture

LIS can be converted to a graph problem (DAG)

Nodes = indices

Edge: i → j if
i < j AND arr[i] < arr[j]

Then problem becomes:

Find LONGEST PATH in DAG

3. Rod Cutting Problem

Problem

You have a rod of length n

You can cut it into pieces
Each length has a price

Maximize profit

Example Thinking

You can cut like:

1 + (n-1)
2 + (n-2)
3 + (n-3)
...

Recurrence

dp[n] = max(

price[i] + dp[n - i]

) for all i = 1 → n

Key Insight

Try all possible first cuts

Time Complexity

O(n²)

4. BIG PATTERN (MOST IMPORTANT)

Lecture 22 is actually teaching ONE idea repeatedly:

Universal DP Pattern

1. Redefine problem → "ending at i"
2. Build recurrence using previous states
3. Compute for all i
4. Take global max

You saw this in:

Problem dp meaning

Max Subarray sum ending at i

LIS length ending at i

Rod Cutting best profit for length n

5. Very Important Concept

DP = Local → Global

Solve local optimal at each index
Combine → get global solution

6. Complexity Journey (from lecture)

Max Subarray:

O(n⁴) → O(n³) → O(n²) → O(n) (Kadane)

Lecture 22 Recording

Lecture 23: Dynamic Programming — Rod Cutting, Grid Paths & Edit Distance

Rod Cutting Problem — Problem Statement

Given a rod of length n and a price table p[i] (profit for selling a piece of length i), find the cutting strategy that maximizes total profit
Two outputs required: the maximum profit and the exact cut lengths used
Example: for a rod of length 4, selling two pieces of length 2 each (profit 10) beats selling the whole rod (profit 9)

Recursive Solution — O(2ⁿ)

At each step, try all possible first cuts of length i (1 ≤ i ≤ n), then recursively solve the remaining rod of length n - i
The recurrence: R(n) = max over i of { p[i] + R(n - i) }
Base case: R(0) = 0
This generates every possible binary partitioning of the rod — 2ⁿ total subproblems
Subproblems repeat massively — e.g., R(2) is computed from many different paths

Memoization — Top-Down DP

Allocate an array revenue[0..n], initialize all to -1, set revenue[0] = 0
Before computing, check if revenue[n] ≥ 0 — if yes, return cached result immediately
Otherwise compute normally and store result before returning
Reduces complexity from O(2ⁿ) to O(n²)

Bottom-Up DP — O(n²)

Build solutions from smaller subproblems upward: compute R(1), R(2), ..., R(n) in order
For each length j, try all first cuts i from 1 to j: R(j) = max(p[i] + R(j-i))
Since all smaller values are already computed, no recursion needed — pure table lookup
Space: O(n) for the revenue table

Recovering the actual cuts (bookkeeping):

Maintain a separate array S where S[j] stores the first cut length that achieved the maximum for rod of length j
To reconstruct: go to S[n], record that cut, subtract it from n, repeat until n = 0
This is equivalent to following parent pointers in a DAG

2D Grid — Longest/Shortest Path with DP

Given an n × n grid where edges go right, down, or diagonally right-down
This grid is a DAG — no cycles possible given edge directions
Goal: find the longest (or shortest) weighted path from top-left (S) to bottom-right (T)
Recurrence: LP(i,j) = max(LP(i-1,j) + w_up, LP(i,j-1) + w_left, LP(i-1,j-1) + w_diag)
Base case: the top row and left column are filled from the source outward
DP fills the matrix row by row — each cell needs only its left, above, and diagonal-above-left neighbors
Time: O(n²) — a single sweep; Space: O(n) if only one previous row is kept (since each row depends only on the row above)
To find shortest path: replace max with min — no other change needed

Edit Distance Problem

Given two words of lengths m and n, find the minimum number of edits (insertions, deletions, substitutions) to transform one into the other
Alignment cost: matching characters → cost 0; mismatch or gap → cost 1
Applications: autocorrect (suggest closest dictionary word), DNA/gene sequence matching, forensic fingerprint comparison

Recurrence — E(i, j) = minimum edit distance between first i characters of word 1 and first j characters of word 2:

E(i, j) = min(1 + E(i-1, j), 1 + E(i, j-1), diff(i,j) + E(i-1, j-1))
Where diff(i,j) = 0 if characters match, 1 if they don't
Base cases: E(i, 0) = i and E(0, j) = j

Bottom-Up DP:

Build an (m+1) × (n+1) matrix
Initialize row 0 as 0, 1, 2, ..., n and column 0 as 0, 1, 2, ..., m
Fill row by row using the recurrence — pure table lookup
Time: O(m × n); Space: O(m × n), reducible to O(min(m, n)) with row-rolling

This is a shortest path problem on a DAG — horizontal/vertical edges have cost 1, diagonal edges have cost 0 (match) or 1 (mismatch)

Longest Common Subsequence (LCS)

Find the longest sequence of characters that appears in both words in order (not necessarily contiguous)
Same 2D matrix structure as edit distance — but maximize instead of minimize
Diagonal edges get value 1 if characters match, 0 otherwise; horizontal/vertical edges always have value 0
This is a longest path problem on the same DAG
Bookkeeping arrows (↑, ←, ↖) stored during DP allow reconstruction of the actual common subsequence

Knapsack Problem — Overview

Given items with weights and profits, and a bag of capacity T, maximize total profit without exceeding capacity
Variants covered:
- Unbounded knapsack: each item can be picked unlimited times → equivalent to Rod Cutting
- 0/1 knapsack: each item picked at most once → requires 2D DP table
- Multiple knapsacks: minimize difference between two bags' totals, etc.
The knapsack problem appears in nearly every competitive programming contest and technical interview

Coin Change is a knapsack variant: given coin denominations with unlimited supply, find the minimum number of coins summing to target T — identical structure to unbounded knapsack

Key Takeaways

All DP problems have an underlying DAG — the recurrence defines the edges, the table defines the nodes
The pattern is always: identify overlapping subproblems → memoize (top-down) or fill table (bottom-up)
Bookkeeping arrays store which choice was made at each step, enabling solution reconstruction
Edit distance, LCS, rod cutting, grid paths, and knapsack are all shortest/longest path problems on DAGs
Complexity drops from exponential (2ⁿ or 3ⁿ) to polynomial (n² or n×m) through DP

Lecture 23 Recording

Lecture 24: Knapsack Variants, Matrix Chain Multiplication & DP on DAGs

0/1 Knapsack Problem

Each item is either picked (1) or not picked (0) — no repetition allowed
Each item has a weight and a value/profit
Goal: maximize total profit without exceeding bag capacity T
Recurrence: K(n, T) = max(K(n-1, T), V[n] + K(n-1, T - W[n]))
Base case: K(0, T) = 0 for all T
Time complexity: O(2ⁿ) for naive recursion; O(n × T) with DP

Knapsack Variants

Subset Sum Problem:

Special case of 0/1 knapsack where weight = value for each item
Find a subset whose elements sum exactly to target t
One of the hardest known problems — only known solution is O(2ⁿ) in general

Unbounded Knapsack:

Each item can be picked any number of times
Rod Cutting is a special case: weight = length of cut, full capacity must be used
Coin Change is also a special case: capacity must be exactly filled

Bounded Knapsack:

Each item can be picked at most a fixed number of times
Requires an additional count array specifying how many times each item may be selected

Fractional Knapsack:

Fractions of items can be taken
Solvable greedily in O(n log n): sort by profit-to-weight ratio, pick greedily
Not a DP problem — but greedy only works when fractions are allowed

Maximize Number of Items (not profit):

Same recurrence, but replace value with 1 for each picked item
Drop the value array entirely; count of items is what gets maximized

Knapsack Variants — Key Insight

All knapsack variants are longest path problems on a DAG
Each node in the recursion tree represents a subproblem state (n, T)
Picking an item = taking an edge with weight = item value
Not picking = taking an edge with weight = 0
DP avoids recomputing overlapping subproblems (same (n, T) appears multiple times in the recursion tree)
Memoization stores results indexed by (n, T) — a 2D table

Knapsack — DP Table (Bottom-Up)

Build a 2D table dp[i][w] = max profit using first i items with capacity w
Fill row by row: for each item i, for each capacity w from 0 to T
Two choices: skip item i → dp[i-1][w], or pick item i → V[i] + dp[i-1][w - W[i]]
Take the max of both choices
Time: O(n × T); Space: O(n × T), reducible to O(T) with row-rolling

Multiple Knapsack / Multiple Lists Variant

K lists each of size n, one knapsack of capacity T
Select one item from each list to maximize total profit within capacity
Extends naturally — outer loop over lists, inner DP per list
Increasing number of lists increases dimensionality of the DP table

Matrix Chain Multiplication — Problem Statement

Given a chain of matrices A1, A2, ..., An, compute their product with minimum total multiplications
Matrix multiplication is associative but not commutative — different parenthesizations give same result but vastly different costs
Example: for matrices of dimensions 50×20, 20×1, 1×10, 10×100:
- Order (((A×B)×C)×D) costs ~51,500 multiplications
- Order (A×(B×(C×D))) costs only ~1,200 multiplications
Cost of multiplying an m×n matrix by an n×t matrix = m × n × t multiplications

Matrix Chain DP — Recurrence

Let C[i][j] = minimum cost to multiply the chain from matrix i to matrix j
Base case: C[i][i] = 0 (single matrix, no multiplication needed)
Recurrence: try all possible split points k between i and j:
- C[i][j] = min over k of { C[i][k] + C[k+1][j] + m_{i-1} × m_k × m_j }
Where matrix Ai has dimensions m_{i-1} × m_i
The last term m_{i-1} × m_k × m_j is the cost of multiplying the two resulting subchains

Matrix Chain DP — Bottom-Up Filling

Fill the table diagonally — subchains of length 1, then 2, then 3, up to n
Each entry depends only on smaller subchains (already computed)
Time: O(n³); Space: O(n²)
Bookkeeping array stores the optimal split point k for each (i, j) → enables reconstruction of optimal parenthesization

Connection to Deep Learning

Every deep neural network layer is a matrix multiplication
A layer with p inputs and q outputs is represented as a p × q weight matrix
Stacking layers = chaining matrix multiplications
The constraint that output dimensions match input dimensions of the next layer is exactly the compatibility condition for matrix chain multiplication
Transformer attention, linear layers, and embeddings are all matrix multiplications under the hood
Choosing efficient computation orders in neural networks is the same optimization problem as matrix chain multiplication

Key Takeaways

Knapsack and all its variants reduce to longest/shortest path on a DAG
Overlapping subproblems are the signal to apply DP — memoize or fill bottom-up
Matrix chain multiplication shows that order of operations matters enormously — same algebraic result, wildly different computational cost
Both problems follow the same DP template: define subproblem, write recurrence, fill table, reconstruct solution via bookkeeping
All DP problems have an underlying DAG — recognizing it makes the solution structure clear

Lecture 24 Recording

Lecture 25 Part-01 Recording

Lecture 25 (Part 1): Greedy Algorithms — Introduction, Correctness Proofs & MST Setup

Why Greedy Choices Can Fail

A greedy choice picks the locally best option at each step hoping it leads to a globally optimal solution
This is not always correct — greedy choices must be formally proven
Counter-example: coin change with denominations {1, 3, 4}, paying 6
- Greedy (pick largest first): 4 + 1 + 1 = 3 coins
- Optimal: 3 + 3 = 2 coins
Greedy failed because the locally best choice (4) blocked a globally better solution

When Greedy Works — The Proof Obligation

Greedy algorithms are valid only when local optimality guarantees global optimality
This must be mathematically proven — intuition is not enough
Standard proof technique: proof by contradiction
- Assume some other algorithm gives a better solution (call it OPT)
- Show that our greedy solution is at least as good as OPT
- This creates a contradiction — so no better solution exists
Without this proof, a greedy algorithm is just a guess

Fractional Knapsack — Greedy Solution & Proof

Problem: Items have weights and values; fractions of items can be taken; maximize total value within capacity T

Greedy Strategy: Sort items by value-to-weight ratio (v/w), pick in decreasing order; take a fraction of the last item if needed

Why greedy works here (proof sketch):

Suppose OPT picks a different first item j instead of our greedy item i
Since item i has the highest v/w ratio, replacing j's contribution with item i's contribution (same weight) gives equal or higher value
This does not reduce total value → our greedy solution is at least as good as OPT → contradiction with OPT being strictly better
Therefore greedy gives the optimal solution

Why greedy fails for 0/1 knapsack:

Without fractions, picking the highest ratio item may use capacity that could fit multiple smaller items with better combined value
Example: one item of weight 90, ratio 1000/90 ≈ 11.1 beats five items of weight 20, ratio 20 — but the five items fill capacity 100 with total value 100 vs single item value 1000 but leaves 10 capacity wasted
Fractions remove this problem — you always fill capacity exactly

Greedy Proof Template

Let GA = greedy algorithm's solution; OPT = any other claimed optimal solution
Sort both solutions by the same greedy criterion
Find the first position where they differ
Show that swapping OPT's choice with GA's choice at that position does not decrease the objective
Repeat until OPT is transformed into GA without loss → GA is optimal

Minimum Spanning Tree — Problem Motivation

Real-world scenario: connect n cities with roads such that every city is reachable, using minimum total road cost
Building all possible roads costs O(n²) — too expensive
Goal: find the minimum cost subset of edges that keeps the graph fully connected

Key observation:

A minimum cost road network cannot contain cycles
If a cycle exists, one edge in the cycle can be removed without disconnecting the network — reducing total cost
Therefore the minimum cost connected subgraph is always a tree
This is called the Minimum Spanning Tree (MST)

Key Takeaways

Greedy algorithms are powerful but require formal proof of correctness — never assume a greedy choice works
The standard proof strategy is by contradiction: assume a better solution exists, then show swapping toward the greedy choice doesn't hurt
Fractional knapsack is solvable greedily in O(n log n); 0/1 knapsack is not — it requires DP
Minimum Spanning Tree is a natural greedy problem — the MST algorithm and its proof will be covered in the next part of this lecture

Lecture 25 Part-02 Recording

Lecture 25 (Part 2): Minimum Spanning Trees — Prim's & Kruskal's Algorithms

Why MST is Not a Shortest Path Problem

Shortest path from a source yields a spanning tree (via parent pointers) — but it is not always the MST
Counter-example: three nodes connected by edges of cost 100, 100, and 1
- Dijkstra picks both 100-cost edges → total cost 200
- MST picks the 1-cost edge and one 100-cost edge → total cost 101
The objectives are fundamentally different: shortest path minimizes distance from source; MST minimizes total edge weight of the connected subgraph

Spanning Tree & Cut — Definitions

A spanning tree of a graph G = (V, E) is a subset of n-1 edges that keeps all vertices connected with no cycles
Any two vertices in a spanning tree have exactly one unique path between them
A cut partitions the vertex set into two non-empty subsets S and V-S; the cut edges are all edges crossing between them
Removing all cut edges disconnects the two subsets

Safe Edge — The Core Greedy Principle

Among all edges crossing a cut, the minimum weight edge is called a safe edge
Adding the safe edge to the current partial MST is always a valid greedy choice
This is the foundational property that both Prim's and Kruskal's algorithms exploit
Proof sketch: if OPT chose a different crossing edge, swapping it for the safe edge cannot increase total cost → safe edge is at least as good

Prim's Algorithm — Growing the Tree

Strategy: Start from any vertex; repeatedly add the cheapest edge connecting the current tree to any unvisited vertex

Algorithm steps:

Initialize all vertex keys to ∞, source key to 0, all parents to Nil
Insert all vertices into a min-priority queue Q
While Q is not empty: extract the minimum key vertex u, add it to MST
For each neighbor v of u: if edge weight w(u,v) < v.key → update v.key = w(u,v) and v.parent = u

Key difference from Dijkstra:

Dijkstra: v.dist = u.dist + w(u,v) — accumulates distance from source
Prim's: v.key = w(u,v) — stores only the direct edge weight, no accumulation
This single line change converts Dijkstra into Prim's

Cycle prevention: once a vertex is extracted from Q, it is never reinserted — edges back into the already-built tree are ignored automatically

Time complexity: O(E log V)

Build heap: O(V)
V extractions at O(log V) each → O(V log V)
E relaxation calls at O(log V) each → O(E log V)
Total: O(E log V)

Kruskal's Algorithm — Merging Components

Strategy: Sort all edges by weight; greedily add the cheapest edge that connects two different components

Algorithm steps:

Initialize each vertex as its own singleton set (individual MST)
Sort all edges by weight in ascending order
For each edge (u, v) in sorted order:
- If FindSet(u) ≠ FindSet(v) → safe edge found, include it; call Union(u, v)
- If FindSet(u) == FindSet(v) → would create a cycle, skip it
Stop when n-1 edges have been selected

Example trace (from lecture):

Pick edge weight 2 → merges two singletons
Pick edge weight 3 → merges two other singletons
Pick edge weight 4 → extends a component
Pick edge weight 5 → extends further
Edge weight 8 → skipped (would create a cycle — both endpoints already in same component)

Union-Find Data Structure

Kruskal's requires efficient set membership queries and merges — this is the Union-Find (Disjoint Set Union) data structure

Two operations:

MakeSet(x) → create a new singleton set containing x
FindSet(x) → return the representative (ID) of the set containing x
Union(x, y) → merge the two sets containing x and y; choose one representative for the combined set

Representative concept:

Each set has one designated representative (like a class president)
FindSet(x) returns this representative
If FindSet(u) == FindSet(v) → same set → edge would create a cycle → skip
If FindSet(u) != FindSet(v) → different sets → safe to add edge → call Union

Prim's vs Kruskal's — Comparison

Property

Prim's

Kruskal's

Strategy

Grow one tree from a source

Merge disjoint components

Data structure needed

Min-heap (priority queue)

Union-Find + sorted edges

Best for

Dense graphs

Sparse graphs

Time complexity

O(E log V)

O(E log E) = O(E log V)

Connection to Deep Learning

Gradient descent in neural networks is also a greedy algorithm
At each step, compute the gradient (slope) in every dimension and move in the direction of steepest descent
The greedy choice: take the step that most reduces the loss locally
Whether this local greedy choice leads to the global optimum is the central question of optimization theory — exactly the same question we ask about greedy algorithms in general

Key Takeaways

MST is not a shortest path problem — the two problems have different objectives and different algorithms
Both Prim's and Kruskal's are greedy algorithms built on the safe edge / cut property
Prim's is essentially Dijkstra with one line changed — no accumulation of distances
Kruskal's requires Union-Find to efficiently detect cycles and merge components
The Union-Find data structure and its time complexity analysis will be covered in the next lecture

Lecture 26 Part-01 Recording

Lecture 26 (Part 1): Prim's Algorithm Deep-Dive & Union-Find Data Structure

Prim's Algorithm — Implementation Review

Start from any source vertex; set its key to 0, all others to ∞, all parents to Nil
Insert all vertices into a min-priority queue (min-heap)
Each iteration: extract the minimum key vertex u, add it to MST via its parent pointer
For each neighbor v of u (via adjacency list): if edge weight w(u,v) < v.key → update v.key = w(u,v) and v.parent = u

Key difference from Dijkstra — one line change:

Dijkstra: v.dist = u.dist + w(u,v) — accumulates path distance
Prim's: v.key = w(u,v) — stores only the local edge weight, no accumulation
This means Prim's is purely greedy on local edge costs, not cumulative distances

Cycle prevention:

Once a vertex leaves the heap, it is marked (boolean flag)
Any edge pointing back to an already-extracted vertex is skipped — it would create a cycle
Edges are only relaxed toward vertices still inside the heap

Adjacency list format: each entry is a pair (neighbor, weight) — the weight is the second element used in the relaxation condition

Time complexity: O(E log V)

Build heap: O(V)
V extractions × O(log V) each = O(V log V)
E relaxation updates × O(log V) each = O(E log V)
Dominant term: O(E log V)

Advanced note: Using a Fibonacci heap instead of a binary heap removes the log factor from updates, giving O(E + V log V) — not required but worth knowing

Kruskal's Algorithm — Recap

Sort all edges by weight in ascending order
Process edges one by one: include an edge (u, v) only if u and v belong to different components
Skip any edge that would create a cycle (same component)
Stop after selecting n-1 edges → MST complete

Correctness argument:

Each selected edge connects two disjoint MSTs — it is always a safe edge
Proof by contradiction: if any other algorithm chose a different crossing edge, swapping it for Kruskal's choice cannot increase total cost → Kruskal's is optimal

Why Greedy Proofs Matter

Competitive programming and exam problems will give a greedy problem and ask you to prove it is optimal
The proof obligation: show that local greedy choices lead to globally optimal solutions
Standard method: proof by contradiction — assume a better solution exists, then show swapping toward the greedy choice never worsens the result
Without this proof, a greedy algorithm is just a heuristic

Union-Find (Disjoint Set Union) Data Structure

Kruskal's needs to efficiently answer: do vertices u and v belong to the same component?

Two operations:

MakeSet(x) → initialize x as its own singleton set; x is its own representative
FindSet(x) → return the representative (root) of x's set; traverse parent pointers until reaching the root
Union(x, y) → merge the sets containing x and y; make one root the parent of the other

How it works conceptually:

Each set has one representative (like a class president)
FindSet(x) climbs the parent chain until it finds the root (node that is its own parent or has Nil parent)
If FindSet(u) == FindSet(v) → same component → adding edge (u,v) creates a cycle → skip
If FindSet(u) != FindSet(v) → different components → safe to add → call Union(u, v)

Why arbitrary union can be slow:

If always making the larger tree the child of the smaller, parent chains can grow to length n
In worst case (chain-like merges), FindSet costs O(n) per call
With e edges processed in Kruskal's, total cost could reach O(e × n) = O(n²)

The fix — Union by Size (or Rank):

Always attach the smaller tree under the larger tree
This bounds tree height at O(log n)
FindSet cost drops to O(log n) per call
Total Kruskal's complexity: O(E log E) = O(E log V)

Key Takeaways

Prim's and Dijkstra differ by exactly one line — understanding this connection deepens intuition for both
Prim's builds MST by greedily extending one tree; Kruskal's builds it by merging disjoint components
Union-Find is the critical data structure for Kruskal's — enables O(1) average cycle detection
Naive Union-Find (arbitrary parent choice) degrades to O(n²); Union by Size restores efficiency
Path compression (covered next lecture) further improves Union-Find to nearly O(1) per operation