Session- 2024-2025
Assignment-1
SEM- 4th
Assignment-1
Design & Analysis of Algorithms
Semester 4
Problem 1 — Fundamentals & Asymptotic
A. Using the definitions of Big-O, Big-Ω, and Big-Θ, prove or disprove: n log n = o(n^1+ε)
for any ε > 0.
B. Give tight asymptotic bounds (Θ) for the recurrence T(n) = 3T(n/3) + n / log n. Use
master theorem or expansion and justify which case applies.
Problem 2 — Divide & Conquer & Median Selection
a) Explain the recurrence and solve the time complexity for merge sort. Briefly justify
why it is optimal among comparison sorts (lower bound).
b) Design an O(n) worst-case algorithm to find the median (the n/2-th smallest element)
of an unsorted array (i.e., median-of-medians algorithm). Provide pseudocode, prove
correctness, and derive the worst-case running time.
Problem 3 — Greedy Algorithms
a) Give a greedy algorithm to find a minimum number of platforms required at a railway
station so that no train waits (given arrival and departure times). Provide complexity
analysis.
b) Consider the coin change problem with coin denominations {1, 3, 4}. Does the greedy
algorithm that always picks the largest possible coin produce an optimal solution for
any amount? If yes, prove; if no, give a counterexample and propose a correct method
(dynamic programming) and its complexity.
Problem 4 — Dynamic Programming
a) Give a DP solution (state definition, recurrence, pseudocode) for the 0/1 knapsack
problem and analyze its time/space complexity.
b) Design and analyze a DP algorithm to compute the length of the Longest Increasing
Subsequence (LIS). Then give a more efficient O(n log n) method outline (no need for
full proof).
c) Sequence alignment: Given two strings, give the DP recurrence for global alignment
with gap penalty d and substitution scoring matrix s(a,b). Describe how to recover the
alignment and discuss complexity.
Problem 5 — Graph Algorithms
a) Present Dijkstra’s algorithm and prove its correctness for non-negative edge weights. State
its time complexity using (i) adjacency matrix and (ii) adjacency list with Fibonacci heap.
b) Show how Bellman-Ford detects negative cycles reachable from the source. Give
complexity.
c) Provide Kruskal’s algorithm for MST, explain why it produces an MST (use cut property),
and analyze complexity with union-find (path compression + union by rank).
d) Given a directed graph with capacities, state the Max-Flow Min-Cut theorem and outline
the Edmonds–Karp algorithm. Provide its worst-case time complexity.
Problem 6 — NP-Completeness
a) Define the classes P, NP, NP-complete. Explain what it means for a problem to be NP-hard.
b) Prove that the decision version of Subset Sum is in NP. Then give a polynomial-time
reduction from Subset Sum to Partition to show Partition is NP-Complete (sketch).
c) Choose ONE of the following and show a polynomial-time reduction (briefly) from a known
NP-complete problem:
3-SAT → CLIQUE, or
3-SAT → VERTEX-COVER.
Session- 2024-2025
Mid Terms Question Paper
SEM- 4th
Session- 2024-2025
University Question Paper
SEM- 4th
Session- 2024-2025
Final Result
SEM- 4th