← Back to Data Structures and Algorithms
Course: MAT5EJ302(1) — Data Structures and Algorithms
Hours: 12 | Textbook Sections: 2.1, 2.2, 2.3, 3.1–3.3 (Dasgupta et al.)
1. The Divide and Conquer Paradigm
Many efficient algorithms follow a three-step template:
- Divide: Break the input into smaller subproblems of the same type.
- Conquer: Solve each subproblem recursively. (Base case: when the input is small enough, solve directly.)
- Combine: Merge the subproblem solutions into a solution for the original problem.
The power of this approach comes from the fact that a problem of size $n$ is often solvable by combining solutions to problems of size $n/2$, leading to running times like $\mathcal{O}(n \log n)$ rather than $\mathcal{O}(n^2)$.
2. Fast Integer Multiplication (Karatsuba’s Algorithm)
2.1 The Baseline: Grade-School Multiplication
For two $n$-bit integers $x$ and $y$, grade-school multiplication requires $\mathcal{O}(n^2)$ bit operations (as shown in Module I). Can we do better?
2.2 A First Attempt
Split $x$ and $y$ at the halfway point:
x = x_L · 2^(n/2) + x_R [left and right halves of x]
y = y_L · 2^(n/2) + y_R
Then:
x · y = (x_L · 2^(n/2) + x_R)(y_L · 2^(n/2) + y_R)
= x_L · y_L · 2^n + (x_L · y_R + x_R · y_L) · 2^(n/2) + x_R · y_R
This requires 4 multiplications of $(n/2)$-bit numbers, giving recurrence:
T(n) = 4T(n/2) + O(n)
By the Master Theorem (see Section 3), this gives $T(n) = \mathcal{O}(n^2)$ — no improvement!
2.3 Karatsuba’s Trick
Observe that $x_L \cdot y_R + x_R \cdot y_L$ can be computed with just one extra multiplication:
(x_L + x_R)(y_L + y_R) = x_L·y_L + x_L·y_R + x_R·y_L + x_R·y_R
So:
x_L·y_R + x_R·y_L = (x_L + x_R)(y_L + y_R) - x_L·y_L - x_R·y_R
We already compute $x_L \cdot y_L$ and $x_R \cdot y_R$. So we only need 3 multiplications total:
Algorithm: Karatsuba(x, y)
n = max(bits of x, bits of y)
if n = 1: return x · y [base case]
Split: x_L = x >> n/2, x_R = x mod 2^(n/2)
y_L = y >> n/2, y_R = y mod 2^(n/2)
p = Karatsuba(x_L, y_L)
q = Karatsuba(x_R, y_R)
r = Karatsuba(x_L + x_R, y_L + y_R)
return p · 2^n + (r - p - q) · 2^(n/2) + q
Recurrence:
T(n) = 3T(n/2) + O(n)
By the Master Theorem: $T(n) = \mathcal{O}(n^{\log_2 3}) = \mathcal{O}(n^{1.585})$.
This is a significant improvement over $\mathcal{O}(n^2)$ for large $n$. Modern fast multiplication algorithms achieve even better — $\mathcal{O}(n \log n \log\log n)$ — but Karatsuba’s is the easiest to understand.
3. Solving Recurrence Relations
Many divide-and-conquer algorithms lead to recurrences of the form:
T(n) = aT(n/b) + O(n^d)
where:
- $a$ = number of subproblems
- $n/b$ = size of each subproblem
- $\mathcal{O}(n^d)$ = work done outside recursive calls
3.1 The Master Theorem
Theorem: For $T(n) = aT(n/b) + \mathcal{O}(n^d)$ with $a \geq 1$, $b > 1$, $d \geq 0$:
| Condition | Solution |
|---|---|
| $d > \log_b a$ | $T(n) = \mathcal{O}(n^d)$ — the merge work dominates |
| $d = \log_b a$ | $T(n) = \mathcal{O}(n^d \log n)$ — balanced |
| $d < \log_b a$ | $T(n) = \mathcal{O}(n^{\log_b a})$ — the recursion dominates |
Intuition: Think about the recursion tree.
- At level $k$ ($k$ levels deep), there are $a^k$ subproblems, each of size $n/b^k$, each doing $(n/b^k)^d$ work.
- Work at level $k$ = $a^k \cdot (n/b^k)^d = n^d \cdot (a/b^d)^k$.
- This is a geometric series with ratio $a/b^d$.
- If $a/b^d < 1$: the first level dominates → $\mathcal{O}(n^d)$.
- If $a/b^d = 1$: all levels equal → $\log n$ levels × $n^d$ each → $\mathcal{O}(n^d \log n)$.
- If $a/b^d > 1$: the deepest level dominates → $\mathcal{O}(n^{\log_b a})$.
3.2 Worked Examples
Example 1: Merge sort: $T(n) = 2T(n/2) + \mathcal{O}(n)$
- $a = 2$, $b = 2$, $d = 1$. Check: $\log_2 2 = 1 = d$. Case 2 → $T(n) = \mathcal{O}(n \log n)$.
Example 2: Binary search: $T(n) = T(n/2) + \mathcal{O}(1)$
- $a = 1$, $b = 2$, $d = 0$. Check: $\log_2 1 = 0 = d$. Case 2 → $T(n) = \mathcal{O}(\log n)$.
Example 3: Karatsuba: $T(n) = 3T(n/2) + \mathcal{O}(n)$
- $a = 3$, $b = 2$, $d = 1$. Check: $\log_2 3 \approx 1.585 > 1 = d$. Case 3 → $T(n) = \mathcal{O}(n^{\log_2 3}) = \mathcal{O}(n^{1.585})$.
Example 4: Naive 4-subproblem split: $T(n) = 4T(n/2) + \mathcal{O}(n)$
- $a = 4$, $b = 2$, $d = 1$. Check: $\log_2 4 = 2 > 1 = d$. Case 3 → $T(n) = \mathcal{O}(n^2)$.
4. Binary Search
Problem: Given a sorted array $A[1..n]$ and a target value $v$, find the index of $v$ in $A$ (or report that it is absent).
4.1 Algorithm
Algorithm: BinarySearch(A, v, lo, hi)
if lo > hi: return -1
mid = ⌊(lo + hi)/2⌋
if A[mid] = v: return mid
if A[mid] > v: return BinarySearch(A, v, lo, mid - 1)
else: return BinarySearch(A, v, mid + 1, hi)
Call initially as BinarySearch(A, v, 1, n).
4.2 Why It Works
The key invariant: at every call, if $v$ exists in $A$, then $v \in A[\text{lo}..\text{hi}]$.
- Initially this is trivially true ($\text{lo}=1$, $\text{hi}=n$).
- At each step, we compare $v$ with $A[\text{mid}]$ and narrow the search range by half.
- The invariant is preserved throughout.
- The range shrinks by half each step, so we terminate in $\mathcal{O}(\log n)$ steps.
4.3 Worked Example
Search for $v = 23$ in $A = [2, 5, 8, 12, 16, 23, 38, 56]$:
Step 1: lo=1, hi=8, mid=4, A[4]=12. 23 > 12 → search right half.
Step 2: lo=5, hi=8, mid=6, A[6]=23. Found at index 6!
Time complexity: $T(n) = T(n/2) + \mathcal{O}(1)$ → $\mathcal{O}(\log n)$.
5. Merge Sort
Problem: Sort an array $A[1..n]$ of $n$ numbers.
5.1 Algorithm
Algorithm: MergeSort(a[1..n])
if n > 1:
return Merge(MergeSort(a[1..⌊n/2⌋]),
MergeSort(a[⌊n/2⌋+1..n]))
else:
return a
The Merge procedure takes two sorted arrays and combines them into one sorted array in $\mathcal{O}(n)$ time: compare the front elements of both arrays, take the smaller, and repeat. Spelled out, using two pointers $i, j$ that each walk one input array left to right:
Algorithm: Merge(A, B) [A, B are sorted arrays]
C = empty array of size |A| + |B|
i = 1, j = 1
for k = 1 to |A| + |B|:
if i > |A|: C[k] = B[j]; j = j + 1
else if j > |B|: C[k] = A[i]; i = i + 1
else if A[i] <= B[j]: C[k] = A[i]; i = i + 1
else: C[k] = B[j]; j = j + 1
return C
Each iteration advances either $i$ or $j$ by one, and the loop runs exactly $|A|+|B|$ times, doing $\mathcal{O}(1)$ work each time — so Merge runs in $\mathcal{O}(|A|+|B|) = \mathcal{O}(n)$, matching the description above.
5.2 Trace on Example
Sort $A = [5, 2, 8, 1, 9, 3]$:
Split: [5, 2, 8] [1, 9, 3]
Split: [5] [2, 8] [1] [9, 3]
Split: [2] [8] [9] [3]
Merge: [2, 8] [3, 9]
Merge: [2, 5, 8] [1, 3, 9]
Merge: [1, 2, 3, 5, 8, 9]
5.3 Time Complexity
Merge sort divides into 2 halves and merges in $\mathcal{O}(n)$ time:
T(n) = 2T(n/2) + O(n) → T(n) = O(n log n)
The Merge step visits each element once → $\mathcal{O}(n)$. There are $\log n$ levels of recursion. Total work = $n \times \log n$ = $\mathcal{O}(n \log n)$.
5.4 Comparison with Other Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Merge sort | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n)$ | Yes |
| Quick sort | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(\log n)$ | No |
| Insertion sort | $\mathcal{O}(n)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(1)$ | Yes |
| Selection sort | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(1)$ | No |
Merge sort is optimal for comparison-based sorting: any comparison-based sort requires $\Omega(n \log n)$ comparisons in the worst case. The next section proves this.
5.5 The $\Omega(n \log n)$ Lower Bound for Comparison Sorting
Merge sort runs in $\mathcal{O}(n \log n)$. Can any comparison-based algorithm do better? No — and this is provable.
The decision-tree argument. Picture any sorting algorithm that decides what to do only by asking questions of the form “is $a_i < a_j$?”. Draw its entire decision process as a tree: each internal node is one such comparison, and each leaf is a final, fully-decided ordering of the input. Running the algorithm on a specific input just walks one root-to-leaf path in this tree — so the tree’s depth is exactly the worst-case number of comparisons the algorithm makes.
Example (3 elements). To sort $a_1, a_2, a_3$, first ask “$a_1 < a_2$?”, then ask a follow-up question depending on the answer, and so on. Every one of the $3! = 6$ possible orderings of three elements must appear as some leaf of this tree — if a permutation were missing, feeding the algorithm an input ordered that way would leave it with nowhere correct to go. Since a binary tree of depth $d$ has at most $2^d$ leaves, we need $2^d \geq 6$, i.e. $d \geq \log_2 6 \approx 2.585$, so $d \geq 3$ — matching the true worst case of exactly $3$ comparisons.
The general theorem. For $n$ elements, every leaf must be labelled by a distinct permutation of $\{1, \ldots, n\}$, so the tree needs at least $n!$ leaves. A binary tree of depth $d$ has at most $2^d$ leaves, so the depth $d$ — the worst-case number of comparisons — must satisfy $2^d \geq n!$, i.e. $d \geq \log_2(n!)$. Using $n! \geq (n/2)^{n/2}$ (the top half of the factors, $\lceil n/2\rceil,\ldots,n$, are each at least $n/2$):
\[\log_2(n!) \;\geq\; \frac{n}{2}\log_2\frac{n}{2} \;=\; \Omega(n \log n).\]So any comparison-based sorting algorithm needs $\Omega(n \log n)$ comparisons in the worst case. Since merge sort already achieves $\mathcal{O}(n \log n)$ (Section 5.3), it matches this lower bound exactly — merge sort is asymptotically optimal among comparison-based sorts.
Note. This bound applies only to algorithms that sort by comparing elements. It does not rule out linear-time sorting when extra structure is available — e.g. when the elements are integers known to lie in a small range $[0, M]$, counting sort can sort in $\mathcal{O}(n+M)$ time by counting occurrences directly, without ever comparing two elements to each other.
6. Graphs
6.1 What Is a Graph?
A graph $G = (V, E)$ consists of:
- A set of vertices (or nodes) $V$
- A set of edges $E$, where each edge connects two vertices
Types:
- Undirected graph: edges have no direction; $\{u, v\} = \{v, u\}$
- Directed graph (digraph): edges have direction; $(u, v) \neq (v, u)$
- Weighted graph: each edge has a numerical weight/cost
Basic terminology:
- Degree of a vertex $v$ = number of edges incident to $v$
- Path = sequence of distinct vertices connected by edges
- Cycle = path that starts and ends at the same vertex
- Connected graph = any two vertices are connected by some path
- Tree = connected undirected graph with no cycles (has $n-1$ edges for $n$ vertices)
6.2 Graph Representations
Two standard ways to store a graph in memory:
Adjacency Matrix
An $n \times n$ matrix $A$ where $A[i][j] = 1$ if there is an edge from $i$ to $j$, 0 otherwise (or the weight for weighted graphs).
Graph: 1-2, 1-3, 2-3, 3-4
Matrix:
1 2 3 4
1 [ 0 1 1 0 ]
2 [ 1 0 1 0 ]
3 [ 1 1 0 1 ]
4 [ 0 0 1 0 ]
Space: $\mathcal{O}(|V|^2)$ Check if edge $(u,v)$ exists: $\mathcal{O}(1)$ Find all neighbours of $v$: $\mathcal{O}(|V|)$
Adjacency List
For each vertex $v$, store the list of its neighbours.
1 → [2, 3]
2 → [1, 3]
3 → [1, 2, 4]
4 → [3]
Space: $\mathcal{O}(|V| + |E|)$ Check if edge $(u,v)$ exists: $\mathcal{O}(\text{degree}(u))$ Find all neighbours of $v$: $\mathcal{O}(\text{degree}(v))$
Comparison
| Operation | Adjacency Matrix | Adjacency List |
|---|---|---|
| Space | $\mathcal{O}(|V|^2)$ | $\mathcal{O}(|V| + |E|)$ |
| Edge lookup | $\mathcal{O}(1)$ | $\mathcal{O}(\text{degree})$ |
| Iterate all edges | $\mathcal{O}(|V|^2)$ | $\mathcal{O}(|V| + |E|)$ |
| Best for | Dense graphs ($E \approx V^2$) | Sparse graphs ($E \ll V^2$) |
Most real-world graphs are sparse (social networks, road networks, web graphs), so adjacency lists are used more often.
7. Depth-First Search (DFS)
DFS is one of the most fundamental graph algorithms. It explores as deep as possible along each branch before backtracking.
7.1 DFS on Undirected Graphs
Algorithm: DFS(G)
for all v ∈ V: visited(v) = false
clock = 1
for all v ∈ V:
if not visited(v): Explore(v)
Algorithm: Explore(v)
visited(v) = true
pre[v] = clock; clock = clock + 1
for each edge (v, u) ∈ E:
if not visited(u): Explore(u)
post[v] = clock; clock = clock + 1
pre[v] = the time when $v$ is first visited (“pre-visit number”).
post[v] = the time when $v$’s exploration is completed (“post-visit number”).
Time complexity: Every vertex and edge is visited at most twice → $\mathcal{O}(|V| + |E|)$.
7.2 Trace Example — Undirected Graph
Graph: vertices $\{A, B, C, D, E\}$, edges $\{A\text{-}B, A\text{-}C, B\text{-}D, C\text{-}D, D\text{-}E\}$
Starting DFS from A:
Visit A (pre=1)
Visit B (pre=2)
Visit D (pre=3)
Visit C (pre=4)
C's unvisited neighbour: none (A visited, D visited)
post[C] = 5
Visit E (pre=6)
post[E] = 7
post[D] = 8
post[B] = 9
post[A] = 10
Pre-order: $A(1), B(2), D(3), C(4), E(6)$ Post-order (completion): $C(5), E(7), D(8), B(9), A(10)$
7.3 Undirected DFS: Only Tree and Back Edges
Key fact. In a DFS of an undirected graph, every edge is either a tree edge or a back edge — there are no forward edges and no cross edges.
Why. Take an undirected edge $\{u, v\}$, and say Explore(u) starts before Explore(v) (so $\text{pre}[u] < \text{pre}[v]$). Because the edge is undirected, it sits in both $u$’s and $v$’s adjacency lists. The first time it’s examined is from $u$’s side, and at that point $v$ cannot have been visited yet (since $\text{pre}[u] < \text{pre}[v]$) — so this examination always discovers $v$, making the edge a tree edge with $u$ as $v$’s parent. Since $v$ is now $u$’s descendant, $u$ stays on the call stack (not yet postvisited) until $v$’s whole subtree finishes. So the second examination — from $v$’s side, looking back at $u$ — finds $u$ already visited but not yet postvisited: exactly the condition for a back edge. There is no way for the edge to instead land on an unrelated, already-finished branch (which is what a forward or cross edge would require).
This is exactly what let us classify $AC$ and $BD$ as back edges (not forward or cross) in the trace above, without having to check every possibility by hand.
7.4 The Nesting Property of Pre/Post Intervals
Key fact. For any two vertices $u, v$ in a DFS, the intervals $[\text{pre}[u], \text{post}[u]]$ and $[\text{pre}[v], \text{post}[v]]$ are either nested (one entirely inside the other) or disjoint — they can never partially overlap. They are nested exactly when one vertex is an ancestor of the other in the DFS tree.
This is why the edge-type tables below (Section 7.6) can be phrased purely in terms of pre/post comparisons — nesting vs. disjointness of intervals is a direct stand-in for the ancestor relationship in the DFS tree.
7.5 Connected Components
If the graph is not connected, one call to Explore only reaches the component containing its starting vertex. The outer loop in DFS handles this automatically: every time it starts a fresh Explore call from an unvisited vertex, that call discovers exactly one new connected component.
Example. Take a graph with two separate pieces: $\{P, Q\}$ with edge $P\text{-}Q$, and $\{R, S, T\}$ with edges $R\text{-}S, S\text{-}T$ — no edge between the pieces.
Explore(P): pre[P]=1, pre[Q]=2, post[Q]=3, post[P]=4 → component {P, Q}
Explore(R): pre[R]=5, pre[S]=6, pre[T]=7, post[T]=8,
post[S]=9, post[R]=10 → component {R, S, T}
The intervals $[1,4]$ and $[5,10]$ are completely disjoint — neither contains the other — matching the Nesting Property (Section 7.4): vertices in different components are never ancestors of each other, so their intervals can’t be nested, leaving disjoint as the only option. In general, the number of times the outer loop of DFS calls Explore equals the number of connected components.
7.6 DFS on Directed Graphs
The same algorithm applies. For directed graphs, we distinguish edge types based on the DFS tree structure:
| Edge Type | Description | Pre/Post Relationship |
|---|---|---|
| Tree edge | Edge in the DFS tree (went from u to unvisited v) | $\text{pre}[u] < \text{pre}[v] < \text{post}[v] < \text{post}[u]$ |
| Back edge | Edge to an ancestor in DFS tree (creates a cycle) | $\text{pre}[v] < \text{pre}[u] < \text{post}[u] < \text{post}[v]$ |
| Forward edge | Edge to a descendant (not tree edge) | $\text{pre}[u] < \text{pre}[v] < \text{post}[v] < \text{post}[u]$ |
| Cross edge | All other edges | $\text{pre}[v] < \text{post}[v] < \text{pre}[u] < \text{post}[u]$ |
Important property: A directed graph has a cycle $\leftrightarrow$ DFS finds a back edge.
7.7 Applications of DFS
- Cycle detection: Look for back edges during DFS
- Topological sort: covered fully in Section 7.8 below
- Connectivity: Check if all vertices are reachable from a source — see Section 7.5 for the general connected-components version
- Strongly connected components: (covered in Module III)
7.8 Directed Acyclic Graphs (DAGs) and Topological Sort
A cycle in a directed graph is a circular path $v_0 \to v_1 \to \cdots \to v_k \to v_0$. A directed graph with no cycles at all is a DAG (Directed Acyclic Graph). By the cycle property above (Section 7.6), testing this takes just one DFS, $\mathcal{O}(|V|+|E|)$: run DFS and check whether it finds a back edge.
DAGs show up wherever there are dependencies with no loops: course prerequisites, task scheduling, build systems, family trees.
Topological ordering (linearization): an ordering of the vertices such that every edge $(u, v)$ goes from an earlier vertex $u$ to a later vertex $v$.
Key fact. In a DAG, every edge $(u, v)$ leads to a vertex with a strictly lower post number: $\text{post}[v] < \text{post}[u]$. (Since a DAG has no back edge, $(u,v)$ must be a tree, forward, or cross edge — and in every one of those three cases, $v$ finishes being explored before $u$ does.)
This one fact immediately gives an $\mathcal{O}(|V|+|E|)$ algorithm:
Algorithm: TopologicalSort(G)
run DFS(G), recording post[v] for every vertex
output the vertices in decreasing order of post[v]
Sources and sinks. Every DAG has at least one source (no incoming edges) and one sink (no outgoing edges): in any topological order, the first vertex cannot have an earlier vertex pointing to it (so it’s a source), and the last vertex cannot have an edge pointing to a still-later vertex (so it’s a sink).
This gives a second, entirely different algorithm:
Algorithm: TopologicalSortBySourceRemoval(G)
while G is not empty:
find a vertex s with in-degree 0 [a source]
output s
delete s and all its outgoing edges from G
Since every remaining subgraph of a DAG is itself a DAG, a source is always guaranteed to exist to remove, until the graph is empty.
Worked Example: Topological Sort, Two Ways
DAG with vertices $\{A,B,C,D,E,F\}$ and edges $B\to A$, $B \to D$, $A \to C$, $D \to C$, $C \to E$, $C \to F$.
Method 1 — DFS / post-number. Running DFS with alphabetical tie-breaking gives:
pre: A=1 B=9 C=2 D=10 E=3 F=5
post: A=8 B=12 C=7 D=11 E=4 F=6
Sorting vertices by decreasing post number: $B(12), D(11), A(8), C(7), F(6), E(4)$ — topological order: \(B,\ D,\ A,\ C,\ F,\ E.\)
Method 2 — source removal. Only source initially is $B$ (in-degree 0) → output $B$, remove it; now $A$ and $D$ both become sources → output $A$ (alphabetically first) → now $D$ is the only source → output $D$ → now $C$ becomes a source → output $C$ → now $E, F$ both become sources → output $E$, then $F$. Topological order: \(B,\ A,\ D,\ C,\ E,\ F.\)
How many valid orderings exist? $B$ must come before both $A$ and $D$; both must come before $C$; and $C$ must come before both $E$ and $F$. But there is no constraint between $A$ and $D$, nor between $E$ and $F$. So $B$ is locked into position 1 and $C$ into position 4, while $\{A,D\}$ can appear in either order (2 ways) and $\{E,F\}$ can appear in either order (2 ways), independently — giving $2\times2=4$ valid topological orders in total: \(BADCEF,\quad BADCFE,\quad BDACEF,\quad BDACFE.\) Method 1 found the fourth of these; Method 2 found the first — both are correct, since a DAG generally admits more than one valid linearization.
Exam tip. A DAG usually has more than one correct topological order. Unless a question specifically asks for the order a named algorithm (DFS/post-number, or source-removal) produces, any valid linearization should be accepted — but you should still be able to list all sources, all sinks, and (for small graphs) count the total number of valid orderings.
8. Summary
| Topic | Key Point | Complexity |
|---|---|---|
| Karatsuba multiplication | 3 recursive calls vs. 4 → faster than $\mathcal{O}(n^2)$ | $\mathcal{O}(n^{1.585})$ |
| Master Theorem | Solves $T(n) = aT(n/b) + n^d$ in 3 cases | — |
| Binary search | Halve search space each step | $\mathcal{O}(\log n)$ |
| Merge sort | Divide + merge; $\mathcal{O}(n \log n)$ optimal sort | $\mathcal{O}(n \log n)$ |
| Sorting lower bound | Decision-tree argument; no comparison sort beats this | $\Omega(n \log n)$ |
| Adjacency matrix | Constant edge lookup, $\mathcal{O}(|V|^2)$ space | $\mathcal{O}(|V|^2)$ space |
| Adjacency list | Efficient for sparse graphs, $\mathcal{O}(|V|+|E|)$ space | $\mathcal{O}(|V|+|E|)$ space |
| DFS | Explore deep before wide; pre/post times | $\mathcal{O}(|V|+|E|)$ |
| Back edges in DFS | Indicate cycles in directed graphs | — |
| Topological sort | Decreasing post number, or repeated source removal | $\mathcal{O}(|V|+|E|)$ |
9. Practice Problems
- Apply the Master Theorem to solve:
- a) $T(n) = 2T(n/4) + \sqrt{n}$
- b) $T(n) = 2T(n/2) + n^2$
- c) $T(n) = 4T(n/2) + n^2$
- d) $T(n) = 8T(n/2) + n^2$
-
Trace Karatsuba’s algorithm on $x = 1234$, $y = 5678$ (use base 100 splitting: $x_L = 12$, $x_R = 34$, $y_L = 56$, $y_R = 78$).
-
Trace binary search for $v = 38$ in $A = [2, 5, 8, 12, 16, 23, 38, 56]$. Show each step.
-
Trace merge sort on $A = [3, 1, 4, 1, 5, 9, 2, 6]$. Show the recursion tree and all merge steps.
-
Prove that the lower bound for comparison-based sorting is $\Omega(n \log n)$. (Hint: count the number of leaves in a decision tree.)
-
For a graph with 5 vertices and edges $\{(1,2),(1,3),(2,3),(3,4),(4,5),(5,1)\}$: draw the adjacency matrix and adjacency list representations.
-
Run DFS on the directed graph: $V = \{1,2,3,4\}$, $E = \{(1,2),(2,3),(3,1),(1,4)\}$. Record pre and post times. Identify the back edge.
-
Show that in a DFS on an undirected graph, every edge is either a tree edge or a back edge (no forward or cross edges exist).
-
Explain why DFS runs in $\mathcal{O}(|V| + |E|)$ time when using adjacency lists.
-
Challenge: Implement merge sort in Python and verify it gives the correct output for A = [9, 4, 7, 2, 5, 1, 8, 3, 6].
-
Draw a decision tree that sorts two elements $a_1, a_2$ by comparisons. How many leaves does it have, and how does this match $2! = 2$?
-
For the DAG with vertices $\{P,Q,R,S,T\}$ and edges $P\to Q$, $P\to R$, $Q\to S$, $R\to S$, $S\to T$: (a) find a topological order using DFS and decreasing post numbers; (b) find a topological order using repeated source removal; (c) identify all sources and all sinks.
- Prove that $n! \geq (n/2)^{n/2}$, and use it to show $\log_2(n!) = \Omega(n\log n)$ (fill in the two steps used in Section 5.5’s proof, in your own words).