GREEDY ALGORITHMS

Unlike dynamic programming algorithms which essentially try all possible combinations, but intelligently, so that they run a reasonable amount of time, greedy algorithms although they generally solve the same sort of problems, utilize a trick or shortcut which, fortunately, always yields the correct answer.

However, hoping that the slick trick works is not the same as knowing that it does.

Minimum Spanning Tree -- Kruskal's Algorithm

So, in the Kruskal's algorithm, the first choice I make is the smallest edge in the tree.  Now if another algorithm makes a different tree than mine, check and see if that other tree contains my first edge.  If it does, great, it matches my algorithm so far.  If it does contain my first edge, then I will add my first edge to that other tree.  This will introduce a cycle in that other tree, which I can break by removing any edge of that cycle.  Well, since the edge I added was the smallest in the graph, if I break the cycle anywhere else, I have lowered the edge weight of that other tree (or at the very least kept it the same if there is another edge whose weight matches mine).

Let's say that the first n edges from Kruskal's are all present in the other tree.  Then, let's try the (n+1)th edge.  Once again, if this edge is not present in the other tree, I add it and introduce a cycle.  Now, this brand new cycle could not possibly contain an edge with a smaller edge weight than my (n+1)th edge.  Because if it did, that edge would have introduced a cycle in the Kruskal tree (because I did not add it there), so this new cycle must also be of edges greater than or equal the (n+1)th edge, so break that cycle and I have again either kept the other tree the same edge weight or possibly have improved it.

"I am doing a good job, aren't I?"

Second person plural:  Y'all in most of the south.  All y'all in Texas, and in New York, it was you guys.  And in New Jersey, it's youse guys.

Huffman Code:  a greedy algorithm to compute the MINIMUM number of bits required to encode a message.

So, a prefix code:  A prefix code is more aptly called a "no-prefix code".  No valid code is a prefix of any other.

So, if I have "0101" as one of my code symbols, no other code symbol is allowed to begin with 0101.  The reason for this is this obviates the need for delimiters.

If I have a huge string:  01010001010110101...  I see that it begins with 0101 and so that must be where this symbols ends and a new one begins.