Data Structures and Algorithms Exam Review

Posted on Jan 14, 2026 in Computer Engineering

1) Recurrences

1.1 10-mark: Solve T(n)=2T(n/2)+n, T(1)=c

T(n)=2T(n/2)+n
=4T(n/4)+2n
=8T(n/8)+3n
… after i steps: T(n)=2i T(n/2i) + i*n
Stop: n/2i=1 => i=log2 n
T(n)=n*T(1) + n log2 n = n*c + n log2 n
=> T(n)=Θ(n log n)

1.2 Master Theorem (Write As-Is)

T(n)=aT(n/b)+f(n), compare f(n) with nlogb a

  • Case 1: f(n)=O(nlogb a – ε) => T(n)=Θ(nlogb a)
  • Case 2: f(n)=Θ(nlogb a logk n) => T(n)=Θ(nlogb a logk+1 n)
  • Case 3: f(n)=Ω(nlogb a + ε) and a f(n/b) ≤ c f(n) (c<1) => T(n)=Θ(f(n))

2) Sorting

2.1 10-mark: Selection Sort (Algorithm + Full Trace + Counts)

SelectionSort(A):
for i=0..n-2:
    min=i
    for j=i+1..n-1:
        if A[j] < A[min]: min=j
    if min!=i: swap(A[i],A[min])

A0=[28,13,12,28,35,11,15, 9,36]

  • P1 swap(28,9) → [ 9,13,12,28,35,11,15,28,36]
  • P2 swap(13,11) → [ 9,11,12,28,35,13,15,28,36]
  • P3 no swap      → [ 9,11,12,28,35,13,15,28,36]
  • P4 swap(28,13) → [ 9,11,12,13,35,28,15,28,36]
  • P5 swap(35,15) → [ 9,11,12,13,15,28,35,28,36]
  • P6 no swap      → [ 9,11,12,13,15,28,35,28,36]
  • P7 swap(35,28) → [ 9,11,12,13,15,28,28,35,36]

Sorted=[9,11,12,13,15,28,28,35,36]
Comparisons: n(n-1)/2; for n=9 ⇒ 36.
Copies: 1 swap=3 copies; swaps=5 ⇒ 15 copies.
Time Θ(n2), Space Θ(1).

2.2 10-mark: Merge Sort (Algorithm + Complete Example)

MergeSort(A,l,r):
if l≥r: return
mid=(l+r)//2
MergeSort(A,l,mid)
MergeSort(A,mid+1,r)
Merge(A,l,mid,r)
Merge(A,l,mid,r): merge sorted A[l..mid] and A[mid+1..r]

A=[8,3,2,9,7,1,5,4]
Split → [8,3,2,9] | [7,1,5,4]
Split → [8,3]|[2,9]   and   [7,1]|[5,4]
Singletons → [8][3][2][9][7][1][5][4]
Merge pairs → [3,8] [2,9] [1,7] [4,5]
Merge size-4 → [2,3,8,9] and [1,4,5,7]
Final → [1,2,3,4,5,7,8,9]
Time Θ(n log n), Space Θ(n).

2.3 10-mark: Quick Sort (Lomuto) (Algorithm + Full Partition Changes)

Partition(A,l,r): pivot=A[r]; i=l-1
for j=l..r-1:
    if A[j]≤pivot: i++; swap(A[i],A[j])
swap(A[i+1],A[r]); return i+1
QuickSort(A,l,r): if l<r: p=Partition(A,l,r); QuickSort(A,l,p-1); QuickSort(A,p+1,r)

A=[10,2,5,15,50,6,20,25], pivot=25
Swaps (only when array changes):
j=5 swap(50,6) → [10,2,5,15,6,50,20,25]
j=6 swap(50,20) → [10,2,5,15,6,20,50,25]
Final swap(pivot with 50) → [10,2,5,15,6,20,25,50], p=6
Best/avg Θ(n log n), worst Θ(n2); avg stack Θ(log n).

3) Graph Algorithms

3.1 10-mark: BFS (Queue) + BFS Spanning Tree (parent[])

BFS(G,s):
for each v: visited=false; parent=NIL
visited[s]=true; enqueue(s)
while Q not empty:
    u=dequeue
    for v in Adj[u]:
        if not visited[v]: visited[v]=true; parent[v]=u; enqueue(v)

Adj: A:{B,C}, B:{A,D,E}, C:{A,F}, D:{B}, E:{B,F}, F:{C,E}; start A
Q=[A]
Deq A → enq B,C; parent[B]=A,parent[C]=A; Q=[B,C]
Deq B → enq D,E; parent[D]=B,parent[E]=B; Q=[C,D,E]
Deq C → enq F;          parent[F]=C;          Q=[D,E,F]
Deq D → -; Q=[E,F]
Deq E → -; Q=[F]
Deq F → -; Q=[]
Order: A,B,C,D,E,F
Tree edges: A-B, A-C, B-D, B-E, C-F
Adj list Θ(V+E); matrix Θ(V2).

