26/11/2015
MODEL PAPER :
Rajasthan Institute of Engineering & Technology, Jaipur
University Roll No. ______________
IIIrd Year MCA. Vth Semester Model Paper, December – 2015
Subject: -Analysis and Design of Algorithms (MCA-502)
Time: -3 Hrs. [Maximum Marks: -80]
[Min. Passing Marks: 32]
Instructions to Candidates: -
Attempt all questions. Marks of questions are indicated against each section.
Q. 1 Answer following question in 1-2 lines. (10x1=10)
i) What do you mean by Space Complexity?
ii) Write the complexity of merge sort algorithm?
iii) What do you mean sum of subsets?
iv) What is Graph coloring?
v) What do you Branch & Bound techniques?
vi) Define Backtracking?
vii) What is greedy method?
viii)What do you mean PRAM?
ix) What do you mean Time Complexity?
x) Define an Asymptotic Notation?
Q.2 Answer the following questions in 50 words each. (5x3=15)
i) Explain the 4-queen problem with example?
ii) Write a Prim’s algorithm in minimum spanning tree?
iii) Explain the concept of optimal binary search tree?
iv) Explain the backtracking method?
v) Explain the flow shop scheduling?
Q. 3 Answer the following questions in 150 words. (5x4=20)
I) Define DFS algorithms?
ii) Describe 0-1 Knapsack problem algorithm using dynamic programming method?
iii) Difference between Divide and Conquer method and Greedy method?
iv) Sort the following sequence using radix sort method.
element : 203,105,44,352,129,302,400,509
v) Explain the parallel evaluation of general arithmetic expressions with example.
Q.4 a) Explain Dijkastra’s algorithm by giving a suitable example?
b) Explain the algorithm for finding all Hamiltonian cycles using backtracking? (2x 10= 20)
Q. 4 a) Answer the following questions in 250 words. (15x1=15)
I) Explain the 8-queen problem using backtracking method with each step?
OR
Explain travelling sales person problem with example?
