### Exam Year

Tribhuvan University

Institute of Science and Technology

2076

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 questions

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.

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.

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.

Section B

Attempt any EIGHT questions

4

Write the algorithm for selection sort and explain its time and space complexity.

5

Solve the following recurrence relation using the master method.

1. T(n) = 7 T(n) + n2
2. T(n) = 4 T(n/4) + kn
6

Explain the greedy algorithm for the fractional knapsack problem with its time complexity.

7

Trace heap sort algorithm for the following data:

{2, 9, 3, 12, 15, 8, 11}

8

What do you mean by Dynamic programming strategy? Explain the element of DP.

9

Explain the approximation for solving vertex cover with a suitable example.

10

Explain Prism’s algorithm for MST problem and analyze its time complexity.

11

Explain in brief about the classes P, NP, and NP complete with examples.

12

Write short notes on

1. Backtracking strategy
2. Tractable and Intractable Problem