DAA Question Bank

Unit-1
1. State and prove master’s theorem?

2. Write the algorithm for insertion sort and analyze its time complexity?
3. Write the recurrence relation for divide and conquer strategy and explain
4. What are different methods to solve recurrence relation
5. Write the algorithm for quick sort with an example
6. Explain merge sort algorithm with an example.
7. Discuss the time complexity of quick sort
8. Write the algorithm for selection sort and analyze its time complexity?
9. Estimate the time complexity using f(n) and g(n) functions in asymptotic notations.
10. Perform binary search on list of elements to find the key element using divide and conquer, and
also estimate the time complexity.
11. Show that the average case time complexity of merge sort algorithm is O(n log n).
12. In what way amortized analysis is used for performance analysis of algorithms? Explain With
Example.
Unit-2
1. Discuss the applications of graphs

2. Explain different types of graphs with examples
3. How do you represent graph inside the memory?
4. Explain about DAG?
5. Explain about topological sorting?
6. Which would be the best representation in adjacency matrix and list? Explain Why?
7. Explain graph traversal BFS with an example?
8. Explain graph traversal DFS with an example?
9. Derive BFS for the bellow graph and represent in matrix format
10. Derive DFS for the bellow graph and represent in matrix format
11. Explain BFS Algorithms and analyse it’s time complexity?

12. Explain DFS Algorithms and analyse it’s time complexity?
Unit-3
Write the difference between greedy method and dynamic programming?

What is a priority queue and how can we implement priority queues?
Explain BST creation with the following keys.
19,5,9,12,34,16,4,3,9
Analyse Binary Heap creation and insertion with their time complexities
List the AVL tree rotations with appropriate examples?
Explain BST search algorithm with appropriate example?
Find out minimum cost spanning tree for the above graph using Kruskal’s Algorithm.
Explain various tree traversal techniques in detail?
Explain Prim’s Algorithm with an example
Explain Kruskal’s Algorithm with an example
Calculate shortest path for the following list using Dijkstra’s algorithm?
0 50 30 100 10
0 0 0 0 0
0 5 0 0 0
0 20 50 0 0
0 0 0 10 0
Explain prims Algorithm for the following graph
Unit-4
Explain the methodology of Dynamic programming.

List the applications of Dynamic programming
Discuss the Bellman Ford algorithm and analyze its time complexity.
Define i) Principles of optimality ii) Feasible solution iii) Optimal solution
What is All – Pair Shortest Path problem (APSP)? Discuss the Floyd’s APSP algorithm and discuss the
analysis of this algorithm
Discuss the Warshall algorithm and analyze its time complexity
Compute the optimal path and its profit for the problem Job sequencing with deadlines?
Job J1 J2 J3 J4 J5
Deadline 2 1 3 2 1
Profit 60 100 20 40 20
Describe the Matrix multiplication chains problem. Apply dynamic programming strategy to determine
optimal sequence of pair wise matrix multiplications
Write the algorithm to compute 0/1 Knapsack problem using dynamic programming and explain it.
Consider a knapsack instance M=8, n=4 P(1;4)= (1,2,5,6) W(1:4)=(2.3.4.5) derive the solution and
explain
Solve the travelling salesman problem for the adjacency matrix of the graph
1 2 3 4
1 0 10 15 20
2 5 0 9 10
3 6 13 0 12
4 8 8 9 0
Explain the Travelling sales man problem with an example?
Unit-5
1. Explain the general technique of backtracking?
2. Explain Hamilton cycle problem?

3. Define class P, class NP, and class NP-complete problems?
4. Explain about graph colouring problem with an example
5. State and explain the subset sum problem with an example.
6. Derive the state space tree for the sum of subset problem
n=6, m=30, W(1:6)= (5,10,12,13,15,18)
7. What is 4-queens problem?
8. Explain the basic principle of Backtracking and list the applications of backtracking.
9. Explain the control abstraction of backtracking and derive the state space tree for 4 queen
problem
10. Explain the solution to the graph coloring problem using backtracking.
11. Give the solution to the 8-queens problem using backtracking
12. Write an algorithm to determine the Hamiltonian cycle in a graph using backtracking.

DAA Question Bank

Uploaded by

Copyright:

Available Formats

DAA Question Bank

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DAA Question Bank

Uploaded by

Copyright:

Available Formats

Unit-1

1. State and prove master’s theorem?

1. Discuss the applications of graphs

11. Explain BFS Algorithms and analyse it’s time complexity?

Write the difference between greedy method and dynamic programming?

Explain prims Algorithm for the following graph

Explain the methodology of Dynamic programming.

Explain the Travelling sales man problem with an example?

1. Explain the general technique of backtracking?

2. Explain Hamilton cycle problem?

You might also like