Download JNTUH (Jawaharlal nehru technological university) MCA (Master of Computer Applications) 2nd Sem (Second Semester) Regulation-R17 2019 December 842AA Data Structures And Algorithms Previous Question Paper
R17
Code No: 842AA
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
MCA II Semester Examinations, December - 2019
DATA STRUCTURES AND ALGORITHMS
Time: 3hrs
Max.Marks:75
Note: This question paper contains two parts A and B.
Part A is compulsory which carries 25 marks. Answer all questions in Part A. Part B
S 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 ? 5 Marks = 25
1.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]
PART - B
5 ? 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]
OR
3.a)
Show that the bestcase running time of Quicksort on a sequence of size n with distinct
elements is 0(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]
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
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?
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, Z, C, Y, B, J, M, E}
[5+5]
OR
11.
Elucidate Brute Force pattern matching algorithm with an example.
[10]
---ooOoo---
This post was last modified on 17 March 2023