DAA PYQ

Q1 – 10 Marks

1. (a) Order the functions 4n², n log₂n and 3ⁿ in decreasing order of growth.

We are asked to compare three functions asymptotically and arrange them in decreasing order of growth rate (for large n):

In asymptotic analysis, constant factors and lower-order terms are ignored. Therefore, behaves like ; the constant 4 does not affect the order of growth. We compare the three broad families: logarithmic–linear , polynomial , and exponential .

A fundamental hierarchy in complexity theory is:

for any constant (c > 0) and base (a > 1). This means logarithmic functions grow slower than any polynomial, and any polynomial grows slower than any exponential function. Here, is slightly larger than linear but still sub-quadratic; is a polynomial of degree 2; and is exponential with base 3.

To see this more formally, consider the ratio of functions as .

1. Compare and :

since n grows faster than . Hence , so (and therefore 4n²) grows faster than .

1. Compare and :

because exponential growth dominates any polynomial. Therefore, grows strictly faster than .

Combining both comparisons, we get

Thus, in decreasing order of growth (largest first):

In Big-O notation, we can say:

which confirms the order obtained above.

1. (b) Discuss the procedure partition in Quick Sort; give its time complexity.

Quicksort is a divide-and-conquer sorting algorithm. Its efficiency largely depends on the partition procedure, which rearranges the elements of an array around a chosen pivot. After partitioning, all elements less than or equal to the pivot appear on its left, and all elements greater than the pivot appear on its right. The pivot is placed in its final sorted position, and the subarrays on both sides are then recursively sorted.

A common partition scheme is the Lomuto partition. Suppose the array is A[low…high].

1. Choose the last element A[high] as the pivot.
2. Maintain an index i that marks the boundary of the “≤ pivot” section. Initially, i = low − 1.
3. Scan the array with index j from low to high − 1.
   • For each element A[j], if A[j] ≤ pivot, increment i and swap A[i] and A[j].
   • This ensures that A[low…i] always contains elements ≤ pivot, and A[i+1…j] contains elements > pivot.
4. After the loop, swap A[i+1] with the pivot A[high].
5. Return i+1 as the pivot’s final index.

Another popular variant is Hoare partition, which uses two indices moving inward from both ends and swaps out-of-place elements until they cross, then places the pivot appropriately. Both schemes have the same asymptotic cost: they perform a single linear scan over the subarray.

For a subarray of size (n), the partition procedure examines each element at most once and performs a constant amount of work per element (comparisons and occasional swaps). Therefore, the time complexity of a single partition operation is:

In the full Quicksort algorithm, each recursive level performs O(n) work through partitioning, and the number of levels is O(log n) on average, giving average complexity . However, when the pivot selection is poor (e.g., always smallest or largest element for already sorted input), the recursion depth becomes n, and the total time becomes . Still, the key point for this question is that the partition step itself is linear in the size of the subarray.

1. (c) Prove that if
then

To prove this property, we recall the definition of Big-O notation. Saying means that there exist positive constants (c_1) and (n_1) such that

Similarly, means there exist positive constants and such that

Let us define . For all , both inequalities hold simultaneously. Consider the sum:

Now introduce the function . By definition of maximum, for every n:

Therefore:

Combining these inequalities, for all :

This is exactly the Big-O condition with constant (c = c_1 + c_2) and reference function . Hence, by the formal definition of Big-O,

Intuitively, this result states that the combined running time of two algorithms executed sequentially is, asymptotically, dominated by the slower-growing of the two major components. If one part is and another is , the total is still ; the quadratic term dominates and the lower-order term does not change the overall order of growth.

Q2 – 10 Marks

2. (a) Give characteristics of Dynamic Programming approach, Greedy approach and Branch and Bound techniques.

Dynamic Programming (DP):
Dynamic programming is a design technique used when a problem has overlapping subproblems and optimal substructure.

