2022-23 Solved Paper · Detailed Marks-Wise Solutions
Answer: False. An approximation algorithm guarantees a solution within a mathematically bounded ratio (the approximation ratio) of the optimal solution, but it does not strictly guarantee finding the absolute optimal (best) solution itself.
Answer: False. The logarithmic complexity \(O(\log n)\) grows strictly slower than linear complexity \(O(n)\), meaning \(O(\log n) < O(n)\) for all sufficiently large \(n\).
Answer: \(O(n \log n)\). This applies to the Fractional Knapsack problem. Sorting the \(n\) items by their profit-to-weight ratio takes \(O(n \log n)\) time, followed by a linear \(O(n)\) scan to pack the knapsack.
Answer: False. An adjacency matrix shows only direct single-edge connections between adjacent vertices, whereas a path matrix (or transitive closure matrix) indicates whether a path of any length exists between two vertices.
Answer: True. An ordered search (like Binary Search on a sorted array) runs in \(O(\log n)\) time, which is logarithmic. Since \(O(\log n)\) is strictly bounded by polynomials like \(O(n)\), it is considered a polynomial-time algorithm.
Answer: True. Because brute force exhaustively evaluates every single candidate solution in the search space without skipping any, it is absolutely guaranteed to find the true optimal (best) solution, despite being highly inefficient.
Answer: True. The exact TSP is an NP-hard optimization problem, meaning no polynomial-time algorithm (\(O(n^k)\)) is currently known to solve it.
Answer: A* Search Algorithm. Other valid answers include Hill Climbing, Simulated Annealing, or Best-First Search, which all use heuristic functions to guess the closest path to the goal.
Answer: \(O(1)\). This occurs when the middle element of the array exactly matches the target value on the very first comparison, requiring no further recursive splits.
Answer: \(O(V^3)\) (where \(V\) is the number of vertices in the graph) due to its three nested loops evaluating paths via intermediate vertices.
Answer: Depth-First Search (DFS). It explores paths deeply into the state space tree using recursive stack frames before backtracking upon hitting constraints.
Answer: A spanning tree is a connected, acyclic subgraph derived from a connected, undirected graph \(G = (V, E)\) that includes absolutely all vertices \(V\) of the graph, utilizing exactly \(|V| - 1\) edges.
Algorithm Explanation: The objective is to maximize profit by scheduling jobs such that they complete before their respective deadlines. Each job takes 1 unit of time. The greedy strategy works by prioritizing jobs with the highest profit and scheduling them in the latest possible free time slot to keep earlier slots open for other jobs.
JobSequencing(Jobs Array J, Integer n):
// 1. Sort all jobs descending by profit
Sort J in descending order of profit
// 2. Find max deadline to size our timeline
Max_D = 0
For i = 1 to n:
Max_D = max(Max_D, J[i].deadline)
// 3. Initialize slots tracking
Array slot[1..Max_D] initialized to Free
// 4. Greedily assign jobs to slots
For i = 1 to n:
// Search for the latest free slot from deadline down to 1
For j = min(Max_D, J[i].deadline) down to 1:
If slot[j] is Free:
slot[j] = J[i] // Lock in job
Break // Job scheduled, move to next job
Return slotTime Complexity Analysis:
• Sorting the \(n\) jobs requires \(O(n \log n)\) time.
• The nested loops for scheduling process each of the \(n\) jobs. In the worst-case scenario, the inner loop searches backwards through \(O(n)\) slots, resulting in \(O(n^2)\) time.
• Total Worst-Case Time Complexity: \(O(n^2)\).
Based on the provided network graph with nodes 1 (Source) and 6 (Sink), and the corresponding edge capacities: \(1\to4 (27)\), \(1\to2 (24)\), \(2\to4 (6)\), \(2\to3 (10)\), \(2\to6 (8)\), \(4\to5 (18)\), \(4\to3 (15)\), \(5\to6 (18)\), \(3\to6 (8)\).
We systematically trace augmenting paths from source 1 to sink 6 using the Ford-Fulkerson method and update residual capacities.
Verification: Look at the sink node 6. All edges directly entering the sink (\(5 \to 6\), \(2 \to 6\), and \(3 \to 6\)) now have a residual forward capacity of exactly 0. The cut around the sink is fully saturated. Thus, no further augmenting paths can possibly exist.
Prim's Algorithm maintains a single growing spanning tree. In each step, it greedily selects the minimum weight edge that connects an unvisited vertex to the existing tree.
Prim-MST(Graph G, weights w, root r):
1. For each vertex u in G.V:
u.key = Infinity // Distance to tree
u.parent = NIL // MST parent tracking
2. r.key = 0 // Start at root
3. Initialize Min-Priority Queue Q containing all vertices V
4. While Q is not empty:
u = Extract-Min(Q) // Greedily pick closest vertex
For each neighbor v in G.adj[u]:
// If v is unvisited and edge (u,v) is lighter than current key
If v is in Q and w(u, v) < v.key:
v.parent = u
v.key = w(u, v)
Decrease-Key(Q, v, w(u, v)) // Update priority queueComplexity Analysis:
• Initializing the priority queue takes \(O(V)\).
• The Extract-Min operation runs \(V\) times. If a Binary Min-Heap is used, it takes \(O(V \log V)\) total.
• The inner loop checks \(E\) edges total. Decrease-Key runs at most \(E\) times, taking \(O(E \log V)\) total.
• Total Time Complexity: \(O(E \log V)\) with a Binary Heap. Using an advanced Fibonacci Heap reduces this to \(O(E + V \log V)\).
(a) Cook's Theorem (Cook-Levin Theorem): [ 2.5 Marks ]
Cook's theorem definitively states that the Boolean Satisfiability Problem (SAT) is NP-Complete.
It was historically the very first problem mathematically proven to belong to the NP-Complete class. The theorem demonstrated that any problem inside the NP complexity class could be converted (reduced in polynomial time) into a boolean satisfiability formula, laying the entire foundation for proving other problems are NP-Complete via reductions.
(b) Clique Definition & Example: [ 2.5 Marks ]
A Clique in an undirected graph \(G=(V, E)\) is a subset of vertices \(V' \subseteq V\) wherein every distinct pair of vertices is connected by a direct edge. In graph theory terms, the subgraph induced by \(V'\) is a perfectly complete graph.
Example: Imagine a social network graph where vertices are people and edges represent mutual friendships. If Alice, Bob, and Charlie are all mutual friends with one another, the subset {Alice, Bob, Charlie} forms a clique of size 3 (a triangle). Finding the largest such clique in a graph is known as the Maximum Clique Problem, which is NP-Hard.
(i) Brute Force Algorithm:
A brute force algorithm is a straightforward, exhaustive search strategy that systematically enumerates and evaluates every single possible candidate solution in the search space to find the optimal one.
Pros: It is absolutely guaranteed to find the true correct optimal solution if it exists.
Cons: It is notoriously inefficient and usually impractical for large inputs, often resulting in exponential \(O(2^n)\) or factorial \(O(n!)\) time complexities (e.g., trying all paths in the Travelling Salesman Problem).
(ii) Approximation Algorithm:
An approximation algorithm is a fast (polynomial-time) algorithm explicitly designed to find a "good enough", near-optimal solution for complex NP-Hard optimization problems where finding the exact optimal solution would take centuries.
Key Feature: It comes with a strict mathematical proof guaranteeing that the computed solution's quality is within a specific bounded ratio (the approximation ratio) of the true optimal solution (e.g., a 2-approximation algorithm for Vertex Cover guarantees the solution is at worst exactly twice the size of the optimal minimum cover).
Edges present in the given graph: \((1,6)[10]\), \((1,2)[28]\), \((6,5)[25]\), \((2,7)[14]\), \((2,3)[16]\), \((7,5)[24]\), \((7,4)[18]\), \((5,4)[22]\), \((3,4)[12]\).
Prim's algorithm tracing, strictly building a connected tree starting from node 1:
All vertices are visited. Algorithm terminates.
The goal is to place \(N\) queens on an \(N \times N\) chessboard so that no two queens attack each other (no shared row, column, or diagonal).
SolveNQueens(row, N, board[]):
// Base Case: All N queens are successfully placed
If row == N:
Print board state (Solution found)
Return
// Try placing a queen in each column of the current row
For col = 0 to N-1:
If IsSafe(row, col, board, N):
board[row] = col // Place Queen at (row, col)
// Recur to place the rest of the queens
SolveNQueens(row + 1, N, board)
// Backtrack: Remove queen (implicitly done by overwriting in next iteration,
// or explicitly setting board[row] = -1)The worst-case time complexity is \(O(N!)\) (Factorial time), as there are \(N\) choices for the first row, at most \(N-2\) valid choices for the second row, and so on, bounding the search space depth.
Floyd-Warshall(WeightMatrix W, Integer V):
Initialize DistanceMatrix D^(0) = W
// k is the intermediate vertex being considered
For k = 1 to V:
For i = 1 to V:
For j = 1 to V:
// Update shortest path if path via k is better
D^(k)[i][j] = min( D^(k-1)[i][j], D^(k-1)[i][k] + D^(k-1)[k][j] )
Return D^(V)QuickSort(Array A, Integer low, Integer high):
If low < high:
// Partition the array and get the pivot index
p = Partition(A, low, high)
// Recursively sort elements before and after pivot
QuickSort(A, low, p - 1)
QuickSort(A, p + 1, high)
Partition(Array A, Integer low, Integer high):
pivot = A[high] // Pick last element as pivot
i = low - 1 // Index of smaller element
For j = low to high - 1:
If A[j] <= pivot:
i = i + 1
Swap A[i] with A[j]
// Place pivot in correct sorted position
Swap A[i+1] with A[high]
Return i + 1The dimensions array is \(P = [30, 35, 15, 5, 10]\). The DP recurrence calculates the minimum cost: \(m[i, j] = \min \{m[i, k] + m[k+1, j] + P[i-1] \cdot P[k] \cdot P[j]\}\).
DP Tracing:
Kruskal-MST(Graph G, weights w):
1. Initialize empty set A = { }
2. // Create disjoint sets for each vertex
For each vertex v in G.V:
Make-Set(v)
3. Sort the edges of G.E in non-decreasing order of weight w
4. // Greedily add edges without forming cycles
For each edge (u, v) in the sorted G.E:
// Check if u and v are in different disjoint sets
If Find-Set(u) != Find-Set(v):
Add edge (u, v) to set A
Union(u, v) // Merge the two sets
5. Return ASorting the edges dominates the complexity, taking \(O(E \log E)\) time. The disjoint-set operations (Find and Union) using union-by-rank and path compression take \(O(E \cdot \alpha(V))\) time, where \(\alpha\) is the inverse Ackermann function (effectively constant). Thus, the total time complexity is \(O(E \log E)\), which is equivalent to \(O(E \log V)\).
Backtracking applies Depth-First Search (DFS) to find all feasible solutions to decision or constraint satisfaction problems, maintaining low memory overhead \(O(V)\). Branch and Bound applies Breadth-First or Best-First Search (BFS) to solve optimization problems by calculating bounds to aggressively prune non-optimal branches, but requires exponentially more memory to store the active search frontier queues.
Based on the provided directed graph edges: \(A \to B, A \to C, B \to E, C \to D, D \to H, H \to G, G \to E, E \to F, F \to A, F \to G\).
We trace all vertices reachable from node A using a Depth-First Search (DFS) reachability sequence:
Through these paths, node A can successfully reach every single vertex in the graph.
Recursion is a functional approach where a problem is solved by a function repeatedly calling itself on smaller instances of the input. It utilizes the system call stack memory, making the code elegant and mathematically expressive, but susceptible to stack overflow and overhead delays. Iteration is an imperative approach that uses loop constructs (for, while) to repeat execution blocks. It uses a fixed, constant \(O(1)\) memory footprint and is generally faster due to avoiding call stack overhead.
(i) \(T(n) = 2T(n/4) + n^{0.51}\) [ 4 Marks ]
Comparing to \(T(n) = aT(n/b) + f(n)\): \(a=2, b=4\).
Calculate critical exponent: \(n^{\log_b a} = n^{\log_4 2} = n^{0.5}\).
Compare \(f(n) = n^{0.51}\) with \(n^{0.5}\). Since \(0.51 > 0.5\), \(f(n)\) grows polynomially faster: \(f(n) = \Omega(n^{0.5 + \epsilon})\) with \(\epsilon = 0.01\).
Check the Regularity Condition for Case 3: \(a f(n/b) \le c f(n)\) for \(c < 1\).
\(2 (n/4)^{0.51} = 2 \times 4^{-0.51} \times n^{0.51} \approx 2 \times 0.493 \times n^{0.51} = 0.986 n^{0.51}\).
Since \(0.986 \le c < 1\), the condition is satisfied. This falls strictly into Case 3.
Complexity: \(T(n) = \Theta(f(n)) = \Theta(n^{0.51})\).
(ii) \(T(n) = \sqrt{2} T(n/2) + \log n\) [ 4 Marks ]
Here, \(a=\sqrt{2}, b=2\).
Calculate critical exponent: \(n^{\log_b a} = n^{\log_2 \sqrt{2}} = n^{0.5} = \sqrt{n}\).
Compare \(f(n) = \log n\) with \(n^{0.5}\). The logarithmic function grows strictly polynomially slower than the square root function. Formally, \(f(n) = O(n^{0.5 - \epsilon})\) holds true (for instance, choosing \(\epsilon = 0.1\), \(\log n = O(n^{0.4})\)).
This matches Case 1 of the Master's Theorem.
Complexity: \(T(n) = \Theta(n^{\log_b a}) = \Theta(n^{0.5}) = \Theta(\sqrt{n})\).
Little Omega (\(\omega\)) Notation provides an asymptotic, strictly loose lower bound for an algorithm's running time. While Big-\(\Omega\) allows the bounds to be asymptotically tight (grow at the exact same rate), little-\(\omega\) strictly requires the algorithm's time complexity to grow infinitely faster than the bounding function as \(n \to \infty\).
Formally, \(f(n) = \omega(g(n))\) if for any arbitrarily large positive constant \(c > 0\), there exists a threshold \(n_0\) such that \(f(n) > c \cdot g(n) \ge 0\) for all \(n \ge n_0\). This guarantees that:
\[\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty\]
Example: Prove that \(f(n) = n^2 = \omega(n)\).
Evaluating the limit: \(\lim_{n \to \infty} \frac{n^2}{n} = \lim_{n \to \infty} n = \infty\).
Since the limit evaluates to infinity, it proves that \(n^2\) grows strictly faster than \(n\), validating \(n^2 = \omega(n)\).