IT-403 Analysis and Design of Algorithm - Jun 2023 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
   aExplain algorithm design technique? How do you measure the algorithm running time?
   How to answer

   • Define algorithm design technique and list major techniques
   • Define running time and input size
   • Explain measurement via time complexity, asymptotic notations
   • Mention experimental vs theoretical analysis and best/worst/average case
2. 7 Marks
   bGive the divide and conquer solution for binary search and analyze the time complexity for it.
   How to answer

   • State divide and conquer principle for binary search
   • Write pseudocode/recurrence for binary search
   • Analyze recurrence T(n)=T(n/2)+O(1)
   • Conclude O(log n) time complexity
3. 7 Marks
   aExplain the quick sort algorithm, simulate it with the following data 20, 35, 10, 16, 54, 21, 25.
   How to answer

   • Explain quick sort partition and recursive steps
   • Show pivoting steps on given data
   • Trace subarrays and swaps to sorted order
   • State average/worst case complexity
4. 7 Marks
   bCompute the optimal solution for job sequencing with deadlines using greedy method. $N = 4$, profits $(p_1, p_2, p_3, p_4) = (100, 10, 15, 27)$, deadlines $(d_1, d_2, d_3, d_4) = (2, 1, 2, 1)$.
   How to answer

   • Sort jobs by profit descending
   • Check deadline feasibility for slots
   • Construct optimal sequence and compute total profit
   • Show greedy steps for N=4 instance
5. 7 Marks
   aConsider the following instance of the knapsack problem and solve it using greedy method $n = 7, m = 15, (p_1, p_2, p_3, p_4, p_5, p_6, p_7) = (10, 5, 15, 7, 6, 18, 3)$ and $(w_1, w_2, w_3, w_4, w_5, w_6, w_7) = (2, 3, 5, 7, 1, 4, 1)$.
   How to answer

   • Compute profit/weight ratios
   • Sort items by ratio and take fractionally up to m=15
   • Calculate total profit and selection vector
   • State greedy knapsack steps
6. 7 Marks
   bApply the kruskal algorithm for the following graph and explain.

   

   How to answer

   • State Kruskal's rule: sort edges and avoid cycles
   • List edges of given graph in increasing weight
   • Select edges step-by-step forming MST
   • Compute MST cost and show tree
7. 7 Marks
   aSolve the following 0/1 Knapsack problem using dynamic programming $P = (11, 21, 31, 33), W = (2, 12, 23, 15), C = 42, n = 4$.
   How to answer

   • Formulate 0/1 knapsack DP table for n=4, C=42
   • Fill profit table using recurrence
   • Trace back optimal item selection
   • State maximum profit and selected items
8. 7 Marks
   bDesign a three stage reliability system with device types $d_1, d_2$ and $d_3$. The costs are $\$30, \$15$ and $\$20$ respectively. The cost of the system is to be no more than $\$105$. The reliability of each device is 0.9, 0.8 and 0.5 respectively.
   How to answer

   • State reliability optimization model with cost constraint $105
   • Use DP for device redundancy allocation
   • Evaluate reliability for stage counts
   • Give optimal numbers of devices per stage
9. 7 Marks
   aOn which type of problem we apply multi stage graph technique? Explain with example.
   How to answer

   • Define multistage graph and its structure
   • State shortest/longest path type problems solved
   • Explain forward/backward DP recurrence
   • Give example graph and solution
10. 7 Marks
    bBriefly explain 8-queen problem using backtracking with algorithm.
    How to answer

    • State 8-queen constraints and backtracking idea
    • Explain placement and bounding / kill test
    • Outline recursive algorithm steps
    • Mention solution tree search
11. 7 Marks
    aIdentify the Hamiltonian cycle from the following graph.

    

    How to answer

    • Define Hamiltonian cycle condition
    • Examine adjacency of v1-v5 graph
    • Trace a cycle visiting all vertices once
    • State identified Hamiltonian cycle
12. 7 Marks
    bWrite an algorithm for traveling salesperson problem using check bounds.
    How to answer

    • State TSP branch and bound / check bounds principle
    • Explain bounding function and state space tree
    • Write stepwise algorithm / pseudocode
    • Mention complexity and pruning
13. 7 Marks
    aDiscuss the operations performed on the binary search tree for the following data : 20, 49, 41, 93, 69, 90, 76, 62, 81, 75, 10, 79, 87, 38 and delete 41 and 76.
    How to answer

    • Show BST insertions for 20,49,41,93,69,90,76,62,81,75,10,79,87,38
    • Draw tree after insertions
    • Show deletion of 41 and 76 with cases
    • Show final BST structure
14. 7 Marks
    bDifferentiate between BFS and DFS.
    How to answer

    • Define BFS queue-based level order traversal
    • Define DFS stack/recursion-based depth traversal
    • Compare on data structure, time/space, applications
    • Give example traversal difference
15. 14 Marks
    Write short notes on any two of the following.

    1. a)2-3 trees
    2. b)Merge sort
    3. c)Optimal merge patterns
    4. d)Floyd Warshall algorithm
    How to answer

    • Select any two topics from list
    • Give definition, working and steps for each
    • Mention time complexity and application
    • Give example/diagram if applicable