AL-402 Analysis and Design of Algorithm - Jun 2024 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
   aDefine Time Complexity. Describe different notations used to represent these complexities.
   How to answer

   • Define time complexity as time taken as function of input size n
   • Need for asymptotic analysis, worst/average/best case
   • Define Big-O, Omega, Theta, Little-o, Little-omega with definitions
   • Give examples and graphs of notations
2. 7 Marks
   bWrite an algorithm for Strassen's matrix multiplication and analyze the complexity of algorithm.
   How to answer

   • State divide and conquer principle for matrix multiplication
   • Write Strassen's 7 multiplications M1-M7 and combination steps
   • Give pseudocode/algorithm steps
   • Analyze recurrence T(n)=7T(n/2)+O(n^2) to O(n^log2 7)
   • Compare with naive O(n^3)
3. 7 Marks
   aShow that the average case time complexity of quick sort is O(nlogn).
   How to answer

   • Set up quicksort partition and recurrence T(n)=T(k)+T(n-k-1)+O(n)
   • Take expectation over random pivot positions
   • Solve average-case recurrence using harmonic numbers / substitution
   • Conclude T_avg(n)=O(n log n)
4. 7 Marks
   bDescribe in detail job sequencing with deadlines problem. Let n = 4, $(P_1, P_2, P_3, P_4) = (100, 10, 15, 27)$ and $(d_1, d_2, d_3, d_4) = (2, 1, 2, 1)$ find the optimal solution for the given values.
   How to answer

   • Define job sequencing with deadlines objective to maximize profit
   • Describe greedy algorithm sorting by profit and slot allocation
   • Apply to n=4, P=(100,10,15,27), d=(2,1,2,1)
   • Find feasible sequence and maximum profit as optimal solution
5. 7 Marks
   aWrite an algorithm for single source shortest path and apply it for the following graph.

   

   How to answer

   • Write single source shortest path algorithm - Dijkstra's algorithm steps
   • Describe initialization, relaxation, priority queue
   • Apply step-by-step to given graph with 6 nodes A-F
   • Show distance table and final shortest paths
6. 7 Marks
   bDiscuss the importance of proving both the greedy choice property and the optimal substructure property for establishing the correctness of a greedy algorithm.
   How to answer

   • Define greedy choice property and optimal substructure
   • Explain why greedy choice ensures safe first choice
   • Explain why optimal substructure allows combining with subproblem optimum
   • Relate to proof of correctness by cut-and-paste / induction
7. 7 Marks
   aExplain Floyd Warshall algorithm problem with the graph given in figure.

   

   How to answer

   • State Floyd-Warshall all-pairs shortest path DP formulation
   • Give algorithm with triple loop and D(k) recurrence
   • Initialize distance matrix from given 9-node graph 0-8
   • Show iterations and final shortest distances
8. 7 Marks
   bWrite an algorithm to solve Knapsack problem using Greedy technique. Find the optimal solution to the Knapsack instance n = 7, m = 15 $(P_1, P_2, P_3 ... P_7) = (10, 5, 15, 7, 6, 18, 3)$ $(W_1, W_2, W_3 ... W_7) = (2, 3, 5, 7, 1, 4, 1)$
   How to answer

   • Write greedy knapsack algorithm using profit/weight ratio
   • Compute ratios and sort items in descending order
   • Fill capacity m=15 fractionally and compute profit
   • State optimal solution vector and max profit
9. 7 Marks
   aDescribe how dynamic programming can be used to solve reliability design problems.
   How to answer

   • Define reliability design problem and redundancy
   • Formulate DP recurrence for maximizing reliability under cost constraint
   • Explain stages, states and backward/forward recursion
   • Illustrate with example steps
10. 7 Marks
    bDescribe graph coloring problem and write an algorithm for m-coloring problem.
    How to answer

    • Define graph coloring and chromatic number
    • State m-coloring decision problem
    • Write backtracking algorithm for m-coloring with promising function
    • Give complexity and example
11. 7 Marks
    aExplain the 4-queen problem using backtracking algorithm.
    How to answer

    • State 4-queen placement constraints - row, column, diagonal
    • Explain backtracking search tree construction
    • Show step-by-step placements and backtrack on conflict
    • Give final solutions for 4x4 board
12. 7 Marks
    bExplain the method of reduction to solve travelling sales person problem using branch and bound.
    How to answer

    • Define TSP and branch and bound lower bound concept
    • Explain matrix reduction - row and column reduction
    • Describe state space tree expansion with cost calculation
    • Show how optimal tour is obtained
13. 7 Marks
    aCompare and contrast NP-Hard and NP-Complete classes
    How to answer

    • Define NP-Hard and NP-Complete with examples
    • Compare on basis of reducibility, verifiability, membership in NP
    • Give table of differences
    • Mention examples like SAT, TSP, Halting problem
14. 7 Marks
    bWhat are B-trees? How are they created? Explain with a suitable example.
    How to answer

    • Define B-tree properties - order, keys, balance
    • Explain creation/insertion with node split steps
    • Give suitable example with m=... insertion sequence
    • Mention search/delete and applications
15. 14 Marks
    Write short notes on any two of the following.

    1. a)Data Stream Algorithms
    2. b)Approximations Algorithms
    3. c)Data Transfer Optimization
    4. d)Huffman coding
    How to answer

    • Select any two topics from four options
    • Give definition, need and key concepts for each
    • Explain algorithm/steps with example
    • Mention applications and advantages