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 is compulsory which carries 25 marks. Answer all questions in Part A. Part B consists of 5 Units. Answer any one full question from each unit. Each question carries 10 marks and may have a, b, c as sub questions.PART - A 5 x 5 Marks =25
- a) How can we measure an algorithm’s running time? [5]
- b) Discuss minimum cost spanning tree. [5]
- c) State the Travelling sales person problem. [5]
- d) What is the purpose of a Hash function in Hashing? [5]
- e) Give the properties of red black tree. [5]
--- Content provided by FirstRanker.com ---
PART -B 5 x 10 Marks =50
- 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 - 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]
- 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 - Explain an algorithm for generating minimum cost Spanning tree and list some applications of it. [10]
- a) Discuss the general method for the dynamic programming.
b) How the reliability of the system can be increased? [5+5]
OR - a) Write an algorithm of m-coloring problem.
b) Solve the 4-queens problem using backtracking. [5+5]
--- Content provided by FirstRanker.com ---
- 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 - 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]
- 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 - Elucidate Brute Force pattern matching with an example. [10]
--- Content provided by FirstRanker.com ---
This download link is referred from the post: JNTUH MCA 2nd Sem Last 10 Years 2023-2013 Question Papers R20-R09 || Jawaharlal nehru technological university
--- Content provided by FirstRanker.com ---