<mainheader:greedy algorithms >

<header>

<href#change making problem >

<href#prims algorithm >

<href#kruskals algorithm >

<footer>

greedy algorithms stop at the first working solution. In the c++ code I have a greedy algorithm called <url:/languages/cPP/algorithms_cPP/knap1.cpp:knap1.cpp>.

<name#change>

change making problem

what makes the change making solution greedy?
"greedy thinking leads to giving one quarter because it reduces the remaining
amount the most, anmely, to 23 cents." (pg. 303, levitin). Hence, it reduces
it by the highest number.
greedy is a general design technique despite the fact that it is applicable to optimization problems only

as an example there is the minimum.c

<name#prims>

prim's algorithm

"given n points, connect them in the cheapest way possible such that there will be a path between every pair of points"
We can represent points by the vertices of a graph. The problem then becomes the "minimum spanning tree problem."
spanning tree: its connected acyclic subgraph (ie. a tree), that contains all the vertices of the graph. A minimum spanning tree of a weighted connected graph is its spanning tree of the smallest weight, where the weight of a tree is defined as the sum of the weights on all its edges.
Once again, the problem here is the minimum spanning tree problem.

the algorithm works as follows:
on each iteration, add a connected-yet-not-visited vertex to the solution
the algorithm stops when it has visited each and every vertex which is part of the tree
output: the set of edges composing a minimum spanning tree of a weighted connected graph G = <V, E>

        ALGORITHM Prim(G)
        // Prim's algorithm for constructing a minimum spanning tree
        // Input: A weighted connected graph G = <V, E>
        // Output: ET the set of edges composing a minimum spanning tree of G
        V <- any vertex // can use any vertex to initialize
        ET <- the null 
        for i <- 1 to V-1 do 
                find a minimum-weight edge EW = (v,u) among all the edges (v,u)
                such that v is in VT and u is in V - VT
                VT <= VT union u   
                ET <= ET union EW
        return ET

this algorithm requires knowing which vertices are adjacent to the vertex you are asking about, and knowing its weight, too. How can this be found out?

the weights can be stored in a min-heap.

The adjacent vertices can be found from the adjacency-matrix or linked-list
representations of the graphs.

<name#kruskals>

kruskal's algorithm

The algorithm begins by sorting the graph's edges in nondecreasing order of
their weights. It then adds the next shortest edge which doesn't make a cycle
to its graph.

first-come-first-serve algorithm for cpu scheduling