Differences

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

--- courses:cs211:winter2018:journals:hornsbym:chapter_4 [2018/03/06 02:35] – [Section 4.5 (Minimum Spanning Tree)] hornsbym
+++ courses:cs211:winter2018:journals:hornsbym:chapter_4 [2018/03/12 02:59] (current) – [Section 4.8 (Huffman Codes)] hornsbym
@@ Line 38: / Line 38: @@
 The section concludes with the implementation and runtime of //Kruskal// and //Prim's Algorithms//. Using a heap-based priority queue to hold the nodes, we can get a running time of O(//m// log//n//). The extractMin and changeKey function work in O(log//n//) time, and each is performed a maximum of //m// times, yielding O(//m// log//n//).
 ===== Section 4.6 (Union-Find Structure) =====
-===== Section 4.7 (Clustering) =====
+This section describes the Union-Find structure and its uses. It is well suite to implementing algorithms similar to //Kruskal's Algorithm//.\\
+\\
+The Union-Find structure only does exactly what its name implies: union and find operations. It does this by keeping track of disjointed sets (or graphs, in the case of //Kruskal's//). In addition to these functions, Union-Find will also have a makeUnionFind. MakeUnionFind will take a graph as an input, then return a Union-Find data structure in which each node is contained within its own set.\\
+\\
+An array-based implementation can be used to run the find operation in O(1) runtime and union in O(n) runtime. This is efficient enough to use on //Kruskal's Algorthm//, but it is not the most optimal implementation. The link-based implementation runs find in O(log//n//), which is worse than the array based implementation, but runs union in O(1). We are able to gain such an improved union runtime because we only have to create a link from one set to the next, as opposed to merging the two sets linearly.\\
+\\
+===== Section 4.7 (Clustering) =====
+===== Section 4.8 (Huffman Codes) =====
+Huffman codes compress data. Computers operate by producing and reading bits, which are sequences of 0's and 1's. Each sequence is assigned some piece of information that the computer can understand, so the problem is centered around picking the most efficient way of assigning sequences to information so that the most used information is assigned to the least costly sequence. Huffman codes do that exactly.\\
+\\
+Huffman codes use trees to organize and locate data. All data are stored in the leaf nodes of the tree, with the parent nodes being empty. As the computer reads through each bit, it traverses through the tree until it lands on a leaf node. Then, it returns that datum and reads through the next bit. It assigns O and 1 to a traversal to either the left or right child node, which guarantees that no two data will have the same encoding.\\
+\\
+What makes this algorithm work efficiently is that the trees are not always full. The most common data will be placed near the top of the tree, so that they are reached first. The book uses commonly used letters as an example. It would not makes sense for the letter 'e' to take up the same amount of space as a 'z' or 'q', since 'e' is more commonly used. Therefore, the trees can be somewhat skinny, but any given input will most likely not end up traversing the entire tree.\\
+\\
+If we use a heap priority queue to implement Huffman's algorithm, we can achieve O(//n// log//n//), with //n// representing the letters of the given alphabet. Heaps are trees that allow us to make insertions and deletions in O(log//n//) time. These operations are ideal for Huffman's algorithm, and so priority queues are the ideal data structure to use.