Tribhuvan University
Bachelor of Science in Computer Science and Information Technology
Semester 5 · TU Board 2080
Course Title: Design and Analysis of Algorithms (CSC314)
Full Marks: 60Pass Marks: 24Time: 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.
Group A
Attempt any two questions.(2 × 10 = 20)
- 1.10
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.10
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.10
Discuss heapify operation with example. Write down its algorithm and analyze its time and space complexity.
Answer comingAlso asked in 2080, 2078, 2076, Model question
Group B
Attempt any eight questions(8 × 5 = 40)
- 4.5
Define RAM model. Write down iterative algorithm for finding factorial and provide its detailed analysis.
- 5.5
Write down algorithm of insertion sort and analyze its time and space complexity.
Answer comingAlso asked in 2080, 2078, 2076, Model question
- 6.5
Write down minmax algorithm and analyze its complexity.
- 7.5
When greedy strategy provides optimal solution? Write down job sequencing with deadlines algorithm and analyze its complexity.
- 8.5
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.5
Does backtracking give multiple solution? Trace subset sum algorithm for the set {3,5,2,4,1} andd sum=8.
- 10.5
Why extended euclidean algorithm is used? Write down its algorithm and analyze its complexity.
- 11.5
Define NP-complete problems with examples. Give brief proof of the statement "SAT is NP-complete".
- 12.5
Write short notes on
a) Aggregate Analysis
b) Selection problems
— The End —