Tribhuvan University
Bachelor of Science in Computer Science and Information Technology
Semester 5 · TU Board 2079
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 questions.(2 × 10 = 20)
- 1.10
Explain the divide and conquer strategy for problem solving. Describe the worst-case linear time selection algorithm and analyze its complexity.
- 2.10
Write the dynamic programming algorithm for matrix chain multiplication. 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 Model question
- 3.10
What do you mean by Backtracking? Explain the backtracking algorithm for solving 0-1
knapsack problem and find the solution for the problem given below:[figure in the original paper]
Group B
Attempt any EIGHT questions(8 × 5 = 40)
- 4.5
Explain the iterative algorithm to find the GCD of given two numbers and analyze its complexity.
- 5.5
Generate the prefix code for the string " CYBER CRIME" using Huffman algorithm and find the total number of bits required.
- 6.5
Define tractable and intractable problem. Illustrate vertex cover problem with an example.
- 7.5
Find the edit distance between the string " ARTIFICIAL" and "NATURAL" Using dynamic programming.
- 8.5
Write short notes on:
a) Best, Worst and average case complexity- b) Greedy Strategy
Answer comingAlso asked in Model question
- 9.5
Solve the following recurrence relations using masters method
- a) T(n) = 2T(n/4) + kn^2, n > 1
=1 , n=1
- b) T(n) = 5T(n/4) + kn , n > 1
=1 , n=1
Answer comingAlso asked in 2082, 2081, 2078, 2076
- 10.5
Solve the following linear congrvences using Chinese Remainder Theorem.
X=l (MOD 2)
X=3 (MOD 5)
x=6 (MOD 7)Answer comingAlso asked in 2081
- 11.5
Find the MST from following graph using Kruskal's algorithm.
[figure in the original paper]
Answer comingAlso asked in Model question
- 12.5
Trace the quick sort algorithm for sorting the array A[ ]={15,7,6,23, 18,34,25} and write it's best and worst complexity.
— The End —