3.2 10-mark: DFS (Recursion) + DFS Spanning Tree (parent[])

DFS(G): for each v visited=false,parent=NIL; for each v if not visited[v] DFSVisit(v)
DFSVisit(u): visited[u]=true; for v in Adj[u] if not visited[v]: parent[v]=u; DFSVisit(v)

Same graph; neighbors alphabetical; start A
A→B (par[B]=A)
B→D (par[D]=B) back
B→E (par[E]=B)
E→F (par[F]=E)
F→C (par[C]=F) back; done
One order: A,B,D,E,F,C
Tree edges: A-B, B-D, B-E, E-F, F-C
Θ(V+E) (adj list).

3.3 10-mark: Topological Sort (Kahn) (Full Indegree Updates)

TopoKahn(G): compute indegree; Q=all indegree 0
while Q: u=pop; output u; for v in Adj[u]: indegree[v]--; if 0 push
if output count < V => cycle

Edges: 1->2,1->4,2->3,2->4,3->5,4->5,4->7,5->6,7->8,8->6
Deg: 1:0 2:1 3:1 4:2 5:2 6:2 7:1 8:1; Q=[1]
Pop 1: out[1]; deg2=0,deg4=1; Q=[2]
Pop 2: out[1,2]; deg3=0,deg4=0; Q=[3,4]
Pop 3: out[1,2,3]; deg5=1; Q=[4]
Pop 4: out[1,2,3,4]; deg5=0,deg7=0; Q=[5,7]
Pop 5: out[1,2,3,4,5]; deg6=1; Q=[7]
Pop 7: out[1,2,3,4,5,7]; deg8=0; Q=[8]
Pop 8: out[1,2,3,4,5,7,8]; deg6=0; Q=[6]
Pop 6: out[1,2,3,4,5,7,8,6]; done; Θ(V+E).

4) Minimum Spanning Tree (MST)

4.1 10-mark: Prim (Algorithm + Full Key/Parent Run)

Prim(G,start): for v key=INF,parent=NIL,inMST=false; key[start]=0
Repeat V times: pick u (min key, not inMST); inMST[u]=true
    for (u,v,w): if not inMST[v] and w<key[v]: key[v]=w; parent[v]=u
Output edges (parent[v],v) for v!=start

Edges: A-B(7), A-C(3), C-D(2), B-D(1), D-E(5); start A
Init key: A=0, B=INF, C=INF, D=INF, E=INF
Pick A: key[B]=7 par[B]=A; key[C]=3 par[C]=A
Pick C: key[D]=2 par[D]=C
Pick D: key[B]=1 par[B]=D; key[E]=5 par[E]=D
Pick B: –
Pick E: –
MST: (A,C,3) (C,D,2) (D,B,1) (D,E,5); total=11
Matrix Θ(V2); list+heap O(E log V).

4.2 10-mark: Kruskal (Algorithm + Full DSU Selection)

Kruskal(G): sort edges by w; MakeSet(v)
for (u,v,w) in sorted:
    if Find(u)!=Find(v): take edge; Union(u,v)
stop when V-1 edges

Sorted: (B,D,1) (C,D,2) (A,C,3) (D,E,5) (A,B,7)
Sets: {A}{B}{C}{D}{E}
Take (B,D,1) → {B,D}
Take (C,D,2) → {B,C,D}
Take (A,C,3) → {A,B,C,D}
Take (D,E,5) → {A,B,C,D,E} stop
MST edges same; total=11
Time O(E log E) + DSU (almost linear).

5) Shortest Paths

5.1 10-mark: Dijkstra (Algorithm + Full Distances + Path)

Dijkstra(G,s): init dist=INF,parent=NIL,visited=false; dist[s]=0
Repeat V times: pick unvisited u with min dist; visited[u]=true
    for (u,v,w): if not visited[v] and dist[u]+w<dist[v]: dist[v]=dist[u]+w; parent[v]=u

Edges: a-b(2),a-c(7),a-e(10),b-d(2),c-d(1),c-g(2),d-f(2),e-g(1),f-g(2); source a
Init: a=0, b=2, c=7, d=INF, e=10, f=INF, g=INF
Pick b(2): d=4 par[d]=b
Pick d(4): f=6 par[f]=d
Pick f(6): g=8 par[g]=f
Pick c(7): d via c=8 (no), g via c=9 (no)
Pick g(8); pick e(10): e→g=11 (no)
Final dist: a=0, b=2, c=7, d=4, e=10, f=6, g=8
Path a→g: a-b-d-f-g
Heap O((V+E)logV); matrix Θ(V2).

5.2 10-mark: Floyd–Warshall (Algorithm + D0 + Updates + Final D)

Floyd(W): D=W
for k=1..V: for i=1..V: for j=1..V: D[i][j]=min(D[i][j], D[i][k]+D[k][j])

