2016-17 Solved Paper · Detailed Marks-Wise Solutions
Answer: (a) partition and exchange sort. Quick sort divides the array into partitions based on a pivot and systematically exchanges elements to sort them.
Answer: (b) Dynamic Programming. The Floyd-Warshall algorithm uses dynamic programming by iteratively finding shortest paths using intermediate vertices.
Answer: An Adjacency Matrix records direct 1-step edge connections between vertices. A Path Matrix (Transitive Closure) records if any path (of any length) exists between vertices.
Answer: (a) maximum (for a Max-Heap). In a max-heap, the parent node is strictly greater than or equal to its children.
Answer: (c) Depth-First Search (DFS). Backtracking inherently explores deep into state spaces and backtracks when a constraint fails, mimicking DFS.
Answer: (c) NP-Hard. The exact TSP optimization problem is NP-Hard as no polynomial-time algorithm exists, though its decision version is NP-Complete.
Answer: (a) \(O(1)\). This happens when the exact middle element of the array happens to be the target element on the first check.
Answer: (c) \(O(V^3)\). It uses three nested loops over the \(V\) vertices to evaluate all intermediate paths.
Answer: (b) \(T(n) = 2T(n/2) + n \log n\). It falls into the gap between Case 2 and Case 3, requiring the advanced generalized version of Master's Theorem.
Answer: (a) Greedy method. By continuously picking items with the highest value/weight ratio, it trivially achieves an optimal solution in \(O(n \log n)\).
1. Best Case Time Complexity: \(O(n \log n)\)
The best case occurs when the partition element perfectly splits the array into two exactly equal halves of size \(n/2\) at every step.
2. Worst Case Time Complexity: \(O(n^2)\)
The worst case happens when the partition process repeatedly picks the smallest or largest element as the pivot, yielding highly skewed partitions of size \(0\) and \(n-1\) (e.g., when the array is already sorted).
Master's Theorem: Provides a fast method to solve recurrences of the form \(T(n) = aT(n/b) + f(n)\), where \(a \ge 1, b > 1\). It compares \(f(n)\) to the critical polynomial \(n^{\log_b a}\).
Solving \(T(n) = 8T(n/2) + n^2\):
We are allowed to take fractions of items. \(W = 20\).
Item 1 (V=25, w=18, ratio=1.38), Item 2 (V=24, w=15, ratio=1.60), Item 3 (V=15, w=10, ratio=1.50).
Feasible Solution 1 (Greedy by Value):
Take Item 1 entirely (Weight=18, Value=25). Remaining capacity = 2.
Take fraction of Item 2 (Weight=2, Value = \(24 \times (2/15) = 3.2\)).
Total Profit = 28.2
Feasible Solution 2 (Greedy by Minimum Weight):
Take Item 3 entirely (Weight=10, Value=15). Remaining capacity = 10.
Take fraction of Item 2 (Weight=10, Value = \(24 \times (10/15) = 16\)).
Total Profit = 31.0
Optimal Solution (Greedy by Max Ratio):
Sort by ratio: Item 2 (1.6) > Item 3 (1.5) > Item 1 (1.38).
Take Item 2 entirely (Weight=15, Value=24). Remaining capacity = 5.
Take fraction of Item 3 (Weight=5, Value = \(15 \times (5/10) = 7.5\)).
Remaining capacity = 0.
The characteristic equation for the linear recurrence \(a_n - 6a_{n-1} + 11a_{n-2} - 6a_{n-3} = 0\) is:
\[r^3 - 6r^2 + 11r - 6 = 0\]
By factoring, we find the roots:
\(r^3 - r^2 - 5r^2 + 5r + 6r - 6 = 0 \implies r^2(r-1) - 5r(r-1) + 6(r-1) = 0\)
\((r-1)(r^2 - 5r + 6) = 0 \implies (r-1)(r-2)(r-3) = 0\)
The roots are distinct: \(r_1 = 1, r_2 = 2, r_3 = 3\).
The general closed-form solution is a linear combination of these roots raised to the power of \(n\):
\[a_n = C_1(1)^n + C_2(2)^n + C_3(3)^n\]
Assuming standard initial conditions (e.g., \(a_0=1, a_1=2, a_2=6\)), one would solve the 3x3 system of equations to determine \(C_1, C_2, C_3\). Since initial conditions were absent in the question, the final abstract closed form is:
GreedyJobSequencing(Jobs[], n):
// 1. Sort jobs strictly by profit in descending order
Sort Jobs in descending order of profit P
// 2. Find max deadline to configure time slots
max_d = 0
For i = 1 to n:
if Jobs[i].deadline > max_d: max_d = Jobs[i].deadline
// 3. Initialize scheduling slots (1-indexed)
Array slot[1...max_d] = FALSE
// 4. Place jobs greedily
For i = 1 to n:
// Start from job's deadline and check backwards
For j = Jobs[i].deadline down to 1:
If slot[j] == FALSE:
slot[j] = Jobs[i]
break // Job scheduledTime Complexity: Sorting takes \(O(n \log n)\). The scheduling loop checks up to \(d\) slots for \(n\) jobs. Worst case time complexity is \(O(n^2)\).
The dimension array is \(P = [10, 20, 50, 1, 100]\). We trace DP table \(m[i,j] = \min (m[i,k] + m[k+1,j] + P[i-1] \cdot P[k] \cdot P[j])\).
The Greedy method makes irrevocable local optimal choices (sorting by value/weight ratio). In 0-1 Knapsack, we cannot take fractions of items. If we pick an item with the highest ratio, it might consume so much capacity that we cannot fit other combinations of items that collectively yield a higher overall value, leaving empty unusable space.
Example: Capacity \(W = 50\).
Item 1: \(v=60, w=10\) (Ratio = 6)
Item 2: \(v=100, w=20\) (Ratio = 5)
Item 3: \(v=120, w=30\) (Ratio = 4)
Greedy selection: Takes Item 1, then Item 2. Total Weight = 30. Remaining = 20. Cannot fit Item 3. Total Value = 160.
Optimal selection: Take Item 2 and Item 3. Total Weight = 50. Total Value = 220.
Greedy fails to find the maximum possible value.
A Non-deterministic algorithm possesses the theoretical ability to magically "guess" the correct option among multiple choices in \(O(1)\) time. It operates conceptually in two phases:
General Problem: Given a set of \(n\) items, each with a weight \(w_i\) and value \(v_i\), determine the combination of items to include in a knapsack of capacity \(M\) such that total weight \(\le M\) and total value is maximized.
FractionalKnapsack(Items, M):
// 1. Calculate ratios and sort
For each item: ratio = value / weight
Sort items descending by ratio
total_value = 0
// 2. Greedily fill capacity
For i = 1 to n:
if Items[i].weight <= M:
total_value += Items[i].value
M -= Items[i].weight
else:
// Take fraction of remaining capacity
fraction = M / Items[i].weight
total_value += fraction * Items[i].value
M = 0
break
Return total_valueComplexity Analysis: Calculating ratios takes \(O(n)\). Sorting the items by ratio takes \(O(n \log n)\). The loop runs in \(O(n)\) time. Total time complexity is strictly bounded by the sort: \(O(n \log n)\).
Kruskal-MST(G, w):
A = { } // Empty set for MST edges
// Create disjoint set for each vertex
For each v in G.V: Make-Set(v)
// Sort all edges in non-decreasing order of weight
Sort G.E by weight w
// Check edges
For each edge (u, v) in G.E:
if Find-Set(u) != Find-Set(v): // No cycle formed
Add (u, v) to A
Union(u, v) // Merge sets
Return ATime Complexity: Sorting edges takes \(O(E \log E)\). Disjoint-set operations take \(O(E \alpha(V))\), which is nearly constant. The total complexity is \(O(E \log E)\) or \(O(E \log V)\).
DFS(Graph G):
// Initialize all vertices to unvisited (White)
For each vertex u in G.V:
color[u] = WHITE
parent[u] = NIL
// Traverse all components
For each vertex u in G.V:
If color[u] == WHITE:
DFS-Visit(G, u)
DFS-Visit(G, u):
color[u] = GRAY // Mark as discovered
// Explore neighbors
For each neighbor v of u:
If color[v] == WHITE:
parent[v] = u
DFS-Visit(G, v) // Recursive deeper dive
color[u] = BLACK // Fully exploredThe m-Coloring Problem is an optimization and decision problem where the objective is to assign up to \(m\) different colors to the vertices of a graph \(G\) such that no two adjacent vertices (vertices connected by a direct edge) share the same color. The smallest number of colors needed to color a graph is called its Chromatic Number \(\chi(G)\). The decision version ("can it be colored with exactly \(m\) colors?") is NP-Complete.
GraphColoring(vertex v, graph G, colors[], m=3):
// Base Case: all vertices colored
If v == G.num_vertices:
Print colors[]
Return True
// Try all m colors for current vertex v
For c = 1 to m:
If IsSafe(v, G, colors, c):
colors[v] = c // Assign color c
// Recur for next vertex
If GraphColoring(v + 1, G, colors, m) == True:
Return True
// Backtrack if assignment fails downstream
colors[v] = 0 // Remove color
Return False // No color possible, trigger backtracking
IsSafe(v, G, colors, c):
For i = 0 to G.num_vertices - 1:
// If adjacent and has same color
If G.adjMatrix[v][i] == 1 and colors[i] == c:
Return False
Return TrueClass P contains all decision problems that can be fundamentally solved in polynomial time by a deterministic Turing machine. Class NP contains all decision problems where a proposed solution (certificate) can be verified as correct in polynomial time by a deterministic Turing machine.
Polynomial Reducibility (\(A \le_p B\)) means there exists an algorithm operating in polynomial time that maps every input instance of problem \(A\) into an equivalent instance of problem \(B\). Thus, solving \(B\) guarantees solving \(A\) with polynomial overhead.
\(P\) is a subset of \(NP\) (\(P \subseteq NP\)). NP-Complete is exactly the intersection of \(NP\) and \(NP-Hard\). If any \(NP-Complete\) problem is ever proven to be in \(P\), it would immediately prove that \(P = NP = NP-Complete\).
The Clique Decision Problem asks: "Given a graph \(G=(V, E)\) and an integer \(k\), does \(G\) contain a clique (a fully connected complete subgraph) of size at least \(k\)?" This problem is proven to be NP-Complete.
The Max-Flow Min-Cut Theorem is a fundamental theorem in flow networks which states that the maximum possible amount of flow passing from the source node to the sink node is absolutely equal to the total capacity of the minimum cut separating the source and sink.
A Cut (S, T) partitions the vertices into two disjoint sets where the source \(S \in S\) and sink \(t \in T\). The capacity of the cut is the sum of capacities of edges pointing from set \(S\) to set \(T\). The theorem elegantly proves that the bottleneck of the network strictly limits the maximum flow.