### Exam Year

Tribhuvan University

Institute of Science and Technology

2078

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 Two Question.

1

What are the elementary properties of algorithm? Explain. Why do you need algorithm? Discuss about analysis of the RAM model for analysis of algorithm with suitable example.

2

Explain about the divide and conquer paradigm for algorithm design with suitable example. Write the Quick sort algorithm using randomized approach and explain its time complexity.

3

Explain in brief about the Dynamic Programming Approach for algorithm design. How it differs with recursion? Explain the algorithm for solving the 0/1 Knapsack problem using the dynamic programming approach and explain its complexity.

Section B

Attempt Eight Questions.

4

Explain the recursion tree method for solving the recurrence relation. Solve following recurrence relation using this method.
T(n)=2T(n/2) +1 for n> 1, T(n) =1 for n =1

5

Write an algorithm to find the maximum element of an array and analyze its time complexity.

6

Write the algorithm for bubble sort and explain its time complexity.

7

What do you mean by optimization problem? Explain the greedy strategy for algorithm design to
solve optimization problems.

8

Explain the algorithm and its complexity for solving job sequencing with deadline problem using greedy strategy.

9

What do you mean by memorization strategy? Compare memorization with dynamic programing.

10

Explain the concept of backtracking. How it differ with recursion?

11

Explain in brief about the complexity classes P, NP and NP Complete.

12

Write short notes on:
a. NP Hard Problems and NP Completeness
b. Problem Reduction