DAA Unit 3: Divide and Conquer, Greedy Previous Year Questions

by
  1. What do you mean by Graph Theory? Explain.
  2. Write a note on Graph and Digraph.
  3. Explain various data structure for Graphs.
  4. Write a note on Breadth First Search(BFS).What type of problem i can solve using BFS.
  5. Write a note on Depth First Search(DFS).What type of problem i can solve using DFS.
  6. Write a note on Bipartite Graph.
  7. Explain Topological Sort.
  8. Discuss Strongly Connected Components with its algorithm.
  9. What do you mean by Minimum Spanning Tree? Explain.
  10. Discuss Kruskal’s Algorithm to find MST with example and also find its analysis.
  11. Discuss Prim’s Algorithm to find MST with example and also find its analysis.
  12. Explain Bellman-Ford Algorithm and give its analysis.
  13. Suppose that undirected graph G=(V,E) has non-negative edge weights and these are raised by 1. Can the minimum spanning tree changes? Can shortest paths changes? Justify with proper example.
  14. Explain the greedy approach of algorithm.
  15. Write the characteristics and structure of Greedy Algorithm.
  16. Explain the Activity Selection Problem and give its solution by using Greedy approach with its analysis and correctness.
  17. What do you mean by “Greedy Algorithm”? Write its pseudo code and prove that the fractional knapsack problem has a greedy-choice property.
  18. What is 0/1 knapsack problem? Does greedy method effective to solve the 0/1 knapsack problem?
  19. Explain the Huffman Codes with examples.
  20. Explain the travelling salesman problem.
  21. What do you mean by Flow? Write Ford Fulkerson algorithm to find maximum flow in a network.
  22. Write an algorithm to find the minimum and maximum elements simultaneously from a given list of elements. you are also required to discuss its running time.