Questions
Syllabus
Qns. By Syllabus

Semester

Subject

Year

Tribhuwan University

Institute of Science and Technology

2080

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 is recurrence relation? How it can be solved? Show that time complexity of the recurrence relation T(n)=2T(n/2)+1T(n) = 2T(n/2) + 1 is O(n)O(n) using substitution method. [10]
2.
Write down the advantages of dynamic programming over greedy strategy. Find optimal bracketing to multiply 4 matrices of order 2,3,4,2,52,3,4,2,5. [10]
3.
Discuss heapify operation with example. Write down its algorithm and analyze its time and space complexity. [10]
Section B

Short Answers Questions

Attempt any Eight questions.
[8*5=40]
4.
Define RAM model. Write down iterative algorithm for finding factorial and provide its detailed analysis. [5]
5.
Write down nimmax algorithm and analyze its complexity. [5]
6.
When greedy strategy provides optimal solution? Write down job sequencing with deadlines algorithm and analyze its complexity. [5]
7.
Suppose that a message contains alphabet frequencies as given below and find Huffman codes for each alphabet.
SymbolFrequencya30b20c25d15e35\begin{array}{|c|c|}\hline \text{Symbol} & \text{Frequency} \\ \hline a & 30 \\ b & 20 \\ c & 25 \\ d & 15 \\ e & 35 \\ \hline \end{array}
[5]
8.
Does backtracking give multiple solution? Trace subset sum algorithm for the set (3,5,2,4,1)(3,5,2,4,1) and sum=8. [5]
9.
Why extended euclidean algorithm is used? Write down its algorithm and analyze its complexity. [5]
10.
Write short notes on a) Aggregate Analysis b) Selection problems [5]
11.
Write down algorithm of insertion sort and analyze its time and space complexity. [5]
12.
Define NP-complete problems with examples. Give brief proof of the statement "SAT is NP-complete". [5]