1. The main idea is to solve each distinct subproblem only once and store its solution in a table (array, matrix, map).
2. Bigger problems are built from solutions of smaller subproblems, either in a bottom-up (tabulation) manner or using top-down memoization with recursion.
3. DP guarantees an optimal solution when the problem satisfies the principle of optimality: an optimal solution of a problem contains optimal solutions of its subproblems.
4. It often converts an exponential-time recursive solution into a polynomial-time algorithm (e.g., O(n²), O(n³)).
5. Typical applications: Fibonacci numbers, shortest paths (Bellman–Ford, Floyd–Warshall), knapsack, matrix-chain multiplication, LCS, edit distance etc.
6. DP trades space for time, as it uses extra memory to store intermediate results.

Greedy Approach:
The greedy method constructs the solution in a sequence of steps.

1. At each step, it makes a locally optimal choice (greedy choice) without reconsidering previous decisions.
2. Works correctly only when the problem has greedy-choice property and optimal substructure.
3. Usually easier and more efficient than DP; many greedy algorithms run in O(n log n) or O(m log n) time with less memory.
4. Does not always give a globally optimal solution; correctness must be proved per problem.
5. Examples: Kruskal’s and Prim’s MST algorithms, Dijkstra’s algorithm (for non-negative weights), Huffman coding, activity selection.

Branch and Bound (B&B):
Branch and Bound is used mainly for combinatorial optimization and NP-hard problems.

1. The solution space is represented as a tree. Each node corresponds to a partial solution.
2. The algorithm “branches” by expanding nodes and adding more decisions.
3. For every node, a bound (usually a lower or upper bound on the best possible solution from that node) is computed.
4. If the bound shows that the node cannot lead to a better solution than the best one currently known, the node is pruned (cut off).
5. This systematic pruning can drastically reduce the search space while still guaranteeing an optimal solution.
6. Typical problems: Travelling Salesman Problem, 0/1 knapsack (exact), assignment problem, etc.
7. B&B is often exponential in worst case, but much faster in practice due to pruning.

2. (b) Give Floyd–Warshall algorithm for all-pairs shortest path and discuss its time complexity.

The Floyd–Warshall algorithm is a classical dynamic programming algorithm used to compute the shortest paths between all pairs of vertices in a weighted graph (directed or undirected). It can handle positive as well as negative edge weights, provided there is no negative-weight cycle.

Assume a graph with vertices numbered 1…n and weight matrix W, where W[i][j] is the weight of edge (i, j); if no edge exists, W[i][j] = ∞, and W[i][i] = 0.

The idea is to iteratively allow more and more intermediate vertices in paths. Let D^k[i][j] be the length of the shortest path from i to j where all intermediate vertices (if any) belong to the set {1, 2, …, k}. Initially, for k = 0, the shortest paths using no intermediate vertices are just the direct edges, so:

D^0[i][j] = W[i][j].

For k ≥ 1, we check whether the shortest path from i to j using vertices from {1…k} either

• does not use vertex k at all (length D^{k-1}[i][j]), or
• uses vertex k as the last intermediate vertex: path i → k plus k → j, with length D^{k-1}[i][k] + D^{k-1}[k][j].

Thus the recurrence is:

The algorithm implements this with three nested loops and typically overwrites a single matrix D.

Algorithm (pseudo-code):

1. Initialize D[i][j] = W[i][j] for all i, j.

For k = 1 to n
    For i = 1 to n
        For j = 1 to n
            if D[i][j] > D[i][k] + D[k][j] then
                D[i][j] = D[i][k] + D[k][j]

Optionally, another matrix P can be maintained to reconstruct actual shortest path sequences.

Time Complexity:
There are three nested loops, each running from 1 to n. Inside the innermost loop, only a constant number of operations are done (a comparison and an addition). Hence:

The space complexity is O(n²) to store the distance matrix (and possibly a predecessor matrix). Floyd–Warshall is preferred for dense graphs or when we need all-pairs shortest paths and the graph is not very large.

2. (c) Discuss the Depth First Search (DFS) technique, explain with an example.

Depth First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along a branch before backtracking. It can be applied to both directed and undirected graphs and operates on an adjacency list or adjacency matrix representation.