V=4; edges: 1->2(4),1->3(8),2->3(1),2->4(7),3->4(2),4->1(3)
D0:
[0, 4, 8, INF]
[INF, 0, 1, 7]
[INF, INF, 0, 2]
[3, INF, INF, 0]
Updates: k=1: 4->2=7, 4->3=11; k=2: 1->3=5, 1->4=11, 4->3=8; k=3: 1->4=7, 2->4=3; k=4: 2->1=6, 3->1=5, 3->2=9
Dfinal:
[0, 4, 5, 7]
[6, 0, 1, 3]
[5, 9, 0, 2]
[3, 7, 8, 0]
Θ(V3) time; Θ(V2) space.

6) Dynamic Programming

6.1 10-mark: 0/1 Knapsack (Full DP Table + Backtracking)

DP[i][w]=DP[i-1][w] if Wi>w else max(DP[i-1][w], Pi+DP[i-1][w-Wi])
Backtrack: if DP[i][w]!=DP[i-1][w], take i and w=w-Wi

M=12; P=(1,6,18,22,28,43); W=(1,2,5,6,7,10)
i=0: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
i=1: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
i=2: [0, 1, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]
i=3: [0, 1, 6, 7, 7, 18, 19, 24, 25, 25, 25, 25, 25]
i=4: [0, 1, 6, 7, 7, 18, 22, 24, 28, 29, 29, 40, 41]
i=5: [0, 1, 6, 7, 7, 18, 22, 28, 29, 34, 35, 40, 46]
i=6: [0, 1, 6, 7, 7, 18, 22, 28, 29, 34, 43, 44, 49]
Backtrack: take item 6 (w=10,p=43) → w=2; take item 2 (w=2,p=6) → w=0; items {2,6}; profit=49
Time Θ(nM), Space Θ(nM).

7) String Matching

7.1 10-mark: Naïve Matching (Algorithm + Complete Example in One Line)

NaiveMatch(T,P): for s=0..n-m: compare P with T[s..s+m-1]; if all match report s
Worst-case O(nm)
Example: T=ABABCABABCAB, P=ABABC → matches at shifts s=0 and s=5.

7.2 10-mark: KMP (Build LPS + Match) (Full LPS + Match Result)

BuildLPS(P): lps[0]=0; len=0; i=1
while i<m:
    if P[i]==P[len]: len++; lps[i]=len; i++
    else if len!=0: len=lps[len-1]
    else: lps[i]=0; i++
KMPMatch(T,P): i=0,j=0; on mismatch set j=lps[j-1] (if j>0) else i++

P=ABABCABAB ⇒ LPS=[0,0,1,2,0,1,2,3,4]
Build: i=1→0; i=2→1; i=3→2; i=4 mismatch→0; i=5→1; i=6→2; i=7→3; i=8→4
T=ABABDABABCABABX, P=ABABCABAB ⇒ first full match starts at index 5
Time Θ(n+m), Space Θ(m).

8) Comparisons + Short Notes (5 Marks)

8.1 BFS vs DFS

BFS: level-order, uses a queue, finds shortest path in unweighted graph, may use more memory. DFS: depth-first, uses a stack/recursion, good for cycles/topological sort/connectivity. Both are Θ(V+E) (adj list).

8.2 Adjacency Matrix vs List

Matrix: space Θ(V2), edge test O(1), traversal Θ(V2), best for dense graphs. List: space Θ(V+E), edge test O(degree), traversal Θ(V+E), best for sparse graphs.

8.3 Prim vs Kruskal

Prim: grows one tree from a starting vertex (uses key[] array, often a heap), efficient for dense graphs. Kruskal: sorts all edges + uses DSU, efficient for sparse graphs. Both output an MST.

8.4 Dijkstra vs Floyd

Dijkstra: single-source shortest path, requires non-negative weights, complexity O((V+E)logV) with a heap. Floyd–Warshall: all-pairs shortest path, allows negative edges (but no negative cycles), complexity Θ(V3).

8.5 Spanning Tree vs MST

A Spanning Tree has V-1 edges, connects all vertices, and contains no cycles. An MST is a spanning tree with the minimum possible total edge weight. BFS/DFS produce a spanning tree; Prim/Kruskal produce an MST.

8.6 DAG + Topological Order

A DAG is a Directed Acyclic Graph. A Topological Order is a linear ordering of vertices such that for every edge u→v, vertex u comes before vertex v in the ordering. It exists if and only if the graph is a DAG; used in scheduling/prerequisites.

8.7 NP-Complete + Reduction (Safe)

P: solvable in polynomial time. NP: verifiable in polynomial time. NP-Complete: in NP and NP-hard (e.g., CNF-SAT). A≤pB means A can be transformed to B in polynomial time. If A is NP-complete and A≤pB and B is in NP, then B is NP-complete.