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: 2078, syllabus wise question
Backtracking
1.
Explain the concept of backtracking. How it differ with recursion? [5]
Divide and Conquer Algorithms
1.
Explain about the divide and conquer paradigm for algorithm design with suitable example. Write the Quick sort algorithm using randomized approach and explain its time complexity. [10]
Dynamic Programming
1.
Explain in brief about the Dynamic Programming Approach for algorithm design. How it differs with recursion? Explain the algorithm for solving the 0/1 Knapsack problem using the dynamic programming approach and explain its complexity. [10]
2.
What do you mean by memorization strategy? Compare memorization with dynamic programming. [5]
Foundation of Algorithm Analysis
1.
What are the elementary properties of algorithm? Explain. Why do you need algorithm? Discuss about analysis of the RAM model for analysis of algorithm with suitable example. [10]
2.
Explain the recursion tree method for solving the recurrence relation. Solve following recurrence relation using this method. T(n)=2T(n/2) +1 for n>1, T(n)=1 for n=1 [5]
Greedy Algorithms
1.
What do you mean by optimization problem? Explain the greedy strategy for algorithm design to solve optimization problems. [5]
2.
Explain the algorithm and its complexity for solving job sequencing with deadline problem using greedy strategy. [5]
Iterative Algorithms
1.
Write an algorithm to find the maximum element of an array and analyze its time complexity. [5]
2.
Write the algorithm for bubble sort and explain its time complexity. [5]
NP Completeness
1.
Explain in brief about the complexity classes P, NP and NP Complete. [5]
2.
Write short notes on: a. NP Hard Problems and NP Completeness b. Problem Reduction [5]