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: 2076, syllabus wise question
Backtracking
1.
Explain in brief the Backtracking approach for algorithm design. How it differs with recursion? Explain the N-Queen problem and algorithm using backtracking and analyze its time complexity.[10]
2.
Write short notes on: a. Backtracking strategy b. Tractable and Intractable Problem[5]
Divide and Conquer Algorithms
1.
Explain the divide and conquer paradigm from algorithm design with a suitable example. Write the Quick sort algorithm using a randomized approach and explain its time complexity.[10]
Dynamic Programming
1.
What do you mean by Dynamic programming strategy? Explain the element of DP.[5]
Foundation of Algorithm Analysis
1.
What do you mean by the complexity of an algorithm? Explain the asymptotic notations used to describe the time/space complexity of any algorithm with their geometrical interpretation and example.[10]
2.
Solve the following recurrence relation using the master method. a. T(n)=7T(n/2)+n2 b. T(n)=4T(n/4)+kn[5]
Greedy Algorithms
1.
Explain the greedy algorithm for the fractional knapsack problem with its time complexity.[5]
2.
Explain the approximation for solving vertex cover with a suitable example.[5]
3.
Explain Prim’s algorithm for MST problem and analyze its time complexity.[5]
Iterative Algorithms
1.
Write the algorithm for selection sort and explain its time and space complexity.[5]
2.
Trace heap sort algorithm for the following data: (2, 9, 3, 12, 15, 8, 11)[5]
NP Completeness
1.
Explain in brief about the classes P, NP, and NP complete with examples.[5]