Tribhuvan University
Bachelor of Science in Computer Science and Information Technology
Semester 5 · TU Board 2076
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
What do you mean by the complexity of an algorithm? Explain the asymptotic notations used to describe the time/space complexity of any algorithm with their geometrical interpretation and example.
Answer comingAlso asked in Model question
- 2.10
Explain the divide and conquer paradigm from algorithm design with a suitable example. Write the Quick sort algorithm using a randomized approach and explain its time complexity.
Answer comingAlso asked in 2078
- 3.10
Explain in brief the Backtracking approach for algorithm design. How it differs with recursion? Explain the N-Queen problem and algorithm using backtracking and analyze its time complexity.
Group B
Attempt any EIGHT questions(8 × 5 = 40)
- 4.5
Write the algorithm for selection sort and explain its time and space complexity.
Answer comingAlso asked in 2080, 2078, Model question
- 5.5
Solve the following recurrence relation using the master method.
- T(n) = 7 T(n/2) + n^2
- T(n) = 4 T(n/4) + kn
Answer comingAlso asked in 2082, 2081, 2079, 2078
- 6.5
Explain the greedy algorithm for the fractional knapsack problem with its time complexity.
- 7.5
Trace heap sort algorithm for the following data:
{2, 9, 3, 12, 15, 8, 11}
Answer comingAlso asked in Model question
- 8.5
What do you mean by Dynamic programming strategy? Explain the element of DP.
- 9.5
Explain the approximation for solving vertex cover with a suitable example.
- 10.5
Explain Prism's algorithm for MST problem and analyze its time complexity.
- 11.5
Explain in brief about the classes P, NP, and NP complete with examples.
Answer comingAlso asked in 2078, Model question
- 12.5
Write short notes on
- Backtracking strategy
- Tractable and Intractable Problem
— The End —