Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionviii [2012/03/06 05:11] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionviii [2012/03/06 05:27] (current) – [Implementation and Running Time] mugabej
@@ Line 59: / Line 59: @@
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Start with T'\\
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Take the leaf labeled ω and add two children below it labeled y* and z*\\
->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> End if
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> End if\\
+\\
+  * The algorithm above is referred to as the //Huffman Algorithm// and the prefix code it produces is termed the //Huffman code//
+  * This algorithm produces an optimal prefix code
+  * This algorithm also follows a bottom-up approach as seen: It focuses on the leaves representing the two lowest-frequency letters, and then continues by recursion.
+\\
+\\
+==== Analyzing the Algorithm ====
+  * The algorithm is optimal
+  * ABL(T') = ABL(T) - f<sub>ω</sub>
+  * The Huffman code for a given alphabet achieves the minimum ABL of any prefix code
+==== Implementation and Running Time ====
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Create a leaf node for each symbol, labeled by its frequency, and add to a\\ queue(PQ).Takes O(nlogn)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> While there is more than one node in the queue: Takes O(n)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Remove the two nodes of lowest frequency. Takes O(logn)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Create a new internal node with these two nodes as children and\\ with frequency equal to the sum of the two nodes' probabilities. Takes O(1) time. \\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Add the new node to the queue Takes O(logn)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> The remaining node is the tree’s root node.\\
+\\
+So overall takes O(nlogn).\\
+\\
+Very intriguing section although its proofs were long. I give it an 8/10.