Bachelors Level/Third Year/Fifth Semester/Science csit/fifth semester/design and analysis of algorithms/syllabus wise questions
B.Sc Computer Science and Information Technology
Institute of Science and Technology, TU
Design and Analysis of Algorithms (CSC325)
Year Asked: 2080, syllabus wise question
Backtracking
1.
Does backtracking give multiple solution? Trace subset sum algorithm for the set (3,5,2,4,1) and sum=8.[5]
Dynamic Programming
1.
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]
2.
Write down nimmax algorithm and analyze its complexity.[5]
Foundation of Algorithm Analysis
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.
Define RAM model. Write down iterative algorithm for finding factorial and provide its detailed analysis.[5]
3.
Write short notes on a) Aggregate Analysis b) Selection problems[5]
Greedy Algorithms
1.
When greedy strategy provides optimal solution? Write down job sequencing with deadlines algorithm and analyze its complexity.[5]
Iterative Algorithms
1.
Discuss heapify operation with example. Write down its algorithm and analyze its time and space complexity.[10]
2.
Write down algorithm of insertion sort and analyze its time and space complexity.[5]
NP Completeness
1.
Define NP-complete problems with examples. Give brief proof of the statement "SAT is NP-complete".[5]
Number Theoretic Algorithms
1.
Suppose that a message contains alphabet frequencies as given below and find Huffman codes for each alphabet.
SymbolabcdeFrequency3020251535
[5]
2.
Why extended euclidean algorithm is used? Write down its algorithm and analyze its complexity.[5]