Design and Analysis of Algorithms
This course introduces basic elements of the design and analysis of computer algorithms. Topics include asymptotic notations and analysis, divide and conquer strategy, greedy methods, dynamic programming, basic graph algorithms, NP-completeness, and approximation algorithms. For each topic, beside in-depth coverage, one or more representative problems and their algorithms shall be discussed.
Tribhuvan University
Institute of Science and Technology
Daa Model Qn
Bachelor Level / fifth-semester / Science
Computer Science and Information Technology( CSC314 )
Design and Analysis of Algorithms
Full Marks: 60 + 20 + 20
Pass Marks: 24 + 8 + 8
Time: 3 Hours
Candidates are required to give their answers in their own words as far as practicable.
The figures in the margin indicate full marks.
SECTION A
Attempt any TWO question.
Write down the elements of dynamic programming. Give the recursive defination of LCS problem. Find LCS between sequences S1 = “Dinesh”, S2 = “Dikshya”.
What is heap? Sort the following data items by using heap sort A[] = {3, 5, 2, 66, 4, 11, 9, 34}.
Given a set S ={6, 4, 5, 6, 9} and X=11. Obtain the subset sum using backtracking approach.
SECTION B
Attempt any EIGHT question.
Write down algorithm of insertion sort and analyze its time and space complexity.
Define binary search algorithm. Write down the recursive algorithm for binary search algorithm and analyse it.
Explain the asymptotic notations used to describe the time/space complexity of any algorithm.
What is the purpose of Euclid’s algorithm? Explain with suitable explain.
Solve the recurrence relation T(n) = T(n-1) + 1 when T(0) = 0.
Define greedy algorithm. Find minimum spanning tree of the following graph by using Kruskal algorithm.
Explain in brief about the classes P, NP, and NP complete with examples.
Find the optimal parenthesization for the matrix chain product ABCD with size of each is given as A5×10 , B10×15 , C15×20 , D20×30
Write short notes on:
a) Best, Worst and average case complexity
b) Backtracking strategy