DESIGN AND ANALYSIS OF ALGORITHMS(DAA) - Important Questions 2012

[Srini]

DESIGN AND ANALYSIS OF ALGORITHMS(DAA) - Important Questions 2012

Common To
080230013esign And Analysis Of Algorithms
10144CS402esign And Analysis Of Algorithms
CS1251 Design And Analysis Of Algorithms
141401esign and Analysis of Algorithms
CS41esign and Analysis of Algorithms

Unit I

1. Write the linear search algorithm and anlyse for its best, worst and average cast time complexity. Explain the asymptotic notations used for best, average and worst case analysis of algorithms
2. Explain in detail about the process of solving recurrence relations with suitable examples
3. Write the linear search algorithm and analyze for its best, worst and average cast time complexity.
4. Write the recursive algorithm for computing Fibonacci numbers and solve its recurrence relation.

Unit II

1. Explain in detail about merge sort. Illustrate the algorithm with a numeric example. Provide complete analysis of the same.
2. Discuss the use of Greedy method in solving Knapsack problem and container loading.
3. Discuss In Detail about Divide an conquer method with suitable examples
4. Write Binary search and linear search algorithm. Discuss the difference

Unit III

1. What is Dynamic programming? Apply this technique to find all pairs shortest path in a graph.
2. Discuss the Knapsack problem in Greedy techniques with an example.
3. Explain in detail about Travelling Salesperson problem with suitable examples
4. Explain all the approaches used in Multistage Graphs with an example.

Unit IV

1. Enumerate and Solve the problem Using Backtracking
(i) 8-Queens problem
(ii) Hamiltonian circuit problem.
2. Explain in detail about Backtracking with examples and apply Backtracking to solve graph colouring problem.
3. Determine the Hamiltonian cycle for the following graph
   
4. Explain subset – sum problem and discuss the possible solution strategies using backtracking.

Unit V

1. Explain the DFS and BFS traversals in a graph and write the algorithm with example.
2. Write and explain the techniques in branch and bound method with examples
3. Explain about graph colouring problem with examples
4. Give short notes on Biconnected component.