DAA previous year question paper 2022 | HNBGU MCA Third semester

DAA

HNBGU MCA Previous Question Paper 2022

    1. Estimate the time complexity using f(n) and g(n) functions in asymptotic notations.

    2. Solve the recurrence relation using substitution method:

      T(n) ={T(1)n=1}
      T(n/b)+ F(n) n>1
      where a=5,b=4 and f(n)= Cn^2
                        
    1. Construct a red black tree by inserting 10, 20, 30, 15, 16 and 27 into and initially empty tree and also delete 15,16 and 30 from the tree.

    2. Write the algorithm for quick sort. Provide a complete analysis of quick sort for the given set of numbers:

      12,33,23,43,44,55,64,77 and 76
    1. Explain how Greedy approach is used in Dijkstra's algorithm for finding the single source shortest path for the given graph:

    2. Discuss the Floyd - Warshall's algorithm using dynamic programming. Trace the algorithm for the given example:

      Diagram to be added.

    1. Show the state space tree for 4 queens problem. Show the steps in solving 4 queens problem using Branch and Bound technique.

    2. Differentiate between Breadth-first search and Depth-First search.

    1. Define NP-hard and NP-complete problems. What are the steps used to show a given problem in NP-complete? Discuss with an example.

    2. Define Travelling Salesman Problem (TSP). Explain the basic steps that are to be followed to solve (TSP) using branch and bound with and sample.

    1. Find the optimal solution for the following fractional Knapsach problem. Given number of items (n) =4, capacity of sack (m) =60, W ={40,10,20,24} and P ={280,100,120,120}.

    2. Given a chain of 4 matrices <A1,A2,A3,A4> with dimensions <5*4>,<4*6>,<6*2>,<2*7> respectively. Using dynamic programming, find the minimum number of scalar multiplications needed and also write the optimal multiplication order.

  1. Write short notes on the following :

    1. Amortized Analysis
    2. Fibonacci Heap
    3. Max. Heapify