CS-402 Analysis Design of Algorithm - Jun 2022 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 Divide and Conquer techniques
   How to answer

   • Define divide and conquer with divide, conquer, combine phases
   • Explain general control structure / recurrence
   • Give examples like merge sort, quick sort, binary search
   • Mention advantages and complexity analysis
2. 7 Marks
   bSort the following array using heap-sort techniques. $(5, 8, 3, 9, 2, 10, 1, 45, 32)$
   How to answer

   • Build max-heap from given array
   • Show heapify steps
   • Repeatedly extract max to sort
   • Write final sorted array
3. 7 Marks
   aDefine Big "Oh" with example.
   How to answer

   • Define Big-Oh formally with c, n0
   • Explain asymptotic upper bound meaning
   • Give example with function and proof
   • Mention properties / graph
4. 7 Marks
   b

   Construct a Huffman Code for the following data:

   Character	A	B	C	D	E
   Probability	0.4	0.1	0.2	0.15	0.15

   Decode the text whose ending 100010111001010 using above Huffman Code.

   How to answer

   • Sort probabilities and build Huffman tree merging lowest two
   • Assign 0/1 and derive codes for A,B,C,D,E
   • Calculate average code length / check prefix property
   • Decode bit string 100010111001010 using tree
5. 7 Marks
   aDefine how Knapsack Problem is Solved by dynamic programming. Consider $n = 3$ $(w_1, w_2, w_3) = (2, 3, 3)$, $(P_1, P_2, P_3) = (1, 2, 4)$ and $m = 6$. Find optimal solution.
   How to answer

   • State 0/1 knapsack recurrence for dynamic programming
   • Build DP table for n=3, m=6 with given weights and profits
   • Trace back optimal subset selection
   • State optimal profit and selected items
6. 7 Marks
   bDiscuss Job Sequencing problem by an example.
   How to answer

   • Define job sequencing with deadlines and profits
   • Explain greedy sorting by profit and slot allocation
   • Work out example schedule
   • State optimal sequence and profit
7. 7 Marks
   aExplain eight queen's problem and apply back tracking to solve this problem.
   How to answer

   • State 8-queens constraints: row, column, diagonal
   • Explain backtracking search and pruning
   • Show placement steps / solution board
   • Mention complexity
8. 7 Marks
   b

   Solve the TSP using branch and bound technique.

   	A	B	C
   A	$\infty$	3	4
   B	6	$\infty$	4
   C	3	5	$\infty$

   How to answer

   • Write given cost matrix with infinity diagonal
   • Compute reductions and bounds for branch and bound tree
   • Expand least-cost nodes to find tour
   • State optimal TSP tour and cost
9. 7 Marks
   aShow preorder, inorder and postorder for the following tree.

   

   How to answer

   • Identify tree structure with root A
   • Traverse preorder: root-left-right
   • Traverse inorder: left-root-right
   • Traverse postorder: left-right-root
10. 7 Marks
    bDiscuss in detail NP complete problems with example.
    How to answer

    • Define NP, NP-complete with nondeterministic polynomial time
    • Explain reducibility and NP-hard vs NP-complete
    • Give examples like SAT, TSP, clique
    • Mention Cook's theorem significance
11. 7 Marks
    aConstruct B tree of order 5 for the list of elements. $2, 8, 5, 6, 13, 9, 14, 12, 19, 24, 18, 15, 5, 16, 20, 21$
    How to answer

    • State B-tree order 5 properties: max 4 keys, min keys
    • Insert keys sequentially showing splits
    • Show intermediate and final B-tree structure
    • Verify all leaves at same level
12. 7 Marks
    bCompare Bfs and Dfs.
    How to answer

    • Define BFS queue-based and DFS stack/recursion-based
    • Compare order, memory, completeness
    • Compare time complexity and applications
    • Give example traversal difference
13. 7 Marks
    aExplain Prim's algorithm with example.
    How to answer

    • State Prim's greedy minimum spanning tree idea
    • Explain cut property and steps with priority
    • Work out example graph step by step
    • Give complexity O(E log V)
14. 7 Marks
    bSolve the following instances of the single source shortest path problem with vertex 'a' as the source.

    

    How to answer

    • Initialize distances from source a
    • Apply Dijkstra relaxing edges iteratively
    • Show distance table / shortest path tree
    • State shortest distances to b,c,d,e
15. 14 Marks
    Write short notes.

    1. i)Parallel Algorithm
    2. ii)Graph Coloring
    3. iii)Quick Sort
    How to answer

    • Define parallel algorithm with speedup and efficiency
    • Explain graph coloring with chromatic number example
    • Explain quick sort partition and recurrence
    • Mention complexities and applications