Greedy algorithms

Question 1

What is Greedy?

Answer 1

Make a local optimal choice in hope that it will ultimately lead to global optimal solution.

Question 2

Greedy specifics

Answer 2

1. Control-function
2. Selection-function
3. Feasibility function
4. Objective function
5. Solution function

Question 3

Greedy requirements!!!

Answer 3

1. Feasible
2. local optimal
3. irrevocable

Question 4

Dijkstra’s algorithm

Answer 4

Choose starting node. Continue to keep track of final score and last visited node. Begin by looking at all edges from starting node and value which one is the best etc. Proceed to the nodes that are directly connected to the starting node and repeat process. Remember not to compare against the node that you came from, however compare against nodes that you have visited before but from a different position. If new path has smaller value then replace it.

Question 5

Minimum spanning tree

Answer 5

a way to connect all nodes with smallest final weight (value).

Question 6

Prim’s algorithm

Answer 6

Begin with selecting any vertex. Look at all the edges that the vertex has and choose the one with smallest weight (value). Now you have 2 vertices in your solution. Look at all the edges available from those vertices and choose the one with smallest value. Repeat until all vertices are in solution.

Question 7

Kruskal’s algorithm

Answer 7

Find and start with edge with smallest weight. Find the second smallest edge that doesn’t create a cycle with previously selected edges. Repeat until all vertices are in solution.

Question 8

Difference between Prim and Kruskal?

Answer 8

Prim: vertex approach
Kruskal: smallest weight edge approach