2023-24 Solved Paper · Detailed Marks-Wise Solutions
Answer: Min-Priority Queue. For optimal performance, it is typically implemented using a Binary Heap (gives \(O(E \log V)\) complexity) or a Fibonacci Heap (gives \(O(E + V \log V)\) complexity). It is used to quickly extract the vertex with the minimum key value among the unvisited vertices.
Answer: Constant Time Complexity. It indicates that the execution time (or space) of the algorithm remains constant, bounded by a fixed upper limit, and does not grow or change regardless of the size of the input data \(n\).
Answer: \(O(n \log n)\). This perfectly matches Case 2 of Master's Theorem where \(a=2, b=2\). Since \(n^{\log_2 2} = n^1 = n\), and \(f(n) = n\), we have \(f(n) = \Theta(n^{\log_b a})\). This results in \(T(n) = \Theta(n \log n)\).
Answer: asymptotic lower bound. It guarantees that the algorithm will take at least this much time to execute for sufficiently large inputs.
Answer: Greedy method. By sorting the items by their profit-to-weight ratio in descending order and continuously picking the item with the highest ratio, an optimal solution is guaranteed.
Answer: Stack. This can be implemented either implicitly using the system call stack via recursion, or explicitly using a LIFO (Last-In-First-Out) Stack data structure to track visited nodes.
Answer: Ford-Fulkerson Algorithm. Specifically, its polynomial-time implementation, the Edmonds-Karp Algorithm, which uses Breadth-First Search (BFS) to find the shortest augmenting paths, is commonly used.
Answer: 92 total distinct solutions. Note that if we exclude solutions that are identical under rotational and reflective symmetry, there are 12 unique fundamental solutions.
Answer: \(O(n \log n)\) in all cases (best, worst, and average cases). Building the max heap takes \(O(n)\), and extracting elements takes \(O(n \log n)\).
Answer: False. Greedy algorithms do not guarantee an optimal solution for 0-1 Knapsack because items cannot be divided to fill remaining capacity. Dynamic Programming or Branch and Bound must be used.
Answer: Bellman-Ford Algorithm. It iteratively relaxes all edges \(|V|-1\) times, allowing it to accurately compute shortest paths with negative weights and detect negative weight cycles.
Answer: 60.
Detailed Calculation:
1. Calculate value/weight ratios:
Both Dijkstra's Algorithm and Bellman-Ford Algorithm solve the Single Source Shortest Path (SSSP) problem, but they utilize entirely different design paradigms and have different constraints regarding edge weights.
| Feature | Dijkstra's Algorithm | Bellman-Ford Algorithm |
|---|---|---|
| Design Paradigm | Greedy Approach (selects the nearest unvisited vertex). | Dynamic Programming Approach (relaxes all edges iteratively). |
| Negative Edge Weights | Cannot handle negative edge weights. Will produce incorrect results. | Fully capable of handling graphs with negative edge weights. |
| Negative Cycle Detection | Fails completely; cannot detect negative cycles and may infinite loop. | Can successfully detect the presence of negative weight cycles. |
| Edge Relaxation Approach | Relaxes edges emanating from a single selected vertex at a time. | Relaxes all edges in the graph in every single iteration. |
| Time Complexity (Worst Case) | \(O(E \log V)\) (using a Binary Min-Heap data structure). | \(O(V \cdot E)\) (significantly slower than Dijkstra on dense graphs). |
Quick Sort's performance is highly dependent on the partition step (how the pivot splits the array).
1. Best Case Time Complexity: \(O(n \log n)\)
The best case occurs when the pivot chosen perfectly splits the array into two equal halves of size \(n/2\) at each level of recursion. The recurrence relation is:
\[T(n) = 2T(n/2) + \Theta(n)\]
Applying Case 2 of Master's Theorem (\(a=2, b=2, f(n)=\Theta(n) \implies n^{\log_2 2} = n\)):
2. Worst Case Time Complexity: \(O(n^2)\)
The worst case occurs when the partition process always picks the greatest or smallest element as the pivot (e.g., array is already sorted, and we pick the last element). This creates highly skewed partitions of size \(0\) and \(n-1\). The recurrence relation is:
\[T(n) = T(n-1) + T(0) + \Theta(n) = T(n-1) + \Theta(n)\]
Expanding the recurrence via substitution:
Floyd-Warshall Algorithm: A classical dynamic programming approach used to find the shortest path between all pairs of vertices in a weighted graph (which may contain negative weights but no negative cycles). It systematically updates shortest paths by considering intermediate vertices \(\{1..k\}\).
Floyd-Warshall(W, V):
// W is the initial adjacency/weight matrix of V vertices.
1. Let D^(0) = W (Initialize shortest distances)
// Core DP triple nested loops
2. For k = 1 to V: // Consider vertex k as an intermediate point
For i = 1 to V: // Source vertex
For j = 1 to V: // Destination vertex
// If path via k is shorter, update it:
D^(k)[i][j] = min( D^(k-1)[i][j], D^(k-1)[i][k] + D^(k-1)[k][j] )
3. Return D^(V) // Contains shortest paths for all pairsTime Complexity Analysis:
The algorithm consists of three nested loops, each iterating exactly \(V\) times (from 1 to \(V\)). Inside the innermost loop, the algorithm performs a constant-time \(O(1)\) addition and comparison operation. Thus, the total number of operations is proportional to \(V \times V \times V\).
Time Complexity = \(\Theta(V^3)\).
Space Complexity = \(\Theta(V^2)\) to store the distance matrix.
Given Knapsack Capacity \(M = 10\) kg. We will use the Greedy Method for the Fractional Knapsack Problem. First, we compute the profit-to-weight ratio for each item.
Step 1: Sort items in descending order of ratio:
Item 5 (8.0) \(\to\) Item 2 (5.0) \(\to\) Item 3 (5.0) \(\to\) Item 1 (3.33) \(\to\) Item 4 (2.40).
Step 2: Greedy Selection (Capacity = 10 kg):
A Randomized Algorithm is an algorithm that incorporates a degree of randomness as part of its logic. It uses pseudo-random numbers to make decisions during execution, meaning its behavior and output (or execution time) can vary even for the exact same input on different runs. The main goal is to achieve better average-case performance or simpler implementation compared to deterministic algorithms.
Randomized algorithms are broadly classified into two major categories:
Given 4 matrices with dimensions: \(A(10 \times 20)\), \(B(20 \times 50)\), \(C(50 \times 1)\), and \(D(1 \times 100)\). The dimension array is \(P = [10, 20, 50, 1, 100]\). The DP recurrence is:
\[m[i, j] = \min_{i \le k < j} \{m[i, k] + m[k+1, j] + P[i-1] \cdot P[k] \cdot P[j]\}\]
Step-by-Step DP Calculation Table:
The Bellman-Ford Algorithm computes shortest paths from a single source vertex to all other vertices. It is robust enough to handle negative edge weights.
Bellman-Ford(Graph G, Source S):
// 1. Initialization
Initialize distance array dist[] of size |V| to Infinity
dist[S] = 0
// 2. Relax all edges |V| - 1 times
For i = 1 to |V| - 1:
For each edge (u, v) in G with weight w:
If dist[u] != Infinity and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
parent[v] = u
// 3. Detect negative weight cycles
For each edge (u, v) in G with weight w:
If dist[u] != Infinity and dist[u] + w < dist[v]:
Return Error "Negative weight cycle detected!"
Return dist[], parent[]Advantages:
• Guaranteed Optimality: Unlike Greedy approaches, DP evaluates all possible subproblem states and combinations, guaranteeing a globally optimal solution.
• Avoids Redundancy: By storing solutions to overlapping subproblems in a table (memoization/tabulation), it drastically cuts down exponential time complexities to polynomial time.
Drawbacks:
• High Memory/Space Overhead: DP algorithms heavily rely on large multi-dimensional matrices or arrays to store intermediate states, demanding substantial RAM memory \(O(n^2)\) or worse.
• Strict Constraints: It can only be applied to problems exhibiting Optimal Substructure and Overlapping Subproblems. Designing the transition relations can also be highly abstract and complex.
According to Donald Knuth, a sequence of instructions must satisfy five essential characteristics to be considered a legitimate algorithm:
Asymptotic notations are mathematical tools used to describe the limiting behavior (time/space complexity) of a function when the input size approaches infinity.
Formulating the Recurrence Relation:
In the Towers of Hanoi puzzle, moving \(n\) disks from the Source peg to the Destination peg using an Auxiliary peg requires:
1. Moving \(n-1\) disks from Source to Auxiliary (Cost = \(T(n-1)\)).
2. Moving the largest \(n^{\text{th}}\) disk from Source to Destination (Cost = \(1\) operation).
3. Moving the \(n-1\) disks from Auxiliary to Destination (Cost = \(T(n-1)\)).
Solving the Recurrence via Back-Substitution:
The goal is to schedule jobs within their deadlines to maximize total profit on a single processor. Each job takes 1 unit of time.
JobSequencing(Jobs array J, Integer n):
// 1. Sort jobs by profit in descending order
Sort J in descending order based on profit p_i
// 2. Find maximum deadline to create timeslots
Max_D = 0
For i = 1 to n:
Max_D = max(Max_D, J[i].deadline)
// 3. Initialize slots array
Array slots[1...Max_D] initialized to NULL
// 4. Greedily schedule jobs
For i = 1 to n:
// Try placing job in the latest possible slot before deadline
For j = min(Max_D, J[i].deadline) down to 1:
If slots[j] is NULL:
slots[j] = J[i] // Assign job
Break // Move to next job
Return slots arrayJobs Data: \(J_1(p=100, d=2)\), \(J_2(p=10, d=1)\), \(J_3(p=5, d=2)\), \(J_4(p=27, d=1)\).
A Spanning Tree of a connected, undirected graph \(G=(V, E)\) is a subgraph that is a tree (connected and acyclic) and includes absolutely all the vertices \(V\) of the original graph, utilizing exactly \(|V| - 1\) edges.
Note: Based on the provided 7-node graph. We trace Prim's algorithm maintaining a set of visited vertices and growing the tree using minimum outgoing edges.
Reducibility is a theoretical mechanism used to convert an instance of problem \(A\) into an instance of problem \(B\) using a computable function. Specifically, polynomial-time reducibility (\(A \le_p B\)) means that there exists an algorithm operating in polynomial time that can map any input of \(A\) to a valid input of \(B\). If \(A \le_p B\), it implies that solving \(B\) is at least as hard as solving \(A\), because an algorithm for \(B\) can automatically be used as a subroutine to solve \(A\).
This statement is the cornerstone of complexity theory. By definition, a problem \(L\) is NP-Complete if every single problem \(X \in NP\) can be reduced to \(L\) in polynomial time (\(X \le_p L\)).
Suppose someone discovers a polynomial-time algorithm to solve \(L\) (meaning \(L \in P\)). Then, to solve any problem \(X \in NP\), we can:
Since both steps take polynomial time, their composition is also polynomial time. Thus, the problem \(X\) is solved in polynomial time. Because this applies to every \(X \in NP\), it would conclusively prove that all NP problems are in P, resulting in the monumental proof that P = NP.
A Flow Network is a directed graph \(G=(V, E)\) where each directed edge \((u, v)\) has a non-negative capacity \(c(u, v) \ge 0\). The network contains two special distinguished vertices: a source node \(S\) (produces flow) and a sink node \(T\) (consumes flow).
Mathematical Constraints: A valid flow \(f\) must adhere to three fundamental rules:
An Augmenting Path is a simple path from the source \(S\) to the sink \(T\) within the residual graph \(G_f\), such that every edge along this path has a strictly positive residual capacity (\(c_f(u,v) > 0\)). Finding one indicates that the total flow in the network can still be increased.
The Residual Capacity \(c_f(u, v)\) represents the amount of additional flow that an edge can still accommodate. It is dynamically calculated based on current flows:
Ford-Fulkerson(Graph G, Source S, Sink T):
// 1. Initialize empty flows
For each edge (u, v) in G.E:
f(u, v) = 0
f(v, u) = 0
// 2. Iteratively augment flow as long as a path exists
While there exists an augmenting path P from S to T in residual graph G_f:
// Find bottleneck edge capacity on the path
c_f(P) = min { c_f(u, v) : (u, v) is in path P }
// Update flows along the path
For each edge (u, v) in path P:
If (u, v) is a forward edge in original graph:
f(u, v) = f(u, v) + c_f(P) // Increase flow
f(v, u) = -f(u, v) // Maintain skew symmetry
Else (it is a reverse edge):
f(v, u) = f(v, u) - c_f(P) // Cancel flow
f(u, v) = -f(v, u)
// 3. Return total flow emerging from Source S
Return SUM(f(S, v)) for all v