TRIBHUVAN UNIVERSITY
INSTITUTE OF SCIENCE AND TECHNOLOGY
2080 B.S.
Candidates are required to give their answers in their own words as far as practicable.
Group A
Long Answer QuestionsAttempt any Two questions.
- 1What is recurrence relation? How it can be solved? Show that time complenity of the recurrence relation $T(n)=2T(n/2)+1$ is $O(n)$ using substitution method.
- 2Write down advantages of dynamic programming over greedy, strategy. Find optimal bracketing to multiply 4 matrices of order {2,3,4,2,5}.
- 3Discuss heapify operation with example. Write down its algorithm and analyze its time and space complexity.
Group B
Short Answer QuestionsAttempt any Eight questions.
- 4Define RAM model. Write down iterative algorithm for finding factorial and provide its detailed analysis.
- 5Write down algorithm of insertion sort and analyze its time and space complexity.
- 6Write down minmax algorithm and analyze its complexity.
- 7When greedy strategy provides optimal solution? Write down job sequencing with deadlines algorithm and analyze its complexity.
- 8Suppose 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 |
- 9Does backtracking give multiple solution? Trace the subset sum algorithm for the set {3,5,2,4,1} and sum=8
- 10Why extended Euclidean algorithm is used? Write down its algorithm and analyze its complexity.
- 11Define NP-complete problems with examples. Give brief proof of the statement "SAT is NP-complete".
- 12Write short Notes on a) Aggregate Analysis b) Selection problems