Module 3 Greedy Method Approach

Edit Answers
12345678910111213141516171819202122232425
Across
  1. 3. A connection between two vertices in a graph.
  2. 4. A path in a graph that starts and ends at the same vertex.
  3. 7. A collection of vertices connected by edges.
  4. 9. A greedy algorithm that constructs an MST by selecting edges in increasing order of weight.
  5. 11. The ratio used to select items in the Fractional Knapsack algorithm.
  6. 16. The smallest possible total cost required to connect all vertices.
  7. 17. A spanning tree with the minimum possible total edge cost.
  8. 18. The process of updating a shortest-path estimate when a shorter path is found.
  9. 19. An algorithm that makes the best local choice at each step.
  10. 20. A container with limited capacity used in an optimization problem.
  11. 21. The current shortest known path length from the source to a vertex.
  12. 22. The maximum weight that can be carried in a knapsack.
  13. 24. The starting vertex from which shortest paths are calculated.
Down
  1. 1. A graph in which every vertex can be reached from every other vertex
  2. 2. The locally best choice made by a greedy algorithm.
  3. 5. A point or node in a graph.
  4. 6. A problem in which fractions of items can be selected to maximize total profit.
  5. 8. The benefit or value obtained by selecting an item.
  6. 10. The best solution available at a particular step.
  7. 12. A set of edges connecting all vertices without forming a cycle.
  8. 13. A greedy algorithm used to find shortest paths from a source vertex.
  9. 14. A greedy algorithm that constructs an MST by repeatedly adding the minimum-cost edge connected to the tree.
  10. 15. SOURCESHORTESTPATH The problem of finding the shortest paths from one source vertex to all other vertices.
  11. 23. The amount of capacity consumed by an item.
  12. 25. The numerical cost associated with an edge.