Design and Analysis of Algorithms
This course introduces basic elements of the design and analysis of computer algorithms. Topics include asymptotic notations and analysis, divide and conquer strategy, greedy methods, dynamic programming, basic graph algorithms, NP-completeness, and approximation algorithms. For each topic, beside in-depth coverage, one or more representative problems and their algorithms shall be discussed.
Tribhuvan University
Institute of Science and Technology
2080
Bachelor Level / fifth-semester / Science
Computer Science and Information Technology( CSC314 )
Design and Analysis of Algorithms
Full Marks: 60 + 20 + 20
Pass Marks: 24 + 8 + 8
Time: 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.
Section A
Attempt any two questions.
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.
Write down the advantages of dynamic programming over greedy strategy. Find optimal bracketing to multiply 4 matrices of order 2,3,4,2,5.
Discuss heapify operation with example. Write down its algorithm and analyze its time and space complexity.
Section B
Attempt any eight questions
Define RAM model. Write down iterative algorithm for finding factorial and provide its detailed analysis.
Write down algorithm of insertion sort and analyze its time and space complexity.
Write down minmax algorithm and analyze its complexity.
When greedy strategy provides optimal solution? Write down job sequencing with deadlines algorithm and analyze its complexity.
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 |
Does backtracking give multiple solution? Trace subset sum algorithm for the set {3,5,2,4,1} andd sum=8.
Why extended euclidean algorithm is used? Write down its algorithm and analyze its complexity.
Define NP-complete problems with examples. Give brief proof of the statement “SAT is NP-complete”.
Write short notes on
a) Aggregate Analysis
b) Selection problems