Semester
Subject
Year
B.Sc Computer Science and Information Technology
Institute of Science and Technology, TU
Design and Analysis of Algorithms (CSC325)
Year Asked: 2082, syllabus wise question
Backtracking
1.
Find all possible subsets of the integers that sum to 21 in the array {5, 6, 10, 11, 15} using back tracking technique. [5]
2.
Distinguish between recursion and backtracking. Using Miller-Rabin primality test, check whether 53 is prime or not? [5+0]
Divide and Conquer Algorithms
1.
What is order statistics? Write and analyze the algorithm for randomized quick sort. [10]
Dynamic Programming
1.
Distinguish between dynamic programming and memorization. Parenthesize the matrices A(30 × 1), B(1 × 40), C(40 × 10) and A(10 × 15), for computing matrix multiplication using dynamic programming. [10]
2.
How does 0/1 Knapsack problem differ from fractional one? Find the minimum vertex cover in the following graph. 
[5+0]
Foundation of Algorithm Analysis
1.
Solve the recurrence relation T(n) = 2T(n/2) + n using recursion tree method. [5]
2.
State the time and space complexity for sequential search. Write the rules for master theorem for finding asymptotic bounds. [5]
Greedy Algorithms
1.
How do you define optimal solution? Does greedy algorithm always guarantee optimal solution? Given the string "SUPER DUPER CSIT", use a Greedy algorithm to build a Huffman tree. [10]
Iterative Algorithms
1.
Find the best and worst case for Bubble sort. [5]
2.
Justify the worst case for binary search. Find the edit distance from the string "RELEVANT" to "ELEPHANT" using dynamic programming approach. [5+0]
NP Completeness
1.
Define class P and NP problem. Why do we need approximation algorithms? Justify. [5]
Number Theoretic Algorithms
1.
Using Extended Euclidean Algorithm, find the GCD of 12 and 16. [5]