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) + 1$ is $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,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.

$\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)$ 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]