CSIT 5th Semester
Design and Analysis of Algorithms Board Question Paper 2080

CSC 325-2080 ✡
Tribhuvan University
Institute of Science and Technology
2080
✡
Bachelor Level/Third Year/Fifth Semester/Science
Computer Science Information Technology (CSC 325)
(Design and Analysis of Algorithms)
(New Course)
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 Answer Questions
Attempt any Two question.
[2x10=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.

2.

Write down 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

[8x5=40]
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.

SymbolFrequency
a30
b20
c25
d15
e35

9.

Does backtracking give multiple solution? Trace the subset sum algorithm for the set {3, 5, 2, 4, 1} and 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