1.

Huffman Coding - Overview

Huffman coding is an optimal prefix code used for lossless data compression. It constructs a binary tree
where more frequent symbols have shorter codes.
Algorithm idea: repeatedly combine the two least-frequent symbols/nodes into a new internal node until a
single tree remains. The code for a symbol is the path from root to its leaf (0/1).
Time complexity: O(n log n) when using a min-heap for n symbols. Huffman codes are optimal among
prefix codes for known symbol frequencies.
Pseudocode (high level): 1. Create a leaf node for each symbol and build a min-heap ordered
by frequency. 2. While heap size > 1: extract two nodes with smallest frequency a,b; create
new node with frequency [Link]+[Link] with children a and b; insert new node back. 3. The
remaining node is the root. Assign 0/1 along edges to get codes.

Huffman - Solved Example & Approach

Example frequencies: a:45, b:13, c:12, d:16, e:9, f:5. Combine lowest pairs repeatedly to obtain codes
(illustrated in the image).
Approach: show tree construction step-by-step using a min-heap; verify prefix-free property and calculate
average code length.

2. Binary Search Tree (BST) - Basics

A BST is a binary tree where for any node, all keys in the left subtree are less than the node's key and all
keys in the right subtree are greater.
Operations: search, insert, delete. Inorder traversal outputs keys in sorted order.
Time complexity: average O(h) where h is height; worst-case O(n) for unbalanced trees.
BST Insert (recursive): if root is null: return new node if key < [Link]: [Link] =
insert([Link], key) else: [Link] = insert([Link], key) return root
BST - Deletion Cases & Example
Deletion has three cases: leaf node (just remove), node with one child (replace with child), node with two
children (replace with inorder successor or predecessor and delete that node).
Example: delete 30 from BST [50,30,70,20,40,60,80,35] -> find successor, adjust links, fix tree.

Derived BST (Self-balancing variants) - Overview

Derived BST typically refers to BST variants that add balancing or self-adjusting behavior: AVL trees
(height-balanced), Red-Black trees, Splay trees. These ensure logarithmic height for worst-case
guarantees.
AVL: maintain balance factor (-1,0,1) at nodes and perform rotations on insert/delete. Red-Black:
color-based balancing that guarantees O(log n) operations with less rotations on average. Splay: moves
accessed nodes to root (amortized bounds).
AVL insert idea: 1. Insert as in BST. 2. Walk back up to update heights and balance
factors. 3. If a node becomes unbalanced (|bf|>1), perform appropriate rotations (LL, RR,
LR, RL).

3. Euler Path / Circuit (Graphs)

An Eulerian trail (path) is a path that uses every edge exactly once. An Eulerian circuit is an Eulerian trail
that starts and ends at the same vertex.
Characterization (undirected): A connected graph has an Euler circuit iff every vertex has even degree. It
has an Euler path (but not circuit) iff exactly two vertices have odd degree (the path endpoints).
Use Fleury's algorithm or Hierholzer's algorithm to actually construct the path in linear time O(E).
Hierholzer's algorithm (idea): 1. Start at any vertex with edges; follow edges one at a
time choosing unused edges until you return to the start; this forms a cycle. 2. If any
vertex on the cycle has unused edges, start another tour there and splice. 3. Continue
until all edges used.

Euler - Solved Example (Approach)

Given graph in figure, compute degrees, check Euler property, then apply Hierholzer to produce a valid
trail. Keep track of used edges and splice cycles.

4. Hamiltonian Path / Cycle (Graphs)

A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle returns to the start. There is no
simple necessary-and-sufficient local condition like Eulerian graphs.
Decision problem is NP-complete. Common methods: backtracking with pruning, Dirac's / Ore's sufficient
conditions for existence, and heuristics for large graphs.
Backtracking approach (recursive): 1. Try to build path by adding one vertex at a time,
rejecting if next vertex not adjacent or already used. 2. Backtrack when stuck. Time:
exponential in worst case.

5. Warshall / Floyd–Warshall - Transitive closure & all-pairs

