Semester
Subject
Year
B.Sc Computer Science and Information Technology
Institute of Science and Technology, TU
Design and Analysis of Algorithms (CSC325)
Year Asked: 2081, syllabus wise question
Backtracking
1.
Given a set , find the subset that sum to 35 using backtracking. [5]
2.
Discuss about recursion and backtracking. Analyze the complexity of Miller Rabin Randomized Primality test. [5]
Divide and Conquer Algorithms
1.
What is the worst case of quick sort and how does randomize quick sort handle this problem? Sort the data using quick sort. [10]
Dynamic Programming
1.
Differentiate between dynamic programming and memorization. Compute the shortest path between every pairs in the following graphs using Floyd Warshall algorithm. 
[10]
2.
Define order statistics problem. Find the edit distance between 'cat' and 'car' using dynamic programming. [5]
Foundation of Algorithm Analysis
1.
Solve the following recurrence relations using master's method.
[5]
2.
State cooks theorem. Discuss about problem reducibility. [5]
3.
Write short notes on: a) Big Oh, Big Omega, Big theta b) Class P, Class NP and NP-Complete [5]
Greedy Algorithms
1.
Does greedy algorithm guarantee optimal solution? Solve the Fractional knapsack problem to find maximum loot from given information.
[10]
2.
Explain the approximation algorithm for vertex cover of a connected graph with an example. [5]
Iterative Algorithms
1.
Write an algorithm to find the fibonacci number with its time and space complexity. [5]
Number Theoretic Algorithms
1.
Solve the following linear equation using Chinese Remainder Theorem. x = 1 MOD 3,x = 2 MOD 5,x = 0 MOD 7 [5]