IT-403 Analysis and Design of Algorithm - Jun 2022 Question Paper

Under each question, How to answer lists the points an answer should cover, outlined by CampusPrep from the syllabus. Check the details against your textbook.

1. 7 Marks
   aWith the help of a flow chart, explain the various steps of algorithm design and analysis process.
   How to answer

   • Draw flowchart showing steps: Problem definition, Model formulation, Algorithm design, Correctness proof, Analysis (time/space), Coding/Implementation
   • Briefly explain each step in the sequence
   • Discuss feedback loops (refining/redesigning algorithms)
2. 7 Marks
   bWhat are the significance of various asymptotic notations? Express the following assertions using three asymptotic notations with proof from its definition i) $n(n-1)/2$ ii) $6 \cdot 2^n + n^2$ iii) $100n + 7$
   How to answer

   • Define Big-O, Big-Omega, Big-Theta notations and their significance in analyzing time complexity
   • For $n(n-1)/2$: show it is $O(n^2)$, $\Omega(n^2)$, and $\Theta(n^2)$ using constants $c$ and $n_0$
   • For $6 \cdot 2^n + n^2$: show it is $O(2^n)$, $\Omega(2^n)$, and $\Theta(2^n)$
   • For $100n + 7$: show it is $O(n)$, $\Omega(n)$, and $\Theta(n)$
3. 7 Marks
   aWrite an algorithm to sort $n$ numbers using Quick Sort. Trace the algorithm to sort the following list in an ascending order: 65, 70, 75, 80, 85, 60, 55, 50
   How to answer

   • Write algorithm/pseudocode for QuickSort and Partition functions
   • Trace step-by-step partitioning on the list [65, 70, 75, 80, 85, 60, 55, 50]
   • Show recursive calls and sub-arrays at each stage until completely sorted
4. 7 Marks
   bDiscuss the general Divide and Conquer technique with control abstraction and recurrence relation.
   How to answer

   • Explain the three steps of Divide and Conquer: Divide, Conquer, Combine
   • Write the standard Control Abstraction algorithm (DAndC(P))
   • Formulate the general recurrence relation: $T(n) = a T(n/b) + f(n)$
   • Briefly mention examples (Merge Sort, Binary Search)
5. 7 Marks
   aDiscuss how to find maximum and minimum element in an array recursively? Trace the same for the following data set 65, 70, 75, 80, 85, 60, 55, 50. Also derive the worst case complexity.
   How to answer

   • Explain recursive Divide and Conquer Max-Min algorithm
   • Trace the binary splitting tree on 65, 70, 75, 80, 85, 60, 55, 50
   • Set up the recurrence relation $T(n) = 2T(n/2) + 2$
   • Solve recurrence to obtain $T(n) = \frac{3n}{2} - 2$ comparisons
6. 7 Marks
   bBriefly explain the Strassen's matrix multiplication. Apply it to multiply the following matrices. Explain how this method is better than direct multiplication method. $$\begin{bmatrix} 4 & 3 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} 2 & 5 \\ 1 & 6 \end{bmatrix}$$
   How to answer

   • Explain Strassen's matrix multiplication using 7 multiplications instead of 8
   • Calculate $M_1$ through $M_7$ with the given $2 \times 2$ matrices
   • Compute $C_{11}, C_{12}, C_{21}, C_{22}$ from $M_1 \dots M_7$
   • Compare complexity: $O(n^{\log_2 7}) \approx O(n^{2.81})$ vs direct method's $O(n^3)$
7. 7 Marks
   aRecall the concept of greedy techniques. Find the optimal solution to the Knapsack instance $n = 7$, $m = 15$. $(P_1, P_2, \dots, P_7) = (10, 5, 15, 7, 6, 18, 3)$ $(W_1, W_2, \dots, W_7) = (2, 3, 5, 7, 1, 4, 1)$
   How to answer

   • Explain the greedy choice property and greedy technique
   • Compute profit/weight ratios for all 7 items
   • Sort items in descending order of profit/weight ratio
   • Greedily include whole items and take fraction of the final fitting item
   • Calculate total profit obtained
