Questions
Syllabus
Qns. By Syllabus

Semester

Subject

Year

Tribhuwan University

Institute of Science and Technology

2078

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 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.[10]
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.[10]
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.[10]
Section B

Short Answers Questions

Attempt any Eight questions.
[8*5=40]
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]
5.
What do you mean by optimization problem? Explain the greedy strategy for algorithm design to solve optimization problems. [5]
6.
Explain the algorithm and its complexity for solving job sequencing with deadline problem using greedy strategy. [5]
7.
What do you mean by memorization strategy? Compare memorization with dynamic programming. [5]
8.
Explain the concept of backtracking. How it differ with recursion? [5]
9.
Write an algorithm to find the maximum element of an array and analyze its time complexity. [5]
10.
Write the algorithm for bubble sort and explain its time complexity. [5]
11.
Explain in brief about the complexity classes P, NP and NP Complete. [5]
12.
Write short notes on: a. NP Hard Problems and NP Completeness b. Problem Reduction [5]