CSE 2207 — Algorithms
ALGORITHM WRITING QUESTIONS
Ahsanullah University of Science and Technology
Department of CSE | [Link]. CSE — Year 2, Semester 2
Questions sorted by topic, with appearance frequency and full answers.
Topic Overview — Algorithm Questions
Topics ranked by number of appearances across all semesters.
# Topic Appearanc
es
1 Single Source Shortest Paths (Dijkstra & Bellman-Ford) 29
2 Minimum Spanning Tree (Prim's & Kruskal's) 23
3 Huffman Codes 9
4 Greedy Method — Fractional Knapsack 5
5 Activity Selection Problem 6
6 Backtracking — N-Queens Problem 8
7 Backtracking — Sum of Subsets 5
8 Dynamic Programming — LCS 13
9 Dynamic Programming — Matrix Chain Multiplication 10
10 Dynamic Programming — 0/1 Knapsack 5
11 Topological Sort 8
12 Merge Sort Analysis 4
13 Quicksort Analysis 10
14 Case Analysis — Heap & Priority Queue 3
15 Case Analysis — Binary Search Tree 4
16 Case Analysis — BFS 4
Topic 1 — Single Source Shortest Paths [29 appearances]
1.1 Dijkstra's Algorithm
Q1. Write down Dijkstra's algorithm. Compute its running complexity considering the priority
queue is implemented with a heap data structure.
Appeared: 2× | Fall 2020, Spring 2021
ANSWER:
Dijkstra's algorithm is a greedy algorithm that solves the single-source shortest-paths problem
on a weighted, directed graph with non-negative edge weights.
INITIALIZE-SINGLE-SOURCE(G, s):
for each v in G.V
v.d ← ∞
v.π ← NIL
s.d ← 0
RELAX(u, v, w):
if v.d > u.d + w(u,v)
v.d ← u.d + w(u,v)
v.π ← u
DIJKSTRA(G, w, s):
1. INITIALIZE-SINGLE-SOURCE(G, s)
2. S ← ∅
3. Q ← G.V // min-priority queue keyed by d values
4. while Q ≠ ∅
5. u ← EXTRACT-MIN(Q)
6. S ← S ∪ {u}
7. for each vertex v in [Link][u]
8. RELAX(u, v, w)
Complexity Analysis:
• With a binary min-heap: O((V + E) lg V) — each EXTRACT-MIN: O(lg V), called V times; each
DECREASE-KEY: O(lg V), called at most E times.
• With a Fibonacci heap: O(V lg V + E) — amortized O(1) for DECREASE-KEY.
Q2. Write down Dijkstra's algorithm that solves the single source shortest path problem.
(Theory/definition question.)
Appeared: 2× | Spring 2022, Spring 2019
ANSWER:
Same algorithm as above. Key properties: Dijkstra's is a greedy algorithm. It assumes all edge
weights are non-negative. It maintains a set S of vertices whose final shortest-path weights from
source s are already determined, and repeatedly selects the minimum-weight-estimate vertex
from V−S.
1.2 DAG Shortest Paths
Q3. Write down the most efficient algorithm that solves the single source shortest paths problem
for a Directed Acyclic Graph (DAG). Also define the 'single source shortest paths' problem.
Appeared: 1× | Fall 2022
ANSWER:
Definition: Given a weighted directed graph G=(V,E) and a source vertex s, find the shortest
(minimum-weight) path from s to every other vertex v ∈ V.
DAG-SHORTEST-PATHS(G, w, s):
1. Topologically sort the vertices of G
2. INITIALIZE-SINGLE-SOURCE(G, s)
3. for each vertex u taken in topologically sorted order
4. for each vertex v in [Link][u]
5. RELAX(u, v, w)
Complexity: O(V + E) — faster than Dijkstra because the DAG structure allows a single linear
pass after topological sort.
1.3 Bellman-Ford Algorithm
Q4. Write down the Bellman-Ford algorithm and justify with a suitable example that this
algorithm can detect negative-weight cycles on a weighted, directed graph.
Appeared: 5× | Fall 2024, Fall 2022, Fall 2021, Spring 2022, Spring 2023
ANSWER:
BELLMAN-FORD(G, w, s):
1. INITIALIZE-SINGLE-SOURCE(G, s)
2. for i = 1 to |G.V| - 1
3. for each edge (u,v) in G.E
4. RELAX(u, v, w)
5. for each edge (u,v) in G.E
6. if v.d > u.d + w(u,v)
7. return FALSE // negative-weight cycle detected
8. return TRUE
Complexity: O(VE)
Negative-weight cycle detection: After |V|−1 relaxations, if any edge (u,v) can still be relaxed
(i.e., v.d > u.d + w(u,v)), a negative-weight cycle is reachable from s — the algorithm returns
FALSE.
Example: Consider a graph with vertices {A, B, C} and edges: A→B (weight 1), B→C (weight
−3), C→B (weight 1). After |V|−1 = 2 passes, check edge B→C: if d[C] > d[B] + (−3) is still
possible, a cycle B→C→B of total weight −2 exists. Algorithm returns FALSE.
Topic 2 — Minimum Spanning Tree [23 appearances]
2.1 Prim's Algorithm
Q5. Write down Prim's algorithm to find a Minimum Spanning Tree.
Appeared: 2× | Spring 2022, Fall 2022
ANSWER:
MST-PRIM(G, w, r):
1. for each u in G.V
2. [Link] ← ∞
3. u.π ← NIL
4. [Link] ← 0
5. Q ← G.V // min-priority queue by key
6. while Q ≠ ∅
7. u ← EXTRACT-MIN(Q)
8. for each v in [Link][u]
9. if v ∈ Q and w(u,v) < [Link]
10. v.π ← u
11. [Link] ← w(u,v)
Complexity: O(E lg V) with binary heap; O(V lg V + E) with Fibonacci heap.
2.2 Kruskal's Algorithm
Q6. Write down Kruskal's algorithm to find a Minimum Spanning Tree.
Appeared: 1× | Spring 2019
ANSWER:
MST-KRUSKAL(G, w):
1. A ← ∅
2. for each vertex v in G.V
3. MAKE-SET(v)
4. Sort edges of G.E in non-decreasing order by weight w
5. for each edge (u,v) in sorted order
6. if FIND-SET(u) ≠ FIND-SET(v)
7. A ← A ∪ {(u,v)}
8. UNION(u, v)
9. return A
Complexity: O(E lg E) = O(E lg V). Sorting edges dominates. The disjoint-set operations run in
nearly O(1) amortized with union-by-rank and path compression.
Topic 3 — Huffman Codes [9 appearances]
Q7. Write a greedy strategic algorithm that constructs the optimal Huffman code for a given set
of characters with their frequencies.
Appeared: 4× | Fall 2024, Spring 2023, Fall 2021, Fall 2018
ANSWER:
HUFFMAN(C): // C = set of characters with frequencies [Link]
n ← |C|
Q ← C // min-priority queue ordered by freq
for i = 1 to n-1
z ← ALLOCATE-NODE()
[Link] ← x ← EXTRACT-MIN(Q)
[Link] ← y ← EXTRACT-MIN(Q)
[Link] ← [Link] + [Link]
INSERT(Q, z)
return EXTRACT-MIN(Q) // root of the Huffman tree
Complexity: O(n lg n) using a min-priority queue (heap). Each EXTRACT-MIN and INSERT is
O(lg n), called O(n) times.
Encoding rule: Left branch = 0, Right branch = 1 (or vice versa, consistently). The code for each
character is the sequence of bits on the path from root to leaf.
Algorithm also used when called: Write an algorithm for the Huffman code (Spring 2018 — 1×).
Topic 4 — Greedy Method: Fractional Knapsack [5
appearances]
Q8. Write a greedy strategic algorithm to solve the fractional knapsack problem.
Appeared: 3× | Spring 2024, Spring 2023, Spring 2022
ANSWER:
Strategy: Sort items by profit/weight ratio in decreasing order. Greedily take as much as
possible of the highest-ratio item, then the next, and so on.
FRACTIONAL-KNAPSACK(v, w, W):
// v[1..n] = values, w[1..n] = weights, W = capacity
for i = 1 to n
ratio[i] ← v[i] / w[i]
Sort items by ratio[i] in non-increasing order
totalValue ← 0
remaining ← W
for i = 1 to n (in sorted order)
if w[i] <= remaining
take all of item i
totalValue ← totalValue + v[i]
remaining ← remaining − w[i]
else
fraction ← remaining / w[i]
totalValue ← totalValue + fraction · v[i]
break
return totalValue
Sahni's version (Algorithm 4.3):
GreedyKnapsack(m, n):
// P[1:n] and w[1:n] sorted so that p[i]/w[i] >= p[i+1]/w[i+1]
// m = knapsack size, x[1:n] = solution vector
{
for i = 1 to n do x[i] = 0; // Initialize x
U = m;
for i = 1 to n do {
if (w[i] > U) then break;
x[i] = 1; U = U - w[i];
}
if (i <= n) then x[i] = U / w[i];
}
Complexity: O(n lg n) due to sorting.
Topic 5 — Activity Selection Problem [6 appearances]
5.1 Recursive Algorithm
Q9. Write a recursive greedy algorithm to find the maximum-sized subset of mutually compatible
activities.
Appeared: 2× | Fall 2024, Fall 2022
ANSWER:
RECURSIVE-ACTIVITY-SELECTOR(s, f, k, n):
// s[i] = start time, f[i] = finish time
// activities sorted in non-decreasing order by finish time
// k = index of most recently added activity, n = total activities
m ← k + 1
while m <= n and s[m] < f[k]
m ← m + 1 // find first activity finishing after f[k]
if m <= n
return {a_m} ∪ RECURSIVE-ACTIVITY-SELECTOR(s, f, m, n)
else
return ∅
Call: Add fictitious activity a₀ with f[0] = 0, then call RECURSIVE-ACTIVITY-SELECTOR(s, f, 0,
n).
5.2 Iterative (Greedy) Algorithm
Q10. Write an iterative (greedy) algorithm to find the maximum-sized subset of mutually
compatible activities.
Appeared: 4× | Spring 2024, Fall 2023, Fall 2022, Spring 2022
ANSWER:
GREEDY-ACTIVITY-SELECTOR(s, f):
// activities sorted in non-decreasing order of finish time
n ← [Link]
A ← {a₁}
k ← 1
for m = 2 to n
if s[m] >= f[k] // activity m compatible with last selected
A ← A ∪ {a_m}
k ← m
return A
Complexity: O(n lg n) for sorting + O(n) for selection = O(n lg n).
Topic 6 — Backtracking: N-Queens Problem [8 appearances]
Q11. Write a backtracking algorithm for the N-queens problem.
Appeared: 5× | Spring 2024, Spring 2023, Spring 2022, Spring 2021, Spring 2019, Spring 2018
ANSWER:
N-QUEENS(board, col, n):
if col == n
PRINT-SOLUTION(board)
return
for row = 0 to n-1
if IS-SAFE(board, row, col)
board[row][col] ← 1 // place queen
N-QUEENS(board, col+1, n)
board[row][col] ← 0 // backtrack (remove queen)
IS-SAFE(board, row, col):
// Check same row on left side
for i = 0 to col-1
if board[row][i] == 1: return false
// Check upper-left diagonal
for i, j = row-1, col-1; i >= 0 and j >= 0; i--, j--
if board[i][j] == 1: return false
// Check lower-left diagonal
for i, j = row+1, col-1; i < n and j >= 0; i++, j--
if board[i][j] == 1: return false
return true
The algorithm places queens column by column. For each column, it tries every row. If
placement is safe (no conflicts), it recurses to the next column. If no safe row is found, it
backtracks.
Topic 7 — Backtracking: Sum of Subsets [5 appearances]
Q12. Write a backtracking algorithm for the sum of subsets problem. Analyze the algorithm.
Appeared: 5× | Fall 2024, Fall 2023, Fall 2022, Fall 2021, Fall 2018
ANSWER:
SUM-OF-SUBSETS(w, i, m, r, x):
// w[1..n] = sorted weights, m = remaining capacity
// r = sum of w[i..n], x[1..n] = inclusion vector
x[i] ← 1 // include w[i]
if w[i] == m
PRINT(x) // solution found
else
if w[i] < m and w[i] < r // include w[i] and recurse
SUM-OF-SUBSETS(w, i+1, m-w[i], r-w[i], x)
x[i] ← 0 // backtrack: exclude w[i]
if (r - w[i]) >= m and (m > 0) // still possible to find solution
SUM-OF-SUBSETS(w, i+1, m, r-w[i], x)
Analysis: The state space tree is a binary tree of depth n. Each left branch includes item i, right
branch excludes it. Pruning condition: remaining sum r − w[i] ≥ m ensures there is still enough
remaining weight to reach the target; m > 0 ensures goal is not already met.
Worst case: O(2ⁿ) nodes. Pruning significantly reduces average-case exploration.
Topic 8 — Dynamic Programming: LCS [13 appearances]
Q13. Write algorithms to find and print the Longest Common Subsequence (LCS) and its length
for two given sequences.
Appeared: 4× | Fall 2024, Fall 2022, Fall 2021, Spring 2019
ANSWER:
LCS-LENGTH(X, Y):
m ← [Link]
n ← [Link]
let c[0..m, 0..n] and b[1..m, 1..n] be tables
for i = 1 to m: c[i,0] ← 0
for j = 0 to n: c[0,j] ← 0
for i = 1 to m
for j = 1 to n
if X[i] == Y[j]
c[i,j] ← c[i-1,j-1] + 1
b[i,j] ← "↖"
elseif c[i-1,j] >= c[i,j-1]
c[i,j] ← c[i-1,j]
b[i,j] ← "↑"
else
c[i,j] ← c[i,j-1]
b[i,j] ← "←"
return c and b
PRINT-LCS(b, X, i, j):
if i == 0 or j == 0: return
if b[i,j] == "↖"
PRINT-LCS(b, X, i-1, j-1)
print X[i]
elseif b[i,j] == "↑"
PRINT-LCS(b, X, i-1, j)
else
PRINT-LCS(b, X, i, j-1)
Complexity: O(mn) time and O(mn) space. The b table allows traceback to print the actual LCS.
Call PRINT-LCS(b, X, m, n).
Topic 9 — Dynamic Programming: Matrix Chain
Multiplication [10 appearances]
Q14. Write an algorithm to calculate the optimal sequence to multiply a matrix chain.
Appeared: 2× | Spring 2024, Spring 2022
ANSWER:
MATRIX-CHAIN-ORDER(p):
// p[0..n] where matrix Aᵢ has dimensions p[i-1] × p[i]
n ← [Link] - 1
let m[1..n, 1..n] and s[1..n-1, 2..n] be tables
for i = 1 to n: m[i,i] ← 0 // single matrix: zero cost
for l = 2 to n // l = chain length
for i = 1 to n-l+1
j ← i + l - 1
m[i,j] ← ∞
for k = i to j-1
q ← m[i,k] + m[k+1,j] + p[i-1]·p[k]·p[j]
if q < m[i,j]
m[i,j] ← q
s[i,j] ← k // record optimal split point
return m and s
PRINT-OPTIMAL-PARENS(s, i, j):
if i == j: print "A_i"
else
print "("
PRINT-OPTIMAL-PARENS(s, i, s[i,j])
PRINT-OPTIMAL-PARENS(s, s[i,j]+1, j)
print ")"
Complexity: O(n³) time, O(n²) space.
Topic 10 — Dynamic Programming: 0/1 Knapsack [5
appearances]
Q15. Write the dynamic programming algorithm for the 0-1 knapsack problem.
Appeared: 3× | Fall 2023, Spring 2022, Fall 2018
ANSWER:
01-KNAPSACK(v, w, n, W):
// v[1..n] = values, w[1..n] = weights, W = capacity
let V[0..n, 0..W] be a table
for i = 0 to n: V[i,0] ← 0 // zero capacity → zero value
for j = 0 to W: V[0,j] ← 0 // zero items → zero value
for i = 1 to n
for j = 1 to W
if w[i] > j
V[i,j] ← V[i-1,j] // item too heavy, skip it
else
V[i,j] ← max(V[i-1,j], v[i] + V[i-1, j-w[i]])
// max of: skip item i OR take item i
return V[n,W]
Complexity: O(nW) time and O(nW) space (pseudo-polynomial — W may be exponential in
input size).
To retrieve which items were selected: trace back through the table from V[n,W], checking if
V[i,j] ≠ V[i-1,j] to determine if item i was included.
Topic 11 — Topological Sort [8 appearances]
Q16. Write a topological sorting algorithm.
Appeared: 3× | Spring 2023, Spring 2022, Spring 2019
ANSWER:
TOPOLOGICAL-SORT(G):
Call DFS(G) to compute finish times v.f for each vertex v
As each vertex is finished, insert it onto the front of a linked list
return the linked list
DFS(G):
for each vertex u in G.V
[Link] ← WHITE
u.π ← NIL
time ← 0
for each vertex u in G.V
if [Link] == WHITE
DFS-VISIT(G, u)
DFS-VISIT(G, u):
time ← time + 1
u.d ← time // discovery time
[Link] ← GRAY
for each v in [Link][u]
if [Link] == WHITE
v.π ← u
DFS-VISIT(G, v)
[Link] ← BLACK
time ← time + 1
u.f ← time // finish time
// Insert u at FRONT of linked output list
Complexity: O(V + E). The DFS itself runs in O(V + E); inserting each vertex at the front of the
list is O(1) per vertex.
Note: Topological sort is only valid on a Directed Acyclic Graph (DAG). The resulting list gives a
linear ordering where for every directed edge u → v, u appears before v.
Topic 12 — Merge Sort Analysis [4 appearances]
Q17. Write the algorithm for merge sort. Analyze the algorithm and show that running time is
O(n lg n).
Appeared: 4× | Spring 2024, Fall 2022, Fall 2021, Spring 2018
ANSWER:
MERGE-SORT(A, p, r):
if p < r
q ← floor((p+r)/2)
MERGE-SORT(A, p, q)
MERGE-SORT(A, q+1, r)
MERGE(A, p, q, r)
MERGE(A, p, q, r):
n₁ ← q - p + 1; n₂ ← r - q
let L[1..n₁+1] and R[1..n₂+1] be arrays
for i = 1 to n₁: L[i] ← A[p+i-1]
for j = 1 to n₂: R[j] ← A[q+j]
L[n₁+1] ← ∞; R[n₂+1] ← ∞ // sentinel values
i ← 1; j ← 1
for k = p to r
if L[i] <= R[j]
A[k] ← L[i]; i ← i + 1
else
A[k] ← R[j]; j ← j + 1
Recurrence: T(n) = 2T(n/2) + Θ(n), T(1) = Θ(1)
Solution by Master Theorem (Case 2): a = 2, b = 2, f(n) = Θ(n), n^(log_b a) = n^1 → f(n) =
Θ(n^(log_b a)) → T(n) = Θ(n lg n).
Topic 13 — Quicksort Analysis [10 appearances]
Q18. Write the algorithm for Quicksort. Compute its average case running complexity.
Appeared: 8× | Spring 2024, Fall 2022, Spring 2022, Fall 2021, Fall 2020, Fall 2019, Spring 2019, Fall 2018
ANSWER:
QUICKSORT(A, p, r):
if p < r
q ← PARTITION(A, p, r)
QUICKSORT(A, p, q-1)
QUICKSORT(A, q+1, r)
PARTITION(A, p, r):
x ← A[r] // pivot = last element
i ← p - 1
for j = p to r-1
if A[j] <= x
i ← i + 1
exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i + 1
Average case analysis:
Assuming all permutations equally likely, each element is equally likely to be the pivot. The
recurrence is:
T(n) = (1/n) · Σ[q=0 to n-1] [T(q) + T(n−1−q)] + Θ(n)
Solution: T(n) = Θ(n lg n)
Worst case: When pivot is always the smallest or largest element → T(n) = T(n−1) + Θ(n) →
T(n) = Θ(n²).
Topic 14 — Case Analysis: Heap & Priority Queue [3
appearances]
Q19. Write down the algorithms for insertion into a heap and for extraction of maximum from a
heap. What are their Big-Oh complexities?
Appeared: 1× | Spring 2018
ANSWER:
MAX-HEAP-INSERT(A, key):
[Link]-size ← [Link]-size + 1
A[[Link]-size] ← -∞
HEAP-INCREASE-KEY(A, [Link]-size, key)
HEAP-INCREASE-KEY(A, i, key):
if key < A[i]: error "new key is smaller than current key"
A[i] ← key
while i > 1 and A[PARENT(i)] < A[i]
exchange A[i] with A[PARENT(i)]
i ← PARENT(i)
HEAP-EXTRACT-MAX(A):
if [Link]-size < 1: error "heap underflow"
max ← A[1]
A[1] ← A[[Link]-size]
[Link]-size ← [Link]-size - 1
MAX-HEAPIFY(A, 1)
return max
MAX-HEAPIFY(A, i):
l ← LEFT(i); r ← RIGHT(i)
largest ← i
if l <= [Link]-size and A[l] > A[largest]: largest ← l
if r <= [Link]-size and A[r] > A[largest]: largest ← r
if largest ≠ i
exchange A[i] with A[largest]
MAX-HEAPIFY(A, largest)
Complexities: Both INSERT and EXTRACT-MAX are O(lg n) because the heap has height ⌊lg
n⌋.
Topic 15 — Case Analysis: Binary Search Tree [4
appearances]
Q20. Write an algorithm to search an item from a Binary Search Tree. Analyze it to compute its
best case and worst case runtime complexities.
Appeared: 4× | Fall 2024, Fall 2023, Fall 2021, Spring 2023
ANSWER:
TREE-SEARCH(x, k): // recursive version
if x == NIL or k == [Link]
return x
if k < [Link]
return TREE-SEARCH([Link], k)
else
return TREE-SEARCH([Link], k)
ITERATIVE-TREE-SEARCH(x, k): // iterative (more efficient in practice)
while x ≠ NIL and k ≠ [Link]
if k < [Link]
x ← [Link]
else
x ← [Link]
return x
Worst case: O(h) where h is the height of the tree. For a skewed tree (degenerate/sorted input),
h = n → O(n).
Best case: O(1) — the key is at the root.
Balanced BST: h = lg n → O(lg n).
Topic 16 — Case Analysis: Breadth First Search [4
appearances]
Q21. Write an algorithm for Breadth First Search (BFS). Analyze its worst case scenario and
compute its worst case time complexity.
Appeared: 4× | Fall 2022, Fall 2019, Spring 2022, Spring 2018
ANSWER:
BFS(G, s):
for each vertex u in G.V - {s}
[Link] ← WHITE
u.d ← ∞
u.π ← NIL
[Link] ← GRAY
s.d ← 0
s.π ← NIL
Q ← ∅
ENQUEUE(Q, s)
while Q ≠ ∅
u ← DEQUEUE(Q)
for each v in [Link][u]
if [Link] == WHITE
[Link] ← GRAY
v.d ← u.d + 1
v.π ← u
ENQUEUE(Q, v)
[Link] ← BLACK
Worst case scenario: A complete graph where every vertex is connected to every other vertex
— the queue processes all vertices and all adjacency lists are fully traversed.
Complexity: Each vertex is enqueued/dequeued once → O(V). Each adjacency list is scanned
once total → O(E). Total: O(V + E).