shortest paths
Warshall's algorithm computes the transitive closure of a directed graph (reachability) using dynamic
programming over adjacency matrices. Floyd–Warshall is a closely related algorithm for all-pairs shortest
paths in weighted graphs.
Warshall (boolean) recurrence: for k from 1..n, for i,j: reach[i][j] = reach[i][j] OR (reach[i][k] AND reach[k][j]).
Time O(n^3).
Warshall pseudocode: for k in 1..n: for i in 1..n: for j in 1..n: R[i][j] = R[i][j] or
(R[i][k] and R[k][j])

6. Max-Heap - Theorem and properties

A max-heap is a complete binary tree where each node's key >= keys of its children. Usually represented
as an array where parent index i has children at 2i+1 and 2i+2 (0-indexed).
Operations: build-heap O(n), insert O(log n), extract-max O(log n). Sift-up/sift-down maintain heap
property.
Build-max-heap (bottom-up): for i = floor(n/2)-1 down to 0: max-heapify(A, i) max-heapify
ensures subtree rooted at i satisfies heap property.
7. Dijkstra's Algorithm - Shortest Paths (single-source)
Dijkstra's algorithm finds shortest paths from a source to all vertices for graphs with non-negative edge
weights. Use a min-priority queue to extract closest unvisited vertex and relax edges.
Time: using binary heap O(E log V). It does not handle negative-weight edges (use Bellman-Ford instead).
Pseudocode (high level): Initialize dist[s]=0, others = INF PQ = min-heap keyed by dist
while PQ not empty: u = extract-min(PQ) for (u,v) in Adj[u]: if dist[v] > dist[u] + w(u,v):
dist[v] = dist[u] + w(u,v); decrease-key in PQ

Dijkstra - Example & Approach

Run Dijkstra step-by-step on the provided graph: initialize distances, relax edges from source, select next
smallest distance vertex, repeat. Keep predecessor array to rebuild paths.

8. Prim's and Kruskal's Algorithms - MSTs

Minimum Spanning Tree (MST) of a connected, weighted undirected graph is a subset of edges
connecting all vertices with minimum total weight.
Prim's: grow tree from a start vertex by repeatedly adding the cheapest edge that connects the tree to a
new vertex (use PQ). Kruskal's: sort edges by weight and add if it doesn't form a cycle (use Union-Find).
Both are greedy and correct by cut/cycle properties.
Kruskal pseudocode: F = {} for each vertex v: MAKE-SET(v) for each edge (u,v) in increasing
weight: if FIND-SET(u) != FIND-SET(v): add edge to F; UNION(u,v) return F
Kruskal/Prim - Solved Example & Approach
Example: run Kruskal on the sample graph by sorting edges and adding safe edges while avoiding cycles
(illustrate union-find steps). For Prim, show chosen edges when growing the tree from a start node.

9. Graph Coloring - Basics and Example

Graph coloring assigns colors to vertices such that adjacent vertices have different colors. The chromatic
number χ(G) is the smallest number of colors needed.
Graph coloring decision is NP-complete in general. Greedy coloring (order-dependent) is a practical
heuristic; special graph classes have polynomial-time algorithms.
Greedy coloring (simple): Order vertices arbitrarily; for v in order: assign smallest
color not used by neighbors. Result uses at most ∆+1 colors, where ∆ is maximum degree.

10. Misc: MST, Complexity, and Study Tips

Key proofs: correctness of Kruskal and Prim rely on 'cut' and 'cycle' properties: the cheapest edge crossing
any cut is safe to add to some MST.
Complexities summary: Dijkstra O(E log V), Prim O(E log V) with heap, Kruskal O(E log E) dominated by
sort, Floyd–Warshall O(V^3), Warshall (boolean) O(V^3), Huffman O(n log n).
Study tips: implement each algorithm, dry-run small examples by hand, and practise past problems that
ask for construction and proof of correctness.
Appendix: Selected solved problems (concise)
1) Huffman: build code for weights [45,13,12,16,9,5] (solution pictured).
2) BST: show inorder, preorder, postorder for sample BST. (Shown earlier).
3) Dijkstra: shortest path from A to E in example graph => A-C-D-E (cost computed by running algorithm).