Tribhuvan University

Institute of Science and Technology


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.


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.


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


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

Section B

Attempt any eight questions


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


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


Write down minmax algorithm and analyze its complexity.


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


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

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


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


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


Write short notes on

a) Aggregate Analysis

b) Selection problems