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.
$\begin{array}{|c|c|}\hline \text{Symbol} & \text{Frequency} \\ \hline a & 30 \\ b & 20 \\ c & 25 \\ d & 15 \\ e & 35 \\ \hline \end{array}$
[5]
2.
Why extended euclidean algorithm is used? Write down its algorithm and analyze its complexity. [5]