8. 7 Marks
   bUsing the Prim's Algorithm, determine the minimum cost spanning tree of the graph of figure:

   

   How to answer

   • State Prim's algorithm steps
   • Select an initial vertex (e.g., vertex 1)
   • Iteratively pick the minimum-weight cut edge connecting tree to non-tree vertices
   • List added edges and sequence: e.g. (1,6)=10, (6,5)=25 or (1,2)=28, (2,7)=14, (7,4)=18, (4,3)=12, (3,2)=16, etc.
   • Calculate total MST cost and draw the resulting MST
9. 7 Marks
   aExplain the dynamic programming. Generate transitive closure of the graph given in the figure give below:

   

   How to answer

   • Explain principles of dynamic programming (optimal substructure, overlapping subproblems)
   • State Warshall's algorithm for finding transitive closure
   • Set up initial adjacency matrix $R^{(0)}$ from the directed 4-cycle graph (1->2->3->4->1)
   • Compute intermediate matrices $R^{(1)}, R^{(2)}, R^{(3)}, R^{(4)}$
   • Present final transitive closure matrix where all entries are 1
10. 7 Marks
    bUsing Floyd's algorithm, find all pairs of shortest path for the graph in the figure given below:

    

    How to answer

    • State Floyd's algorithm recurrence: $D^{(k)}[i,j] = \min(D^{(k-1)}[i,j], D^{(k-1)}[i,k] + D^{(k-1)}[k,j])$
    • Construct initial distance matrix $D^{(0)}$ from the given graph
    • Calculate matrices $D^{(1)}, D^{(2)}, D^{(3)}$ successively
    • State final all-pairs shortest path distance matrix
11. 7 Marks
    aExplain Backtracking Concept. Construct the state-space tree for solving 4-Queen's problem using backtracking.
    How to answer

    • Explain the concept of backtracking and depth-first exploration with pruning
    • Define 4-Queens problem constraints (no two queens in same row, column, or diagonal)
    • Draw the state-space tree showing explored nodes, pruned branches, and reaching a solution (e.g., [2, 4, 1, 3] or [3, 1, 4, 2])
12. 7 Marks
    bWhat is Branch and Bound algorithm? Write the steps and apply nearest neighbour approximation algorithm on the Travelling Salesperson Problem with the starting vertex $a$, and calculate the accuracy ratio of approximation.

    

    How to answer

    • Define Branch and Bound method and state its core steps
    • Describe Nearest Neighbour approximation algorithm for TSP
    • Apply Nearest Neighbour starting at vertex $a$: $a \to b (1) \to c (2) \to d (1) \to a (6)$, total cost = 10
    • Find optimal tour cost: e.g., $a-b-d-c-a$ with cost $1+3+1+3=8$
    • Calculate accuracy ratio: $10 / 8 = 1.25$
13. 7 Marks
    aWhat is a Decision Tree? Give a decision tree for 3 elements selection sort for arranging the items in ascending order and estimate its lower bound.
    How to answer

    • Define decision tree for comparison-based algorithms
    • Draw the full comparison decision tree for selection sorting 3 elements ($x_1, x_2, x_3$)
    • Show how the $3! = 6$ permutations appear as leaves
    • Calculate lower bound: height $h \ge \lceil \log_2(3!) \rceil = \lceil \log_2 6 \rceil = 3$
14. 7 Marks
    bApply DFS algorithm to solve the topological sorting problem for the graph in the figure given below:

    

    How to answer

    • Explain topological sorting via DFS (ordering by decreasing finish times)
    • Trace DFS traversal starting from appropriate sources, recording start/finish times for all vertices
    • Order vertices in reverse order of finish times to obtain topological ordering
15. 14 Marks
    Explain any two of the followings with examples: a) AVL Tree b) Hamiltonian Problem c) M - Coloring d) NP-Complete Problem
    How to answer

    • Select any two topics to answer (7 marks each)
    • For AVL Tree: define self-balancing binary search tree, balance factor $\{-1, 0, +1\}$, rotations (LL, RR, LR, RL) with an example
    • For Hamiltonian Problem: define Hamiltonian path and cycle, discuss NP-completeness and backtracking formulation with example
    • For M-Coloring: define vertex coloring using at most m colors such that no adjacent vertices share a color, illustrate with a graph example
    • For NP-Complete Problem: define P, NP, NP-hard, NP-complete, polynomial time verification, and give standard examples (SAT, Clique)