AL-402 Analysis & Design of Algorithms - Jun 2026 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
   aFor the function $f(n) = 1000n^2 + 100n + 6$. Find the Big Oh notation.
   How to answer

   • Define Big-O formally with constants c and n0
   • Bound 1000n^2+100n+6 <= c*n^2 for n>=n0
   • Identify dominant term n^2 and choose c, n0
   • Conclude f(n) = O(n^2)
2. 7 Marks
   bApply quicksort on the given array: 15, 31, 1, 9, 80, 12, 14, 7, 24.
   How to answer

   • Choose pivot strategy and partition rule
   • Show partition steps for array
   • Recurse on left and right subarrays
   • Give final sorted array
3. 7 Marks
   aWrite an algorithm to search an element using binary search method. Analyse this algorithm for worst, average and best cases.
   How to answer

   • Write binary search pseudocode for sorted array
   • Explain low, high, mid iteration
   • Derive best, average, worst case complexities
   • Give example trace
4. 7 Marks
   bSolve the following recurrence relation- $T(n) = 2T(n/2) + n$.
   How to answer

   • Identify form T(n)=2T(n/2)+n
   • Apply Master theorem or recursion tree
   • Expand levels and sum cost per level
   • Conclude T(n)=Theta(n log n)
5. 7 Marks
   a

   Consider that there are three items. Weight and profit value of each item is as given below:

   i	Wi	Pi
   1	18	30
   2	15	21
   3	10	18

   Also $W=20$. Obtain the solution for the above given Knapsack problem.

   How to answer

   • Compute profit/weight ratios and sort
   • Apply fractional knapsack greedy selection for W=20
   • Calculate fractions taken and total profit
   • State optimal solution vector
6. 7 Marks
   bExplain 0-1 Knapsack problem and discuss its solution.
   How to answer

   • Define 0-1 knapsack with binary choice constraint
   • Contrast with fractional knapsack
   • Explain DP recurrence / table solution
   • Discuss complexity and example
7. 7 Marks
   aWhat is "Greedy Algorithm"? Write its pseudocode. Apply Greedy algorithm on colouring the vertices of a given graph.
   How to answer

   • Define greedy choice property
   • Write general greedy pseudocode
   • Explain vertex colouring greedy steps
   • Show colour assignment on example graph
8. 7 Marks
   bExplain Kruskal's algorithm with the help of suitable example.
   How to answer

   • Explain MST and Kruskal sorting of edges
   • Describe union-find cycle avoidance steps
   • Trace on example graph with edge selection
   • State time complexity O(E log E)
9. 7 Marks
   aDescribe Floyd Warshall's algorithm with a suitable example.
   How to answer

   • Define all-pairs shortest path DP formulation
   • Give Floyd-Warshall triple loop with recurrence
   • Trace distance matrix updates on example
   • State O(n^3) complexity
10. 7 Marks
    bCompare dynamic programming, greedy method and divide and conquer method in detail.
    How to answer

    • Define each paradigm and its principle
    • Compare on basis of subproblems, optimality, examples
    • Present comparison table
    • Conclude when each is applicable
11. 7 Marks
    aObtain any 2 solutions to 4-queen's problem. Establish the relationship between them.
    How to answer

    • Explain 4-queens constraints
    • Show backtracking placement steps for two solutions
    • Draw board configurations
    • Explain symmetry / relationship between solutions
12. 7 Marks
    bWhat is Hamiltonian cycle? Explain how it can be solved using backtracking approach?
    How to answer

    • Define Hamiltonian cycle
    • Explain backtracking state space and pruning
    • Give algorithm steps / pseudocode
    • Trace on example graph
13. 7 Marks
    aDescribe the lower bound theory and its use in solving algebraic problems.
    How to answer

    • Define lower bound and decision tree model
    • Explain techniques to prove lower bounds
    • Apply to sorting / searching algebraic problems
    • State significance for optimality
14. 7 Marks
    bExplain Travelling Salesman Problem in detail.
    How to answer

    • Define TSP tour and objective
    • Explain DP / branch-and-bound / approximation approaches
    • Give example with distance matrix and tour cost
    • Discuss complexity as NP-hard
15. 7 Marks
    aExplain the difference between P and NP.
    How to answer

    • Define P as polynomial-time solvable
    • Define NP as nondeterministic polynomial verifiable
    • Compare on determinism, verification, examples
    • Mention P vs NP open problem
16. 7 Marks
    bExplain approximation algorithms for Vertex Cover.
    How to answer

    • Define vertex cover problem
    • Describe greedy 2-approximation algorithm steps
    • Explain approximation ratio proof
    • Give example trace