Basic Idea:
Starting from a selected source vertex, DFS marks it as visited and then recursively visits one unvisited neighbor, then a neighbor of that neighbor, and so on. When a vertex has no unvisited neighbors left, the algorithm backtracks to the previous vertex and continues the search with any remaining unvisited neighbors. This creates a traversal tree called the DFS tree.

Algorithm (recursive version):

DFS(G, s):
    mark s as visited
    for each vertex v adjacent to s:
        if v is not visited:
            DFS(G, v)

We call DFS for each unvisited vertex in the graph to ensure all connected components are covered.

Example:
Consider an undirected graph with vertices {A, B, C, D, E} and edges:
A–B, A–C, B–D, C–D, C–E.

Adjacency (one possible order):
A: B, C
B: A, D
C: A, D, E
D: B, C
E: C

Start DFS from A.

1. Visit A (mark visited).
2. Go to first neighbor B. Visit B.
3. From B, visit its unvisited neighbor D.
4. From D, both neighbors (B, C) are either visited or will be visited next. So go to unvisited neighbor C. Visit C.
5. From C, its neighbors A and D are visited, E is unvisited. Visit E.
6. E has only neighbor C, already visited. Backtrack; no more options.

A possible DFS traversal order: A, B, D, C, E. The corresponding DFS tree edges are (A,B), (B,D), (D,C), (C,E).

Applications:

1. Cycle detection in undirected and directed graphs.
2. Topological sorting in Directed Acyclic Graphs (DAGs).
3. Finding connected components and strongly connected components (with Kosaraju or Tarjan algorithms).
4. Solving puzzles and backtracking problems (e.g., mazes, n-Queens structure).

Complexity:
Using adjacency lists, DFS runs in O(V + E) time, where V is number of vertices and E is number of edges, because each vertex and edge is processed at most once. Space complexity is O(V) for the recursion stack and visited array.

Q3 – 10 Marks

3. (a) Define 0/1 knapsack problem. Solve the given instance using dynamic programming (W = 5).

The 0/1 Knapsack Problem is a classical optimization problem where we are given a set of items, each with a specific value and weight, and a knapsack with a maximum capacity W. The objective is to select a subset of items such that the total value is maximized without exceeding the weight limit. The name “0/1” signifies that each item can either be taken entirely (1) or not taken at all (0); fractional selection is not allowed, unlike the fractional knapsack. This problem exhibits optimal substructure and overlapping subproblems, making it ideal for a dynamic programming (DP) solution.

DP constructs a table where dp[i][w] represents the maximum value achievable using the first i items with a capacity limit of w. The recurrence is:

Given Items:

Capacity W = 5

DP Table Construction

We create a 4 × 6 table (items 0–3, capacity 0–5):

Step-by-Step Filling:

• For Item 1 (w=2, v=60):
  dp[1][2] = 60, dp[1][3] = 60, dp[1][4] = 60, dp[1][5] = 60
• For Item 2 (w=2, v=150):
  Choose max of taking or skipping:
  At capacity 2: max(60, 150) = 150
  At capacity 3–5, values become: 150, 210, 210
• For Item 3 (w=3, v=120):
  At capacity 3: max(150, 120) = 150
  At capacity 4: max(210, 120) = 210
  At capacity 5: max(210, 120 + 150) = 270

Final answer is:

Selected Items:

• Item 2 (value 150, weight 2)
• Item 3 (value 120, weight 3)

Total weight = 5, total value = 270.

Thus, the DP solution ensures an optimal selection.

3. (b) Apply Dijkstra’s algorithm on the given graph (source = Node 4). Show all steps.

Dijkstra’s algorithm computes the shortest path from a single source to all other vertices in a weighted graph with non-negative edge weights. It maintains a set of permanently labeled nodes whose shortest distance from the source is known. A priority queue or greedy selection is used to repeatedly choose the vertex with the smallest temporary distance.

Initial Setup

Source = 4

Distances initially:

Start at node 4.

Step 1: From Node 4

Edges:
4 → 2 = 1
4 → 1 = 3
4 → 5 = 7

Distances update:
d(2)=1, d(1)=3, d(5)=7.

Mark node 2 (smallest 1).

Step 2: From Node 2

