Tribhuvan University
Bachelor of Science in Computer Science and Information Technology
Semester 5 · Model question
Course Title: Design and Analysis of Algorithms (CSC314)
Full Marks: 60Pass Marks: 24Time: 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.
Group A
Attempt any TWO question.(2 × 10 = 20)
- 1.10
Write down the elements of dynamic programming. Give the recursive defination of LCS problem. Find LCS between sequences S1 = "Dinesh", S2 = "Dikshya".
- 2.10
What is heap? Sort the following data items by using heap sort A[] = {3, 5, 2, 66, 4, 11, 9, 34}.
Answer comingAlso asked in 2076
- 3.10
Given a set S ={6, 4, 5, 6, 9} and X=11. Obtain the subset sum using backtracking approach.
Answer comingAlso asked in 2081
Group B
Attempt any EIGHT question.(8 × 5 = 40)
- 4.5
Write down algorithm of insertion sort and analyze its time and space complexity.
Answer comingAlso asked in 2080, 2078, 2076
- 5.5
Define binary search algorithm. Write down the recursive algorithm for binary search algorithm and analyse it.
- 6.5
Explain the asymptotic notations used to describe the time/space complexity of any algorithm.
Answer comingAlso asked in 2076
- 7.5
What is the purpose of Euclid's algorithm? Explain with suitable explain.
- 8.5
Solve the recurrence relation T(n) = T(n-1) + 1 when T(0) = 0.
- 9.5
Define greedy algorithm. Find minimum spanning tree of the following graph by using Kruskal algorithm.
[figure in the original paper]
Answer comingAlso asked in 2079
- 10.5
Explain in brief about the classes P, NP, and NP complete with examples.
Answer comingAlso asked in 2078, 2076
- 11.5
Find the optimal parenthesization for the matrix chain product ABCD with size of each is given as A_5×10 , B_10×15 , C_15×20 , D_20×30
Answer comingAlso asked in 2079
- 12.5
Write short notes on:
a) Best, Worst and average case complexity- b) Backtracking strategy
Answer comingAlso asked in 2079
— The End —