### Exam Year

Tribhuvan University

Institute of Science and Technology

2080

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 is recurrence relation? How it can be solved? Show that time complexity of the recurrence relation T(n) = 2T(n/2) + 1 is O(n) using substitution method.

2

Write down the advantages of dynamic programming over greedy strategy. Find optimal bracketing to multiply 4 matrices of order 2,3,4,2,5.

3

Discuss heapify operation with example. Write down its algorithm and analyze its time and space complexity.

Section B

Attempt any eight questions

4

Define RAM model. Write down iterative algorithm for finding factorial and provide its detailed analysis.

5

Write down algorithm of insertion sort and analyze its time and space complexity.

6

Write down minmax algorithm and analyze its complexity.

7

When greedy strategy provides optimal solution? Write down job sequencing with deadlines algorithm and analyze its complexity.

8

Suppose that a message contains alphabet frequencies as given below and find Huffman codes for each alphabet

 Symbol Frequency a 30 b 20 c 25 d 15 e 35
9

Does backtracking give multiple solution? Trace subset sum algorithm for the set {3,5,2,4,1} andd sum=8.

10

Why extended euclidean algorithm is used? Write down its algorithm and analyze its complexity.

11

Define NP-complete problems with examples. Give brief proof of the statement “SAT is NP-complete”.

12

Write short notes on

a) Aggregate Analysis

b) Selection problems