Edges:
2 → 1 = 4
2 → 3 = 2
2 → 4 = 1 (ignore, visited)
2 → 5 = 3

Check updates:
d(1) = min(3, 1+4=5) → 3 (unchanged)
d(3) = 1+2 = 3
d(5) = min(7, 1+3=4) → 4

Mark node 1 or 3 (tie = 3). Choose node 1.

Step 3: From Node 1

Edges do not improve any distances.

Mark node 3 next.

Step 4: From Node 3

Edges:
3 → 2 (visited)
3 → 5 = 6
3 → 6 = 9

Update:
d(5) = min(4, 3+6 = 9) → 4
d(6) = 3+9 = 12

Mark node 5 next (distance = 4).

Step 5: From Node 5

Edges:
5 → 3
5 → 6 = 4

Update:
d(6) = min(12, 4+4 = 8) → 8

Final Distances from Node 4

Thus, node 4 reaches node 6 with shortest distance 8.

Dijkstra ensures optimality through greedy relaxation and is efficient with time complexity O(E log V) when using a priority queue.

3. (c) What is a spanning tree of a graph? Explain Kruskal’s algorithm. Why is it a greedy algorithm?

A spanning tree of a connected graph G(V,E) is a subgraph that includes all the vertices of G and has exactly V–1 edges, forming a tree (no cycles). A graph may have many spanning trees. Among these, a Minimum Spanning Tree (MST) is one with the minimum total weight of edges. MSTs are essential in network optimization, circuit design, clustering, and communication routing.

Kruskal’s Algorithm

Kruskal’s algorithm constructs the MST by repeatedly selecting the minimum-weight edge that does not form a cycle with the existing selected edges. It uses the Disjoint Set Union (DSU) or Union-Find structure to efficiently detect cycles.

Steps of Kruskal’s Algorithm:

1. Sort all edges in non-decreasing order of weights.
2. Initialize an empty MST set.
3. For each edge (u, v) in sorted order:
   • If u and v belong to different components, add the edge to the MST.
   • Else, ignore it because adding it would create a cycle.
4. Continue until MST contains V − 1 edges.

Union-Find operations ensure near constant-time checks for cycles.

Why is Kruskal Greedy?

Kruskal is greedy because at each step it selects the locally optimal choice—the smallest weight edge available—without considering future consequences. This locally optimal choice leads to a globally optimal MST, due to:

• Cut Property: The lightest edge across any cut must be part of some MST.
• Cycle Property: The heaviest edge in any cycle cannot be part of the MST.

Thus, picking the globally smallest safe edge is always correct.

Time Complexity

• Sorting edges: O(E log E)
• Union-Find operations: O(E α(V)), nearly linear

Total complexity: O(E log V).

Q4 – 10 Marks

4. (a) Find the structure of an Optimal Binary Search Tree (OBST) for keys A, B, C, D with probabilities:

A = 0.20, B = 0.10, C = 0.45, D = 0.25

An Optimal Binary Search Tree (OBST) minimizes the expected search cost by arranging keys so that frequently accessed keys appear near the root. OBST uses Dynamic Programming to compute matrices for cost, weight, and root selection. The main idea is that for each interval of keys, we try all possible roots and choose the one with minimal cost.

Step 1: Probability Table

Let P[i] be probability of key i.

No dummy keys are given, so we assume unsuccessful probabilities = 0.

Step 2: Weight Matrix W[i][j]

Step 3: Cost Matrix C[i][j]

Base case: C[i][i–1] = 0.

Cost formula:

Length 1 (single key):

C[1][1] = 0.20
C[2][2] = 0.10
C[3][3] = 0.45
C[4][4] = 0.25

Length 2:

For keys (A,B):
Try roots A and B:

• r=A: cost = W(1,2) + C[2][2] = 0.30 + 0.10 = 0.40
• r=B: cost = W(1,2) + C[1][1] = 0.30 + 0.20 = 0.50

Choose A → C[1][2] = 0.40, root = A.

Similarly:

• C[2][3] = 0.55 + min(0.45, 0.10) = 0.65, root = C
• C[3][4] = 0.70 + min(0.25, 0.45) = 0.95, root = D

