CS-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

   • State definition $f(n)=O(g(n))$ with constants $c, n_0$.
   • Bound $1000n^2+100n+6 \le c n^2$ for $n\ge n_0$.
   • Conclude $f(n)=O(n^2)$ and give example $c, n_0$.
2. 7 Marks
   bApply quicksort on the given array: 15, 31, 1, 9, 80, 12, 14, 7, 24.
   How to answer

   • Choose pivot and partition rule.
   • Show partition steps recursively.
   • Show intermediate arrays after each partition.
   • 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 mid comparison and halving.
   • Derive best $O(1)$, worst $O(\log n)$, average $O(\log n)$.
   • Give recurrence $T(n)=T(n/2)+O(1)$.
4. 7 Marks
   bSolve the following recurrence relation- $T(n) = 2T(n/2) + n$.
   How to answer

   • Identify $a=2, b=2, f(n)=n$.
   • Apply Master's theorem / iteration method.
   • Show $T(n)=n\log n + O(n)$.
   • 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 for 3 items.
   • Apply fractional knapsack greedy selection with $W=20$.
   • Show fraction 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 $x_i \in \{0,1\}$.
   • Give DP recurrence / formulation.
   • Explain optimal substructure and table filling.
   • Discuss complexity $O(nW)$ with 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 for graph colouring.
   • Apply vertex ordering 0-5 to given graph step by step.
   • State number of colours used.
8. 7 Marks
   bExplain Kruskal's algorithm with the help of suitable example.
   How to answer

   • State Kruskal's rule: sort edges, add if no cycle.
   • Show sorting and union-find steps on example.
   • Construct MST stage by stage.
   • Give total weight and 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 recurrence $D^{(k)}$.
   • Write triple-loop pseudocode.
   • Trace on small example graph matrix.
   • State complexity $O(V^3)$.
10. 7 Marks
    bCompare dynamic programming, greedy method and divide and conquer method in detail.
    How to answer

    • Define divide-and-conquer, greedy, DP principles.
    • Compare on basis of subproblems, optimality, examples.
    • Give table of differences.
    • State when each is applicable.
11. 7 Marks
    aObtain any 2 solutions to 4-queen's problem. Establish the relationship between them.
    How to answer

    • State 4-queens constraints (row, column, diagonal).
    • Show backtracking tree to get two board placements.
    • Draw/display the two $4\times4$ solutions.
    • Explain symmetry/relationship between them.
12. 7 Marks
    bWhat is Hamiltonian cycle? Explain how it can be solved using backtracking approach?
    How to answer

    • Define Hamiltonian cycle.
    • Write backtracking NextValue / Hamiltonian procedure.
    • Explain pruning using adjacency.
    • Give example trace and complexity.
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 trivial, information-theoretic bounds.
    • Apply to sorting/searching algebraic problems.
    • State use in proving optimality.
14. 7 Marks
    bExplain Travelling Salesman Problem in detail.
    How to answer

    • Define TSP tour and cost objective.
    • Discuss DP Held-Karp / branch-and-bound formulation.
    • Explain complexity and approximations.
    • Give small example tour.
15. 7 Marks
    aExplain the difference between P and NP.
    How to answer

    • Define class P (polynomial-time solvable).
    • Define class NP (nondeterministic / verifiable).
    • Compare on solving vs verifying, examples.
    • Discuss P vs NP question.
16. 7 Marks
    bExplain approximation algorithms for Vertex Cover.
    How to answer

    • Define vertex cover problem.
    • Write 2-approximation greedy matching algorithm.
    • Prove approximation ratio 2.
    • Give example and complexity.