B.TECH - Semester 7 design and algorthims Question Paper 2019 (jun)
Practice authentic previous year university questions for better exam preparation.
Sample Questions
- Given $f(n)=n!$. Find $\theta(g(n))$ and the valid range of $n$.
- Solve the recurrence relation : $$ T(n)= \begin{cases}T(n / 2)+T(n / 2)+2 & n>2 \\ 1 & n=2\end{cases} $$
- Differentiate conventional problem solving method with that of recursive approach.
- How will you find the shortest paths between all pairs of nodes in a graph?
- Write an algorithm to represent a graph using adjacency matrix. Find the space complexity.
- (a) Construct a B Tree (4-5) for the following data set $$ 28,48,65,33,53,78,18,83,57,88,93,103,98,73 . $$
- (b) Delete 57, 73, and 48 in the constructed B tree. P.T.O.
- Write an algorithm to delete an element from an AVL Search tree.
- Find the optimal solution to the knapsack instance No.of objects $(n)=7$, Capacity of Knapsack $(m)=20$, Profits $(p 1 \ldots p 7)=(10,5,16,4,7,6,19)$ and Weights $(w 1, \ldots, w 7)=(2,7,5,6,4,4,6)$.
- When can we say that a problem belongs to NP class? Give an example.
- How are bounding functions helpful in obtaining optimal solutions in backtracking method of algorithmic design? Answer any one full questions from each Module.
- (a) Write the algorithm for sorting of the numbers $(56,98,10,33,24,67,0,4,100)$ using insertion sort. Find the time complexity. 10
- (b) Write an algorithm for building a heap. Show the result of inserting $10,12,1,14,6,5,8,15,39$ and 2 , one at a time into an initially empty binary max heap.
- (a) Describe the process of calculating the running time of an algorithm. Give an example.
- (b) Solve the recurrence relation : $$ T(n)=\left\{\begin{array}{cc} 3 T(n / 2)+k n & n>1 \\ 1 & n=1 \end{array}\right. $$
- (a) What are the various operations that can be done in a Red Black Tree? Explain in detail.
- (b) Explain Dijkstra's algorithm and solve the single source shortest path problem with an example.
- Find the minimum cost spanning tree using Kruskals algorithm. Trace the algorithm for the Graph in Fig 2. Fig. 2
- How is Strassen algorithm for matrix multiplication better than standard matrix multiplication? Explain in detail.
- Find the minimum cost tour for the following Travelling Salesman Problem using Least cost Branch and Bound method. $\left(\begin{array}{ccccc}\infty & 11 & 10 & 9 & 6 \\ 8 & \infty & 7 & 3 & 4 \\ 8 & 4 & \infty & 4 & 8 \\ 11 & 10 & 5 & \infty & 5 \\...