Length 3 (A,B,C):

Try roots A, B, C:

• r=A → 0 + C[2][3] = 0.65
• r=B → 0.20 + 0.45 = 0.65
• r=C → 0.40 + 0 = 0.40

Cost = W(1,3) + 0.40 = 0.75 + 0.40 = 1.15, root = C

Length 4 (A,B,C,D):

Try roots A, B, C, D:

• r=C gives minimal cost ⇒ best split.

Cost = W(1,4) + C[1][2] + C[4][4]
= 1.00 + 0.40 + 0.25
= 1.65

Final OBST Structure:

        C
      /   \
     A     D
      \
       B

C is root because it has the highest probability.

4. (b) Give the algorithm to solve the 8-Queen problem using Backtracking.

The 8-Queen problem asks for placing 8 queens on an 8×8 chessboard so that no two queens attack each other. Queens attack horizontally, vertically, and diagonally. Because this problem requires exploring multiple possible arrangements and withdrawing from invalid positions, the Backtracking technique is used.

Concept of Backtracking

Backtracking is a depth-first search strategy for solving constraint satisfaction problems. We try placing queens one by one in each row, checking whether the current placement is safe. If placing a queen leads to a conflict, we backtrack and try another column.

Algorithm Steps

1. Start with row = 1.
2. For each column in that row, check whether placing a queen is safe:
   • No queen exists in the same column.
   • No queen exists on the left diagonal.
   • No queen exists on the right diagonal.
3. If safe, place queen and move to next row.
4. If the row exceeds 8, a solution is found and printed.
5. If no column is valid, backtrack to previous row.

Pseudo-Code

procedure SolveNQueen(row)
    if row > 8:
        print Board
        return
    
    for col from 1 to 8:
        if isSafe(row, col):
            placeQueen(row, col)
            SolveNQueen(row + 1)
            removeQueen(row, col)

Safety Check

function isSafe(row, col):
    for each previous row i:
        if col == queen[i].col → conflict
        if |row - i| == |col - queen[i].col| → diagonal conflict
    return true

Why Backtracking Works

Backtracking systematically explores every possibility but avoids unnecessary exploration through pruning. It ensures correctness and reduces computation significantly.

Output

There are 92 valid solutions to the 8-Queen problem. Backtracking efficiently finds all of them.

4. (c) Explain how the Travelling Salesman Problem (TSP) can be solved using Branch and Bound.

The Travelling Salesman Problem (TSP) requires finding the minimum-cost route that visits every city exactly once and returns to the starting point. TSP is NP-hard, meaning exponential time may be required in the worst case. However, Branch and Bound (B&B) greatly reduces computation through systematic pruning.

Branching Strategy

1. Each node in the search tree represents a partial tour.
2. The root node starts with no edges selected.
3. Branching occurs by including or excluding edges.
4. Each branch leads to a new partial solution.

Lower Bound Calculation

A lower bound estimates the minimum possible tour cost from a partial tour. It is computed using:

• Reduced cost matrix
• Minimum outgoing edges
• 2-opt lower bounds
• Sum of two smallest edges from each node

If the lower bound of a node is greater than the best known solution, that node is pruned (discarded).

Bounding Example

For a partial path including edges (A → B → C), we compute:

1. Reduced matrix by setting used edges = 0
2. Summing minimum row and column values
3. Adding partial path cost

This gives a bound B.

If B ≥ bestCost, prune.

Algorithm Steps

1. Create initial reduced cost matrix and compute root bound.
2. Insert root into priority queue (min-heap).
3. Repeatedly pick node with lowest bound.
4. Branch by selecting next edge (include/exclude).
5. Recompute bound for each child.
6. Prune nodes with high bound.
7. When a complete Hamiltonian cycle is found, update bestCost.
8. Continue until heap becomes empty.

Why Branch and Bound Works Well

• It cuts off huge parts of the search space.
• Guarantees optimal solution.
• Performs efficiently on medium-sized problems (10–20 cities).

Time Complexity

Worst case = O(n!)
Practical performance = greatly reduced due to pruning.

Q5 – 10 Marks

5. (a) Set the recurrence relation for Binary Search and determine its time complexity.

