LINCOLN UNIVERSITY COLLEGE
EXAMINATION PAPER
FACULTY: COMPUTER SCIENCE AND MULTIMEDIA
COURSE: MASTER OF COMPUTER SCIENCE
YEAR/ SEMESTER:FIRST YEAR/SEMESTER ONE
MODULE TITLE: DESIGN & ANALYSIS OF ALGORITHM
CODE: MCS 112
TIME ALLOWED:3 HOURS
Instruction to candidates
1. This question paper has THREE (3) Sections.
2. Answer ALL questions in Section A, VSAQ
3. Answer 7 questions out of 9 in Section B, SAQ
4. Answer 2 questions out of 3 in Section C, LAQ
5. No scripts or answer sheets are to be taken out of the Examination Hall.
Do not open this question paper until instructed
(Candidates are required to give their answers in their own words as far as practicable)
SECTION A
Very Short Answer Questions Attempt all questions
7*2=14
1. State how algorithms performance is analyzed.
2. Distinguish between syntax and semantics of programming language.
3. Write down the advantage of divide and conquer paradigm.
4. Compare NP-hard and NP-complete.
5. List any two problems of backtracking algorithm.
6. Prove 5*n²+2*n-3-O(n³).
7. Can greedy always give the optimal solution?
SECTION B
Short Answer Questions
Attempt any seven (7) questions out of nine (9) questions [7×8-56]
1. Write the recursive algorithm for computing Fibonacci numbers and solve its recurrence relation.
2. How do you compute lowest common ancestor using parallel graph
algorithm? Illustrate with an example.
3. How many page faults will occur for the page reference 1, 2, 3, 4, 2, 1, 5, 6, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6 using LRU approach? Assume the number of page frame is 3.
4.For the given set of items and knapsack capacity 5 kg, find the optimal solution for the 0/1 knapsack problem making use of dynamic programming approach.
5. Write recursive program for binary search.
6. Find the max and min elements in the array (23, 67, 8, 90, 45, 43, 33, 22, 6, 78.99, 102, 40, 76, 89) using divide and conquer approach.
7.ind the longest common subsequence between the string PARAMETER and PARIWAR
8. Construct and AVL tree by inserting the following keys in the order given below: 2, 3, 5, 6, 9, 8, 7, 4, 1 following all the rules of AVL..
9.Find the cost for travelling salesman problem starting from node A.
SECTION C
Long Answer Questions
Attempt any two (2) questions out of three (3) questions[2×15=30]
1. Write recursive algorithm for Quick sort and solve its recurrence relation. [7+8]
2. Distinguish between recursion and backtracking. Trace the dynamic algorithm to parenthesize the chain for multiplying the following matrices.[5+10]
A(4, 10), B(10, 3), C(3. 12), D(12, 20), E(20, 7)
3. Given the following graph find the minimum spanning tree using Prim’s and Kruskal’s algorithm. [7.5+ 7.5 ]
****BEST OF LUCK****
