IT-403 Analysis and Design of Algorithm - 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
   aIllustrate the operation of merge-sort on array A= (38, 27, 43, 3, 9, 82, 10). Also drive the time complexity of merge sort.
   How to answer

   • Divide array recursively into halves down to single elements
   • Merge step with comparisons to produce sorted subarrays, trace for given A
   • Final sorted array
   • Recurrence T(n)=2T(n/2)+O(n)
   • Solution O(n log n) in all cases
2. 7 Marks
   bExplain the steps involved in designing and analyzing algorithms. Discuss the criteria used to evaluate the efficiency of an algorithm.
   How to answer

   • Definition of algorithm design and analysis
   • Steps: problem understanding, model, design, correctness, analysis, implementation, testing
   • Efficiency criteria: time, space, optimality, simplicity
   • Measures: asymptotic, best/worst/average case
3. 7 Marks
   aWrite quick-sort partition algorithm. Drive best and worst-case time complexity of quick sort.
   How to answer

   • Partition pseudocode with pivot and indices i, j
   • Correctness of partitioning
   • Recurrence for best case balanced partition
   • Recurrence for worst case unbalanced partition
   • Best $O(n \log n)$, worst $O(n^2)$
4. 7 Marks
   b

   For the given set of items and knapsack capacity = 60 kg, find the optimal solution for the fractional knapsack problem making use of greedy approach.

   Item	1	2	3	4	5	6	7
   Weight	5	10	15	22	25	31	36
   Value	30	40	45	77	90	98	105

   How to answer

   • Compute value/weight ratio for each item
   • Sort items by decreasing ratio
   • Take items greedily up to capacity 60 kg
   • Take fraction of next item
   • Compute maximum total value
5. 7 Marks
   aWhat is Greedy algorithm? How greedy methods can be used to solve the optimization problem?
   How to answer

   • Definition of greedy algorithm and greedy choice
   • Components: greedy choice property, optimal substructure
   • General procedure for optimization problems
   • Example of application
6. 7 Marks
   bExplain the job sequencing with deadlines problem with suitable example. demonstrate how the Greedy algorithm schedules jobs to maximize profit.
   How to answer

   • Define jobs with deadlines and profits
   • Greedy rule: sort by profit descending
   • Schedule in latest free slot before deadline
   • Worked example
   • Profit maximization demonstration
7. 7 Marks
   aExplain the reliability design problem using the dynamic programming approach. Discuss the steps involved in obtaining an optimal solution with a suitable example.
   How to answer

   • Definition of reliability design problem
   • Dynamic programming formulation with stages
   • Recurrence for maximizing reliability
   • Steps to obtain optimal solution
   • Suitable example
8. 7 Marks
   b

   Apply the Floyd-Warshall algorithm to determine the shortest distances between all pair of vertices for the following weighted cost matrix:

   	A	B	C	D
   A	0	5	$\infty$	10
   B	$\infty$	0	3	$\infty$
   C	$\infty$	$\infty$	0	1
   D	$\infty$	$\infty$	$\infty$	0

   How to answer

   • Initialize distance matrix D0 from cost matrix
   • Iterative update Dk[i][j]=min(Dk-1[i][j], Dk-1[i][k]+Dk-1[k][j]) for k=A,B,C,D
   • Show intermediate matrices
   • Final all-pairs shortest distances
9. 7 Marks
   aFind the optimal solution to the 0/1 Knapsack instances with n=4 and Knapsack capacity m=8 where profits and weights as follows: P= {1, 2,5,6} and W= {2, 3, 4, 5}.
   How to answer

   • Formulate 0/1 knapsack DP table for n=4, m=8
   • Recurrence f[i][w]=max(f[i-1][w], p_i+f[i-1][w-w_i])
   • Fill table and traceback
   • Optimal profit and selected items
10. 7 Marks
    bDescribe the graph coloring problem and explain how the backtracking approach is used to solve it.
    How to answer

    • Definition of graph coloring and chromatic number
    • Backtracking state space and bounding
    • Algorithm steps with m-colorability
    • Example coloring
11. 7 Marks
    aIllustrate the N-queens problem? Draw "state space tree" for 8-queen problem using backtracking.
    How to answer

    • Rules: no two queens share row, column, diagonal
    • Backtracking placement row by row
    • State space tree pruning
    • Tree for 8-queen up to solution
12. 7 Marks
    bExplain the concept of lower bound theory. Also, describe the fundamentals of parallel algorithm.
    How to answer

    • Definition of lower bound and its use
    • Methods: comparison trees, oracle, etc.
    • Definition of parallel algorithm
    • Fundamentals: PRAM, speedup, efficiency
13. 7 Marks
    aConsider the travelling salesman instance defined by the following cost matrix: $$\begin{pmatrix} \infty & 5 & 1 & 10 & 6 \\ 1 & \infty & 4 & 12 & 7 \\ 3 & 6 & \infty & 4 & 16 \\ 7 & 1 & 3 & \infty & 9 \\ 16 & 12 & 7 & 6 & \infty \end{pmatrix}$$ Draw the state space tree with least cost branch & bound and show the reduced matrices corresponding to each of the node.

    

    How to answer

    • Reduce initial cost matrix and compute root cost
    • Branch on next city, compute reduced matrices and bounds
    • Draw state space tree with LC values
    • Select least-cost live node to optimal tour
14. 7 Marks
    bConstruct a BST by inserting the keys 45, 25, 60, 15, 35, 50, 70, 30 in the given order. Perform inorder, preorder, and postorder traversals of the resulting tree.
    How to answer

    • Insert keys in order maintaining BST property
    • Show resulting BST structure
    • Write inorder, preorder, postorder sequences
    • Verify traversals
15. 7 Marks
    aShow the result of inserting keys 25,31,38,76,5,60,38,8, 30,15,35,17 in order into an empty B-tree of order 5.
    How to answer

    • Definition of B-tree order 5
    • Insert keys stepwise with node splits
    • Show intermediate trees
    • Final B-tree structure
16. 7 Marks
    bExplain P, NP, NP -Complete and NP-Hard complexity classes. How they are related to each other.
    How to answer

    • Define P, NP, NP-Complete, NP-Hard
    • Deterministic vs nondeterministic polynomial time
    • Reducibility and completeness
    • Relationship diagram P subset NP, NPC subset NP