Differences

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

--- courses:cs211:winter2018:journals:beckg:ch4 [2018/03/07 03:22] – beckg
+++ courses:cs211:winter2018:journals:beckg:ch4 [2018/03/12 20:48] (current) – beckg
@@ Line 125: / Line 125: @@
 Prim's Algorithm can be implemented in essentially the exact same manner as Dijkstra's (above). Therefore, with a priority queue, the algorithm runs in //O(m logn)// time.
+This section was very well explained, however I personally found it more clear the way we discussed in class (and the way I presented it here): with the Cut and Cycle properties first presented together and then used in analyzing the algorithms together. 8/10.
 ===== 4.6: Implementing Kruskal's Algorithm: the Union-Find Data Structure =====
@@ Line 142: / Line 143: @@
 Regardless, we hit the bottleneck of sorting the //m// edges: //O(m log m)// time, but more succinctly put, because //m =< n<sup>2</sup>//: //O(m logn)//. We do a total of at most //2m// Find operations, and //n-1// Union ops while running Kruskals, so the sorting time dominates and the final time is //O(m logn)//.
+I thoroughly enjoyed this section and the nuances between the different implementations (array, pointer, and collapse optimized pointer) of the Union-Find structure were very well explained. 9/10.
 ===== 4.7: Clustering =====
+Another application of MSTs is //clustering//: when we have a collection of objects and want to partition them into coherent. A common approach is defining a //distance function//, where objects more dissimilar can be considered more distant.
+With regard to formalism, we consider a set //U// of //n// objects labeled //p<sub>i</sub>// for //1=<i=<n//. We define the numerical distance between two objects //d(p<sub>i</sub>, p<sub>j</sub>)// to be always positive and symmetric between objects. Additionally, a //k-clustering// is a partition of //U// into //k// nonempty sets //C<sub>1</sub>, C<sub>2</sub>, ..., C<sub>k</sub>//, and the //spacing// of a k-clustering is the minimum distance between any pair of points lying in different clusters. We then are faced with a natural problem: finding a k-clustering (among the exponentially many possibilities) that has maximum spacing.
+The solution arises by seeing the clusters as connected components. Sorting the edges in ascending order of distance (cost), we can then iteratively merge these connected components by adding edges (skipping them if they would simply connect back to the same component). This is technically //single-link clustering//, a special case of //hierarchical agglomerative clustering// (agglomerative refers to combining clusters, single-link means we do so after a single link joins them). //But//, this is simply Kruskal's Algorithm, stopping after we've reached //k// connected components--just before it adds its last //k-1// edges.
+Or, we could think of it as taking the MST produced by the algorithm, and deleting the //k-1// most expensive edges. Therefore, within each component we actually have a tree, and there are //k// components. __These components constitute a k-clustering of maximum spacing.__ This hinges on the fact that those most expensive edges are the ones that would have connected any of the //k// components. Therefore, the next edge that would have been added (but wasn't, because we stopped the algorithm) can be considered to be the //spacing// of the k-clustering, which we know to be maximal due to the edge ordering. And if we had reached a higher edge, then we would have too many edges to have //k// disjoint clusters.
+This was a succinct and yet informative section. They explained the extension (abridgement?) of Kruskal's very well, and the formalism was illustrative and not overbearing. 9/10.
+===== 4.8: Huffman Codes and Data Compression =====
+Encoding complex information into binary sequences is a crucial part of data compression. A particular component is focused on storing information in as little physical memory as possible, and that's where taking advantage of the nonuniform frequencies of letter appearances comes into play. "Letters" in this case refers to fundamental pieces of whatever "alphabet" may be being used--this does not necessarily mean ASCII based information, it could be some form of encoded info.
+A //prefix code// for a set S of letters is a function g that maps each letter to some sequence of zeros and ones, in such a way that for distinct letters x and y in S, the sequence g(x) is not a prefix of the sequence g(y). This then allows the encoded message be perfectly decoded by scanning the bit sequence left to right. //Optimal// prefix codes are those that minimize the average number of bits required per letter (ABL(g)). This coincides with a given text to be translated as it depends on the relative frequencies of the letters' appearances which sum to 1.
+Note that we can represent prefix codes as binary trees, by simply defining from the root node, taking the path to the left child is a 0 and the right a 1. Additionally, the tree that corresponds to the optimal prefix code is //full//--each non-leaf node has two children. Also, note that the ABL therefore can be thought of as the weighted average of the depths of leaves (the weight is the frequency of each letter's appearance).
+Proven in the book, we have that there is an optimal prefix code and corresponding tree T in which the two lowest frequency letters are assigned to leaves that are siblings in T. So, given the relative frequencies of each letter, //Huffman's Algorithm// creates such a tree recursively from the bottom up by:
+  * If S has two letters: encode one using 0 and one using 1.
+  * Else:
+    * Let y and z be the two lowest freq. letters
+    * form a new alphabet S' by deleting y and z and replacing them with a new letter w of frequency //f<sub>y</sub>+f<sub>z</sub>//.
+    * Recursively construct a prefix code for S' with tree T'
+    * Define a prefix code for S as follows:
+      * Start with T'
+      * Take leaf labeled w and add two children below it labeled y and z
+The codes produced by this are called //Huffman codes//, and they achieve the minimum ABL of any prefix code. Implementing the algorithm using heap based PQs, we get a running time of //O(n logn)// for an alphabet of n letters.
+I very much liked this section. It was very good explaining everything, as well as the nuances involved in data compression. It certainly "fits" in this chapter of the book due to the greedy nature of the algorithm, but the introduction to information theory made the field seem fascinating and all I want is more! 9/10.