CY-502 Design And Analysis of Algorithms - Nov 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
   aDefine Time Complexity. Describe different notations used to represent these complexities.
   How to answer

   • Define time complexity as function of input size
   • Explain Big-O, Omega, Theta notations with definitions
   • Give examples and graphical interpretation
   • Mention best, average, worst case
2. 7 Marks
   bExplain how divide and conquer method is used to implement Merge sort technique with its Time complexity?
   How to answer

   • Explain divide and conquer principle - divide, conquer, combine
   • Give merge sort algorithm steps
   • Derive recurrence T(n)=2T(n/2)+O(n)
   • State time complexity O(n log n) with example
3. 7 Marks
   aDescribe 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 problem and greedy approach
   • Explain sorting by profit and slot allocation rule
   • Apply to n=4, P=(100,10,15,27), d=(2,1,2,1)
   • Give optimal sequence and maximum profit
4. 7 Marks
   bCompute the optimal solution for knapsack problem using greedy method $N = 3$, $M = 20$, $(p_1, p_2, p_3) = (25, 24, 15)$, $(w_1, w_2, w_3) = (18, 15, 10)$.
   How to answer

   • State fractional knapsack greedy criterion profit/weight
   • Compute ratios and sort objects
   • Fill capacity M=20 fractionally
   • Compute maximum profit and solution vector
5. 7 Marks
   aWhat is multistage graph problem? Discuss its solution based on dynamic programming approach. Also give a suitable algorithm and find its computing time.
   How to answer

   • Define multistage graph and stages
   • Give dynamic programming forward/backward recurrence
   • Write multistage graph algorithm
   • Analyze computing time O(|V|+|E|)
6. 7 Marks
   bExplain Floyd Warshall algorithm problem with the graph given in figure.

   

   How to answer

   • State Floyd-Warshall all-pairs shortest path idea
   • Give recurrence D(k)[i][j] = min(D(k-1)[i][j], D(k-1)[i][k]+D(k-1)[k][j])
   • Apply iterations to given 6-node graph
   • Obtain final shortest distance matrix
7. 7 Marks
   aDescribe 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 m-coloring algorithm
   • Mention complexity and example
8. 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 principle
   • Explain reduction of cost matrix and bound calculation
   • Describe state space tree search steps
   • Mention how optimal tour is obtained
9. 7 Marks
   aCompare and contrast NP-Hard and NP-Complete classes.
   How to answer

   • Define NP-Hard and NP-Complete with reducibility
   • Compare on definition, examples, solvability
   • Explain P, NP, NP-Hard, NP-Complete relationship
   • Give examples like SAT, TSP, Knapsack
10. 7 Marks
    bWhat are B-trees? How are they created? Give its advantages.
    How to answer

    • Define B-tree and its order properties
    • Explain creation/insertion with node splitting
    • Give search procedure
    • List advantages for disk access and databases
11. 7 Marks
    aDefine algorithm. Write about algorithm design techniques.
    How to answer

    • Define algorithm with characteristics
    • List design techniques: divide and conquer, greedy, DP, etc.
    • Briefly explain each technique
    • Give example of each
12. 7 Marks
    bWrite an algorithm for Huffman code. How does it work? Explain with a example.
    How to answer

    • State Huffman coding greedy principle
    • Give steps: frequency, priority queue, tree building
    • Explain encoding/decoding with example
    • Mention optimal prefix code property
13. 7 Marks
    aWhat is dynamic programming? List the features of dynamic programming.
    How to answer

    • Define dynamic programming and principle of optimality
    • List features: overlapping subproblems, memoization, etc.
    • Differentiate from divide and conquer
    • Give examples like knapsack, multistage graph
14. 7 Marks
    bHow lower bound theory is used to solve the algebraic problems? Explain in detail.
    How to answer

    • Define lower bound and its importance
    • Explain techniques: decision trees, adversary argument
    • Apply to algebraic problems like sorting, searching
    • Give Omega(n log n) example for sorting
15. 14 Marks
    Write short notes on any two of the following.

    1. a)Parallel Algorithms
    2. b)Data Stream Algorithms
    3. c)Logic Optimization
    4. d)Optimal merge patterns
    How to answer

    • Select any two topics from given four
    • Give definition and key concepts for each
    • Mention applications and advantages
    • Give example or diagram if relevant