Download JNTUH MCA 2nd Sem R17 2019 December 842AA Data Structures And Algorithms Question Paper

FirstRanker.com
Firstranker's choice
Code No: 842AA

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

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
MCA 1I Semester Examinations, December - 2019
DATA STRUCTURES AND ALGORITHMS
Time: 3hrs Max.Marks:75

Note: This question paper contains two parts A and B.

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

PART - A 5 x 5 Marks =25

1. a) How can we measure an algorithm’s running time? [5]
2. b) Discuss minimum cost spanning tree. [5]
3. c) State the Travelling sales person problem. [5]

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

4. d) What is the purpose of a Hash function in Hashing? [5]
5. e) Give the properties of red black tree. [5]

PART -B 5 x 10 Marks =50

2. a) Solve the recurrence: T(n)=4T(n/2)+n, Where n >1 and is a power of 2.
   b) Write an algorithm for the finding the GCD of two numbers and also find the time complexity of the same. [5+5]
   

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

   OR
3. a) Show that the bestcase running time of Quicksort on a sequence of size n with distinct elements is O(nlogn).
   b) Explain the strassen’s matrix multiplication. [5+5]

4. a) Describe UNION and FIND algorithms.
   b) What is the solution generated by using job sequencing with deadlines when n=7, (P1, P2,P3 ....P7)=(3,5,20, 18, 1,6,30), and (d1, d2,.....d7 ) =(1, 3,4, 3,2, 1,2). [5+5]
   

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

   OR
5. Explain an algorithm for generating minimum cost Spanning tree and list some applications of it. [10]

6. a) Discuss the general method for the dynamic programming.
   b) How the reliability of the system can be increased? [5+5]
   OR

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

7. a) Write an algorithm of m-coloring problem.
   b) Solve the 4-queens problem using backtracking. [5+5]

8. Create the heap to sort the following list of numbers. 5, 18, 20, 9, 4, 15, 10, 30, 8, 45, 2, 22,55,63,14,72,17. [10]
   OR
9. a) What are the major advantages of extendible hashing over other hashing techniques?
   

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

   b) Write a function double hash to resolve collisions using double hashing. [5+5]

10. a) How a node can be deleted from the binary search tree? Explain the methods.
    b) Construct the B-tree of order 4 for the following list of elements {K, L, T, A, G, H, P, W,R,U,ZC,Y,B,I,M,E} [5+5]
    OR
11. Elucidate Brute Force pattern matching with an example. [10]

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