Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
courses:cs211:winter2011:journals:wendy:chapter4 [2011/03/01 00:51] – [Section 7: Clustering] shangw | courses:cs211:winter2011:journals:wendy:chapter4 [2011/03/02 04:59] (current) – shangw | ||
---|---|---|---|
Line 79: | Line 79: | ||
This section talks about another problem-Clustering-and how to solve it with greedy algorithm. Clustering (of maximum spacing) can be precisely described as partitioning a collection of objects U such that the maximum possible spacing s achieved (That is, the minimum distance between any pair of points lying in different clusters is minimized). | This section talks about another problem-Clustering-and how to solve it with greedy algorithm. Clustering (of maximum spacing) can be precisely described as partitioning a collection of objects U such that the maximum possible spacing s achieved (That is, the minimum distance between any pair of points lying in different clusters is minimized). | ||
- | The algorithm is exactly the Kruskal' | + | The algorithm is exactly the Kruskal' |
+ | |||
+ | Practical applications can be finding out the clusters and using low-cost network within the cluster and using more robust network between each cluster. | ||
+ | |||
+ | This section is quite short but the application of the minimum spanning tree is interesting. | ||
+ | |||
+ | ===== Section 8: Huffman Code and Data Compression ===== | ||
+ | |||
+ | This section introduces us the Huffman Code and how to use greedy algorithm to achieve. | ||
+ | |||
+ | First, the book gradually introduces the origin of Huffman coding from using 1,0 bits representing letters, the different frequency of usage of letters in English, the Morse code which is similar but easier with the pausing, Prefix codes and the way to calculate the optimal prefix codes (minimize the sum of frequency*bit-length). | ||
+ | |||
+ | To begin design the algorithm, intuitively the Binary Tree comes to mind because if we only use the leaves to represent letters then it is gonna be prefix code since no parent is involved. It is not hard to see that the optimal prefix code corresponds with some full binary tree. Now we attempt to construct the algorithm to build such a full binary tree. The Top-Down Approach as in the S-F code is the first try, unfortunately the example used earlier is already a counter example. To perfectly modify this approach needs to borrow knowledge from dynamic programming, | ||
+ | |||
+ | Compression is not always as easy as the Huffman coding. Tow major challenges are the " | ||
+ | |||
+ | I like the structure of this section because it tends to " | ||
+ | |||
+ | Readability is 8. |