SRM University 2007 B.Tech Computer Science and Engineering Bank : Design and Analysis of Algorithms - exam paper

PART-B

1. Explain the binary search algorithm with an example.
2. Explain mimmax issue using Divide and conquer technique. calculate its time complexity.
3. Explain merge sort with an example. calculate its time complexity.
4. Explain Quick sort with an example. provide its time complexity.
5. Solve the knapsack issue using greedy technique.
6. Explain Prim’s algorithm to construct Minimum cost spanning tree.
7. Explain Kruskal’s algorithm to construct Minimum cost spanning tree.
8. Explain Optimal Randomized algorithm to construct Minimum cost spanning tree.
9. Explain single source shortest path algorithm (Dijkstra’s algorithm).


UNIT – III

PART – A
1. Define Dynamic programming technique.
2. Define Principle of optimality.
3. What do you mean by Multistage graph.
4. Differentiate the two approaches in finding the minimum cost path of multistage graph.
5. Find the minimum cost path using forward and backward technique for the graph provided beneath.
6. Give the conditions to the table in 0/1 knapsack.
7. 0/1 knapsack issue cannot be solved by Greedy technique.Why?
8. Explain briefly about Traveling sales person issue.
9. What are the three traversal technique for binary trees.
10. What do you mean by traversal?
11. Give the non recursive algorithm for Triple order traversal.
12. Give the recursive algorithm for Triple order traversal.
13. Define Breadth 1st search.
14. Define Depth 1st search.
15. What is breadth 1st spanning tree? provide and eg.
16. Give the constraints to solve the Traveling sales person issue in dynamic programming.
17. What is 0/1 knapsack issue.
18. Define connected graph. provide an eg.
19. Define Articulation point. provide the condition to identify an articulation point.
20. Identify the articulation points and draw the biconnected components for the graph provided beneath.

PART – B
1. Explain all pairs shortest path algorithm with an eg. provide its time complexity
2. What is multistage graph? discuss with an eg. Write the pseudo code for the finding the minimum cost path using forward approach.
3. What is multistage graph? discuss with an eg. Write the pseudo code for the finding the minimum cost path using backward approach.
4. Write an algorithm for 0/1 knapsack issue.
5. Write and discuss an algorithm for BFS and DFS. provide an eg.
6. Give an algorithm to identify articulation points and to construct biconnected components. discuss with an eg.
UNIT – IV

PART – A

1. What are explicit constraints and implicit constraints?
2. Explain 8-Queen issue in brief.
3. What are static trees and dynamic trees?
4. Give any four issues that could be solved by backtracking.
5. What are the constraints of 8-Queens issue
6. Define m-colorability optimization issue.
7. What is a Hamiltonian cycle?
8. What are the two methods of Branch and bound techniques?
9. Compare and contrast LC-BB and FIFO BB.
10. What is a decreased cost matrix?


PART – B

1. Explain N-Queens issue using Backtracking.
2. Explain Graph Coloring.
3. Explain sum of subsets.
4. Explain Hamiltonian cycles.
5. Solve Knapsack issue using backtracking.
6. Explain Traveling Salesperson issue using branch and bound techniques.

UNIT – V

PART – A

1. What is P and NP?
2. What is deterministic algorithm?
3. What is Non-Deterministic Algorithm?
4. Draw the relationship ranging from P, NP, NP complete and NP-hard.
5. What is the property of NP-Complete problem?
6. What is the property of NP-Hard problem?
7. What are the 2 most famous unsolved issues in Computer science?


PART – B

1. Explain the basic concepts of P, NP, NP-Complete and NP-Hard.
2. Prove a graph issue is NP-Hard.
3. Explain a NP-Hard Scheduling issue.
4. Explain a NP-Hard code generation issue.
5. Explain the concepts of Approximation algorithm.

Earning:   Approval pending.