Binary Search is one of the most efficient searching techniques used on a sorted array. It repeatedly divides the search interval into two halves and eliminates the half in which the target value cannot lie. Because of this divide-and-conquer nature, it achieves logarithmic time complexity.

Recurrence Relation

Assume Binary Search is applied on an array of size n. At each step, we compare the target value with the middle element:

• If equal → search ends.
• If target < mid → recursively search the left half (size = n/2).
• If target > mid → recursively search the right half (size = n/2).

Every recursive call reduces the problem size from n to n/2, and we perform only constant work (comparison, midpoint calculation).

Therefore, the recurrence is:

This reflects one recursive call on half the previous input size and a constant amount of overhead.

Solving the Recurrence

Using the Master Theorem or repeated expansion:

Expand the recurrence:

We stop when:

Substituting:

Thus, the time complexity of Binary Search is:

Space Complexity

• Recursive version: O(log n) due to recursion stack
• Iterative version: O(1)

Conclusion

Binary Search achieves logarithmic performance because it eliminates half of the search space at each step. The recurrence relation directly solves to O(log n). This efficiency makes Binary Search fundamental in searching applications, tree algorithms, and system-level optimizations.

5. (b) Give Big-Theta estimation of ln(n) and log₂(n).

Big-Theta (Θ) notation describes the tight bound of a function. It captures both upper and lower asymptotic limits, meaning:

1. Big-Theta of ln(n)

The natural logarithm function grows very slowly compared to polynomial and exponential functions. Some key properties:

• ln(n) increases without bound, but very slowly.
• ln(n) = logₑ(n).
• Derivative decreases as n increases, meaning slow growth.

Since ln(n) is a standard function in asymptotic analysis:

This means any logarithm base differs only by a constant factor:

Since constants are ignored in Big-Theta:

2. Big-Theta of log₂(n)

The change-of-base formula states:

Meaning all logarithms differ only by constant factors. So:

Therefore:

Comparison

Both ln(n) and log₂(n) grow at the same asymptotic rate, because:

• Multiplying by a constant factor does not change Big-Theta.
• Both functions grow slower than any (polynomial).
• Both grow faster than any constant or polylogarithmic variant like log(log n).

Final Conclusion

Logarithmic functions with different bases are asymptotically equal.

5. (c) Define: Spanning Tree, Optimal Binary Search Tree, Hamiltonian Cycle, Subgraph, Catalan Number

Below are detailed 10-marks level definitions:

1. Spanning Tree

A spanning tree of a connected graph G(V,E) is a subgraph that:

• Contains all vertices of G
• Has exactly V − 1 edges
• Is connected
• Contains no cycles

A graph may have many spanning trees. If edges have weights, the spanning tree with minimum total weight is called the Minimum Spanning Tree (MST).

2. Optimal Binary Search Tree (OBST)

An OBST is a binary search tree that minimizes the expected search cost based on the probabilities of searching for keys. Frequently accessed keys are placed near the root. OBST is constructed using Dynamic Programming, storing matrices for cost, weight, and root choices. It is used in compilers, dictionary lookups, and database indexing.

3. Hamiltonian Cycle

A Hamiltonian Cycle in a graph is a cycle that:

• Visits every vertex exactly once
• Returns to the starting vertex
• Does not repeat any vertex

Graphs that contain such cycles are called Hamiltonian graphs. The problem of determining a Hamiltonian cycle is NP-complete, and is core to TSP.

4. Subgraph

A subgraph H(V’,E’) of a graph G(V,E) is a graph where:

• V’ ⊆ V
• E’ ⊆ E
• Each edge in E’ connects vertices in V’

A subgraph may be formed by deleting edges, deleting vertices, or both. Trees, cycles, and paths in a graph are examples of subgraphs.

5. Catalan Number

Catalan numbers form a famous sequence in combinatorics. The nth Catalan number is:

Catalan numbers count many structures:

• Number of valid parenthesis expressions
• Number of BSTs possible with n keys
• Number of ways to triangulate a polygon
• Number of ways to arrange non-crossing partitions

They grow approximately as: