AL-402 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
   aSolve the following recurrence relation using recursion tree method: $$T(n) = 2T(n/2) + n$$ $$T(1) = O(1)$$
   How to answer

   • Define recursion tree with root cost n and branching factor 2
   • Expand levels: level i has 2^i nodes each cost n/2^i, total n per level
   • Number of levels log n with leaf cost O(1)
   • Sum total cost n log n to get T(n) = O(n log n)
2. 7 Marks
   bShow the following recurrence relation using Master's theorem: $$T(n) = 2T(n/2) + n \log n$$
   How to answer

   • State Master's theorem cases for T(n)=aT(n/b)+f(n)
   • Identify a=2, b=2, f(n)=n log n
   • Compare f(n) with n^{log_b a}=n
   • Conclude case and final Theta bound
3. 7 Marks
   aFind the number of comparisons made by the sequential search for the worst and best case.
   How to answer

   • State sequential search scanning from first element
   • Best case: key at first position gives 1 comparison
   • Worst case: key at last or absent gives n comparisons
   • Give O(1) best and O(n) worst
4. 7 Marks
   bApply Quick sort on the array given below: 15, 31, 1, 9, 80, 12, 14, 7, 24
   How to answer

   • Choose pivot and partition step
   • Show recursive partitions for given array
   • Trace swaps and pivot positions
   • Give final sorted array
5. 7 Marks
   aList various problems that can be solved using the Greedy algorithm approach.
   How to answer

   • Define greedy choice property
   • List problems: fractional knapsack, MST, Huffman, activity selection, Dijkstra
   • Brief condition for applicability
   • Give examples
6. 7 Marks
   bWrite Kruskal's algorithm to find MST for a given graph. Also discuss about its time complexity.
   How to answer

   • Write steps: sort edges, initialize disjoint sets, pick safe edge
   • Explain cycle avoidance using union-find
   • Analyze sorting O(E log E) dominating
   • Give total time complexity O(E log V)
7. 7 Marks
   aWrite Dijkstra's Algorithm for the solution of single source shortest path problem.
   How to answer

   • Initialize distance, visited set with source 0
   • Repeatedly relax edges from min-distance vertex
   • Update predecessors for shortest paths
   • Give O(V^2) / O(E log V) complexity
8. 7 Marks
   bExplain fractional Knapsack problem in detail.
   How to answer

   • Define fractional knapsack with capacity and profit/weight
   • Explain greedy by profit/weight ratio sorting
   • Describe steps with fractional allowance
   • Give example and O(n log n) time
9. 7 Marks
   aWhat is 0/1 Knapsack problem? Is Greedy method effective to solve 0/1 Knapsack problem.
   How to answer

   • Define 0/1 knapsack with binary choice constraint
   • Contrast with fractional version
   • Explain why greedy fails with counterexample
   • State need for DP / branch and bound
10. 7 Marks
    bIs there anything common between dynamic programming and divide and conquer? What is the main difference between the two?
    How to answer

    • State common divide-and-conquer structure
    • Explain overlapping subproblems and memoization in DP
    • Contrast optimal substructure usage
    • Give examples of each
11. 7 Marks
    aObtain any two solutions to 4-queens problem. Establish the relationship between them.
    How to answer

    • Explain 4-queens constraints: row, column, diagonal
    • Show two solutions e.g. [2,4,1,3] and [3,1,4,2]
    • Draw 4x4 board placements
    • Establish symmetry / complement relationship
12. 7 Marks
    bConstruct the minimum spanning tree for the given graph using Kruskal's Algorithm:

    

    How to answer

    • List all edges sorted by weight: 10,12,14,16,18,22,24,25,28
    • Iteratively add safe edges avoiding cycles using Kruskal
    • Construct MST with 6 edges
    • Compute total minimum cost
13. 7 Marks
    aWrite an algorithm for the implementation of binary search method.
    How to answer

    • State divide and conquer with low, high, mid
    • Give pseudocode with comparison and recursion/iteration
    • Explain O(log n) time on sorted array
    • Mention termination conditions
14. 7 Marks
    bSolve the following instance of Knapsack problem by using the branch and bound technique:

    

    How to answer

    • Compute profit/weight ratios and sort items
    • Build branch and bound state space tree with bounds
    • Prune infeasible / non-promising nodes with W=16
    • Report optimal 0/1 selection and max profit
15. 7 Marks
    aExplain the class NP-complete with example.
    How to answer

    • Define NP-complete as NP and NP-hard
    • Explain polynomial reduction concept
    • Give examples: SAT, TSP, knapsack, clique
    • Mention verification in polynomial time
16. 7 Marks
    bThere are 8, 15, 13 and 14 number of nodes in 4 different trees. Which of them could have formed a Full Binary Tree?
    How to answer

    • Define full binary tree: each node 0 or 2 children
    • Use property n = 2h+1 -1 i.e. odd number of nodes
    • Check 8,15,13,14 for odd / 2^k-1 form
    • Conclude only 15 can form full binary tree