Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:anna:chapter_4 [2011/02/15 23:59] – poblettsa
+++ courses:cs211:winter2011:journals:anna:chapter_4 [2011/03/02 03:48] (current) – poblettsa
@@ Line 23: / Line 23: @@
 There are two things to note about this algorithm.  First, this algorithm is dependent on the fact that all the weights are positive.  Second, this algorithm is really just an extension of BFS.  If we implement this algorithm with a priority queue, it can run in O(mlogn) time.  Where the algorithm itself if O(m) and the operations on the priority queue are O(logn).
+=== 4.5 The Minimum Spanning Tree Problem ===
+This problem consists of figuring out the cheapest way to connect a network such that all the nodes are connected and the solution is a tree.  There are three different greedy algorithms for this problem, all of which work well.  The first is Kruskal's algorithm, which builds a spanning tree by successively inserting the edge of least cost, given nit does not create a cycle with the edges already added.  Next is Prim's Algorithm, which is similar Dijkstra's Algorithm.  It starts with a root node and repeatedly adds the cheapest node out of the partial tree to the nodes not already looked at.  Lastly, there is the Reverse-Delete Algorithm that starts with a full graph and repeatedly deletes the most expensive node, as long as it would not disconnect the graph.
+The two important properties for analyzing these algorithm are the Cut Property and the Cycle Property.  The Cut Property basically says that for any subset of nodes S, then the minimum edge from S to the rest of the graph must be in the minimum spanning tree.  This property helps prove the optimality of Kruskal's and Prim's Algorithms.  The Cycle Property essentially states that the most expensive edge in any cycle is not in the minimum spanning tree.  This helps prove the optimality of Reverse-Delete.  If we implement Prim's Algorithm with a priority queue, we can get an overall running time of O(m logn).  For me, Reverse-Delete and Kruskal's Algorithm are the most intuitive.
+=== 4.6 Implementing Kruskal's Algorithm: The Union-Find Data Structure ===
+To efficiently implement Kruskal's Algorithm, we create a special data structure with specific functionality.  Find(u) will return the set containing the node u and Union(u,v) will merge two sets.  The simplest data structure for union-find is an array with the name of the set containing each element.  With this Find(u) is constant time and Union(u,v) is linear.  However, we can do better if we use a data structure that uses pointers.  Each node will be in a record and will have a pointer to the name of the set it is in.  Thus, we can implement Union(u,v) in constant time by just updating the pointers.  We can also make Find(u) run in O(logn), which is overall faster.
+To implement Kruskal's Algorithm with this idea, we first sort the nodes by cost, which takes O(logm) time.  Then we use the Union-Find to maintain the connected component of the tree we are building.  We consider each edge with nodes u and v, compute Find(u) and Find(v), and then merge them if the algorithm says the edge should be in the tree.  This algorithm seems very straight-forward, but is a little trickier to implement once you get into the details and try to make it as efficient as possible.
+=== 4.7 Clustering ===
+The Clustering Problem is essentially trying to classify objects into coherent groups based on some distance function.  This distance function is often abstract, rather than a distance in feet as we may think of it.  The goal is to divide objects into groups so that objects in the same group are "close together" and objects in different groups are "far apart".  We use minimum spanning trees to try to find the clustering of maximum spacing of k clusters and n nodes.
+The idea of the algorithm is to add an edge between the nodes/clusters of smallest distance repeatedly, where clusters are connected components.  We will start with n clusters and continue this process until we are down to k clusters, as we desire.  It turns out this can be done using Kruskal's Algorithm where we just stop before it adds the last k-1 edges.  This is equivalent to getting the minimum spanning tree then deleting the most expensive k-1 edges.  I would not have thought these were equal, but after going through the proof it makes sense.
+=== 4.8 Huffman Codes and Data Compression ===
+The general problem of this section is how to encode symbols using bits.  The simplest way, but not the most efficient, is to have codes of the same length for each symbol.  For example, if we had 32 symbols to encode, we would need 5 bits.  However, must alphabets have letters that occur more frequently than others, so it would be more efficient to make the bits for those symbols shorter.  This idea is called data compression.  A type of code with different numbers of bit for different symbols is a variable length coding (i.e. Morse code).  However, it is also important that a code be a prefix code, which means that no code word is a prefix of another.  This means you can just read the encoded message in a straight line until you reach a code word, and you will not run into any confusion.
+To evaluate compression, we can look at average number of bits per letter, which is the sum of the frequencies times the number of bits for each letter.  The goal is to find a prefix code with the minimum average bits per letter.  These codes are called Huffman codes, and are represented using a binary tree.  In this tree, the left child represents a 0 and the right side represents a 1.  Each leaf is a letter and you get the bits for that letter by following the path down the tree.  An algorithm to build this tree, given frequencies and an alphabet, is on page 172.  You can prove Huffman codes are optimal using induction and the running time of the algorithm is O(k logk).
+This section was interesting to me because I actually took a class on data compression in Scotland last semester.  We actually learned to think about and visualize Huffman codes without the tree, but we still used the tree to implement it.  It was interesting to see a more in depth analysis of the algorithms I worked with before.