IT-403 Analysis and Design of Algorithm - Jun 2025 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
   aWrite a recursive algorithm for computing the $n^{th}$ Fibonacci number.
   How to answer

   • Define $F(n)=F(n-1)+F(n-2)$ with $F(0)=0, F(1)=1
   • Write recursive procedure FIB(n) with base cases
   • Explain recursive calls and termination
   • Mention time complexity $T(n)=T(n-1)+T(n-2)+O(1)$ exponential
2. 7 Marks
   bA machine needs a minimum of 200 sec to sort 1000 elements by Quick sort. What is the minimum time needed to sort 200 elements will be approximately?
   How to answer

   • Assume average-case Quick sort $O(n \log n)$
   • Use ratio $T_2/T_1 = (n_2 \log n_2)/(n_1 \log n_1)$
   • Substitute $n_1=1000, T_1=200$ sec, $n_2=200$
   • Compute approximate minimum time in seconds
3. 7 Marks
   aGenerate recurrence relation from the recursive binary search algorithm.
   How to answer

   • Show binary search halves array and one comparison per call
   • Write $T(n)=T(n/2)+O(1)$ with $T(1)=O(1)$
   • Explain worst/average case recurrence
   • Mention solution $O(\log n)$
4. 7 Marks
   bConsider the problem of finding the smallest and largest elements in an array of $n$ numbers using divide and conquer method.
   How to answer

   • Divide array of $n$ numbers into two halves
   • Recursively find min and max in each half
   • Combine with 2 comparisons
   • Derive recurrence and $3n/2-2$ comparisons vs $2n-2$ naive
5. 7 Marks
   aFind the time complexity of the recurrence relation $T(n)= n + T(n/10) + T(7n/5)$.
   How to answer

   • Identify form $T(n)=n+T(n/10)+T(7n/5)$
   • Discuss recursion tree / substitution attempt
   • Note $7n/5 > n$ so not standard decreasing recurrence
   • Conclude about divergence / no $O(n^k)$ bound under usual assumption
6. 7 Marks
   bAnalyze the time complexity of Strassen's algorithm compared to conventional matrix multiplication.
   How to answer

   • State conventional $O(n^3)$ matrix multiplication
   • State Strassen recurrence $T(n)=7T(n/2)+O(n^2)$
   • Solve to $O(n^{\log_2 7}) \approx O(n^{2.81})$
   • Compare constants, crossover and practical implications
7. 7 Marks
   aWhat is Minimum Cost Spanning Tree? Explain Kruskal's Algorithm with the help of algorithm.
   How to answer

   • Define spanning tree and minimum cost criterion
   • Explain Kruskal sorting edges and union-find cycle avoidance
   • Give steps/pseudocode and example
   • State complexity $O(E \log E)$ and correctness idea
8. 7 Marks
   bThe recurrence $T(n) = 7T(n/2) + n^2$ describe the running time of an algorithm A. A competing algorithm A' has a running time of $T'(n) = aT'(n/4) + n^2$. What is the largest integer value for $a$ $A'$ is asymptotically faster than A?
   How to answer

   • Apply Master theorem to $T(n)=7T(n/2)+n^2$ to get $\Theta(n^{\log_2 7})$
   • Apply Master theorem to $T'(n)=aT'(n/4)+n^2$
   • Compare exponents $\log_4 a$ vs 2 for $a$ threshold
   • Find largest integer $a$ with $A'$ asymptotically faster than $A$
9. 7 Marks
   aExplain properties of Binomial Heap in. Write an algorithm to perform uniting two Binomial Heaps. And also, to find Minimum Key.
   How to answer

   • Define binomial heap as collection of binomial trees
   • List properties: heap-order, $B_k$ structure, at most one tree per degree
   • Give UNION procedure merging root lists by degree
   • Give FIND-MIN scanning roots
10. 7 Marks
    bExplain Backtracking. Let set $S = \{1, 3, 4, 5\}$ and $X = 8$, we have to find subset sum problem using backtracking approach.
    How to answer

    • Define backtracking as systematic trial with pruning
    • Model subset-sum with state-space tree for $S=\{1,3,4,5\}, X=8$
    • Show bounding and backtrack steps to find subsets
    • List solutions e.g. $\{3,5\}, \{1,3,4\}$
11. 7 Marks
    aWhat is stable sorting algorithm? Which of the sorting algorithms we have seen are stable and which are unstable? Give name with explanation.
    How to answer

    • Define stable sort preserving equal-key order
    • Classify e.g. Merge, Bubble, Insertion as stable
    • Classify e.g. Quick, Heap, Selection as unstable
    • Explain with example why stability matters
12. 7 Marks
    bSuppose character a, b, c, d, e, f has probabilities 0.07, 0.09, 0.12, 0.22, 0.23, 0.27 respectively. Find an optional Huffman code and draw the Huffman tree. What is the average code length?
    How to answer

    • Sort probabilities and repeatedly combine two smallest
    • Construct Huffman tree step by step
    • Assign 0/1 codes and compute codewords for a-f
    • Compute average length $L=\sum p_i l_i$
13. 7 Marks
    aWrite Merge sort algorithm and sort the following sequence $\{23, 11, 5, 15, 68, 31, 4, 17\}$ using merge sort.
    How to answer

    • Write MERGE-SORT divide, conquer, MERGE procedures
    • Recursively split $\{23,11,5,15,68,31,4,17\}$
    • Show merging steps in order
    • Give final sorted sequence
14. 7 Marks
    bExplain B-Tree and its properties. Also write B-Tree deletion cases with example.
    How to answer

    • Define B-Tree of order/m-degree and its properties
    • Explain height, keys, occupancy invariants
    • Describe deletion cases: leaf, internal, borrowing, merging
    • Illustrate each case with example
15. 7 Marks
    aFor a binary tree T, the preorder and in-order traversal sequences are as follows: In order : B C A E G D H F I J Preorder : A B C D E G F H I J

    1. i)Construct a binary Tree.
    2. ii)What is its post-order traversal sequence?
    How to answer

    • Use inorder to split left/right subtrees with preorder root
    • Recursively construct tree for A B C D E G F H I J
    • Draw resulting binary tree T
    • Traverse to obtain postorder sequence
16. 7 Marks
    bProve that if the weights on the edge of the connected undirected graph are distinct then there is a unique Minimum Spanning Tree. Give an example in this regard. Also discuss Kruskal's Minimum Spanning Tree in detail.
    How to answer

    • Assume two distinct MSTs and consider minimum differing edge
    • Use cut/cycle property with distinct weights for contradiction
    • Conclude uniqueness of MST
    • Give weighted graph example and outline Kruskal's steps