DAA
HNBGU MCA Previous Question Paper 2022


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

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


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.

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


Explain how Greedy approach is used in Dijkstra's algorithm
for finding the single source shortest path for the given
graph:

Discuss the Floyd  Warshall's algorithm using dynamic
programming. Trace the algorithm for the given example:
Diagram
to be added.


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

Differentiate between Breadthfirst search and DepthFirst
search.


Define NPhard and NPcomplete problems. What are the steps
used to show a given problem in NPcomplete? Discuss with an
example.

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


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}.

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.

Write short notes on the following :
 Amortized Analysis
 Fibonacci Heap
 Max. Heapify