Reg No-: Name: ‏ہے‎

APA ABDUL ೬1521711121. UNIVERSITY

Third Semester MCA (2 Year) Degree Examination December 2021

Course Code; 20110/4203
Course Name: DESIGN & ANALYSIS OF ALGORITHMS
Max. Marks: 60 Duration: 3 Hours
PART A
Answer all questions, cach carries ‏ل‎ marks. Marks
‏کے‎ Differentiate space and time complexity. (3)
7 Solve the following recurrence equation using iteration method. (3)
ஙா (४2)+ छ
ച്‌ Define the control abstraction of Greedy strategy. (3)
4 Explain the pseudocode of Bellman ford algorithm for finding the single shortest (3)
path,
PA Describe the working of Backtracking problem with a suitable example (3)
6 Write a comparison-based sorting algorithm used by lower bound theory (3)
technique
ത്‌ Explain Clique problem with an example. (3)
7 ‏و‎ Explain the Bipartite matching problem with an cxample. (3)
| ಟ್‌ Describe approximation ratio in approximation algorithm. (3)
‏"ظز‎ What are the two different types of Randomized algorithms? (3)
PART B
Answer any one question from each module, Each question carries 6 marks.
|| Describe different Asymptotic ರ aa for expressing time complexity of (6)
algorithms.
OR
At Explain the Merge sort algorithm and give its worst-case analysis (6)
Module 11
ತಿ Explain the different steps used to find the minimum cost spanning tree for the (6)
below graph using Prim’s algorithm

Page Lof2