Download AKTU B-Tech 5th Sem 2015-2016 Design And Analysis Of Algorithms Ecs 502 Question Paper

Firstranker's choice

FirstRanker.com

Printed Pages: 677

--- Content provided by FirstRanker.com ---

ECS-502

(Following Paper ID and Roll No. to be filled in your Answer Book)

Paper ID :110512 Roll No.

B.Tech.

(SEM. V) THEORY EXAM. 2015-16

--- Content provided by FirstRanker.com ---

DESIGN AND ANALYSIS OF ALGORITHMS

[Time: 3 hours] [Maximum Marks: 100]

Section-A

1. Attempt all parts. All parts carry equal marks. Write answer of each part in short. (10x2=20)
   1. Why should we do asymptotic analysis of algorithms? Explain.
   2. Order the following expressions by their asymptotic growth and justify your answer 2ⁿ, n!, (log n)!, n³, 2^log₂n, 2²ⁿ, n^{log log n}, eⁿ
   3. How can you modify Quick sort algorithm to search an item in a list?

   --- Content provided by FirstRanker.com ---

   4. What are all pairs shortest path?
   5. Define Convex Hull.
   6. Discuss various properties of Binomial Tree
   7. What are the steps to design an algorithm?
   8. Prove that red-black tree with n internal nodes has height at most 2log₂(n+1)

   --- Content provided by FirstRanker.com ---

   9. Prove that the maximum degree of n-node in a binomial tree is log₂n.
   10. What do you understand by ‘stable' sort? Name two stable sort algorithms.
   11. Define Greedy Approach.

Section-B

Attempt any five questions from this section. (5x10=50)

--- Content provided by FirstRanker.com ---

2. Explain insertion in Red Black Tree. Show steps for inserting 9,8,7,6,5,4,3,2, & 1 into empty RB tree.
3. Show all the steps of Strassen's matrix Multiplication algorithm to multiply the following matrices X = $\left[\begin{array}{cc}1& 5\\ 4& 8\end{array}\right]$ and Y = $\left[\begin{array}{cc}9& 6\\ 9& 8\end{array}\right]$
4. Define Dynamic programming. How Dynamic Programming approach is used to find the shortest path? Illustrate with an example.
5. Find optimal solution to the Fractional Knapsack instances n= 7 and Knapsack capacity M = 15 Where profits and weights are as follows (p₁, p₂, ......p₇) = (10,5,15,7,6,18,3) & (w₁, w₂......w₇) = (2,3,5,7,1,4,1) respectively
6. Construct the string- matching automaton for the pattern P=aabab and illustrate its operation on the text string T=aaababaabaabaab.

--- Content provided by FirstRanker.com ---

7. Illustrate the operation of heap sort on the array A=(6,1,2,4,3,5,7,9,8,0)
8. Find an LCS for the sequences. X={x₁, x₂ ......X_m} and Y={y₁,y₂.....y_n}. Also show that it requires O (m+n) time.
9. Write short note on Fast Fourier Transform (FFT).

Section-C

Attempt any two questions from this section. (2x15=30)

10. Attempt both :
    1. Why the statement "The running time of algorithm A is at least O (n²) is meaningless"? Explain.

    --- Content provided by FirstRanker.com ---

    2. What is the procedure of partition (A, p, r) in Quick Sort and also define the complexity of Quick Sort.
11. What do you mean by Branch & Bound? How TSP can be solve using this approach.
12. Attempt both :
    1. Discuss the relationship between the class P, NP, NP- complete and NP- hard with suitable example of each class.
    2. Define Approximation algorithms. What is Approximation ratio? Give an Approximation algorithm for the Travelling Salesman

    --- Content provided by FirstRanker.com ---