STUPIDSID
1(a)
Show that solution of \[\T(n)=T\left ( \left \lfloor \dfrac{n}{2} \right \rfloor \right )+1 \, is \,O(log \,n).\]
2 M
1(b)
What are the factors which affect the running time of an algorithm?
2 M
1(c)
Illustrate Heap sort on the array:
A=[5, 8, 3, 9, 2, 10, 1, 40]
A=[5, 8, 3, 9, 2, 10, 1, 40]
3 M
Solve any one question from Q.1(d) & Q.1(e)
1(d)
Sort the following list using quick sort technique and argue upon its running time
A=[5, 7, 9, 4, 10, 2, 8, 1]
A=[5, 7, 9, 4, 10, 2, 8, 1]
7 M
1(e)
Show how the following matrices would be multiplied using Strassen's algorithm.
7 M
2(a)
Explain the concept behind Greedy strategy.
2 M
2(b)
Write the basic difference between Prim's algorithm and Kruskal's algorithm.
2 M
2(c)
Consider n=7, m=15.(p1, p2,&dots;p7=(10, 5, 15, 7, 6, 18, 3) and (w1,w2,&dots;w7)=(2, 3, 5, 7, 1, 4, 1). Obtain the optimal solution for this knapsack instanace.
3 M
Solve any one question from Q.2(d) & Q.2(e)
2(d)
Find an optimal merge pattern for 11 files whose length are 28, 32, 12, 5, 84, 5, 3, 9, 35, 3, , 11. Write and explain the algorithn used and determine its complexity.
7 M
2(e)
Write Djikstra's algorithm to find the shortest path between two given vertices. Using this algorithm find shortest path from vertex 1 to vertex 3 in the following weighted graph.
7 M
3(a)
What is principle of optimality? Explain with suitable example.
2 M
3(b)
Write short note on dynamic programming.
2 M
3(c)
Explain how a reliability design can be obtained using dynamic programming.
3 M
Solve any one question from Q.3(d) & Q.3(e)
3(d)
Find minimum cost path from 'S' to 't' in mutistage graph using dynamic programming?
7 M
3(e)
Define how knapsack problem is solved using dynamic programming approach.
Consider
n=3,(w1, w2, w3)=(2, 3, 3) and (p1,p2,p3)=(1, 2, 4)
m=6. Find optimal solution for given data.
Consider
n=3,(w1, w2, w3)=(2, 3, 3) and (p1,p2,p3)=(1, 2, 4)
m=6. Find optimal solution for given data.
7 M
4(a)
Write a Pseudo algorithm for graph coloring problem.
2 M
4(b)
Explain the term lower bound with suitable example.
2 M
4(c)
What is Hamiltonian cycle? Explain how it can be solved using backtracking algorithm.
3 M
4(d)
Consider the following travelling salesman on instance defined by cost matrix.\[\\begin{bmatrix}
\infty & 7& 3& 12& 8\\
3& \infty& 6& 14& 9\\
5& 8& \infty& 6& 18\\
9& 3& 5& \infty& 11\\
18& 14& 9& 8&\infty
\end{bmatrix}\]
obtain reduced cost matrix and solve it.
obtain reduced cost matrix and solve it.
7 M
4(e)
Solve 8-queen's problem for a feasible sequence(6, 4, 7, 1)
7 M
5(a)
Explain the function for deletion of a node from binary search tree.
2 M
5(b)
Explain 2-3 trees with the help of suitable example.
2 M
5(c)
What is BFS and DFS? Explain with suitabke example with respect to tree.
3 M
5(d)
Insert the elements in the order shown below to build into an AVL tree. Also determine the complexity of this procedure 1, 26, 2, 25, 3, 24, 4, 23, 5, 22, 6.
7 M
5(e)
Discuss the relationship between class P, NP, NP complete and NP hard problems with example of each class.
7 M
More question papers from Analysis & Design of Algorithm