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 Breadth-first search and Depth-First
search.
-
-
Define NP-hard and NP-complete problems. What are the steps
used to show a given problem in NP-complete? 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
