Questions
Syllabus
Qns. By Syllabus

Semester

Subject

Year

Tribhuwan University

Institute of Science and Technology

2076

Bachelor Level / Third Year / Fifth Semester / Science

B.Sc in Computer Science and Information Technology (CSC325)

(Design and Analysis of Algorithms)

Full Marks: 60

Pass Marks: 24

Time: 3 Hours

Candidates are required to give their answers in their own words as for as practicable.

The figures in the margin indicate full marks.

Section A

Long Answers Questions

Attempt any TWO questions.
[2*10=20]
1.
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.[10]
2.
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.[10]
3.
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.[10]
Section B

Short Answers Questions

Attempt any Eight questions.
[8*5=40]
4.
Solve the following recurrence relation using the master method. a. $T(n) = 7 T(n/2) + n^2$ b. $T(n) = 4 T(n/4) + kn$ [5]
5.
Explain the greedy algorithm for the fractional knapsack problem with its time complexity. [5]
6.
What do you mean by Dynamic programming strategy? Explain the element of DP. [5]
7.
Explain the approximation for solving vertex cover with a suitable example. [5]
8.
Explain Prim’s algorithm for MST problem and analyze its time complexity. [5]
9.
Write short notes on: a. Backtracking strategy b. Tractable and Intractable Problem [5]
10.
Write the algorithm for selection sort and explain its time and space complexity. [5]
11.
Trace heap sort algorithm for the following data: (2, 9, 3, 12, 15, 8, 11) [5]
12.
Explain in brief about the classes P, NP, and NP complete with examples. [5]