DiscussioThe Uon: October 31, 2007University of Michiganyg1Agendaz Questions on anythingz Basic Debugging Tipsz PA2: Huffman Encodingz Specific questions:2Questions on anything?z Questions?:3Basic Debugging Tipsz xxd (demonstration) z Cout vs. printf− printf: How to use− Common args: d, x, o:4PA2: Huffman Encodingz MinHeapWh t' h ?−What's a heap?− What's a minheap?− Enqueue (example) − Dequeue (example) z Right childz Smallest key swap− How can we use this for:r PA2...?5PA2: Huffman EncodingHappy Halloweenappy a o ee(Candy example(y p:!))6PA2: Huffman Encodingz Okay, so we have minheap with freqz Trie− Putting into tree− Encodinglklfhz Alert: Can make your life easier with− Good style (Markdowns on PA1) Classes−Classesz Triez Minheap:quencies... Now what?hh7PA2: Huffman Encodingz Okay, so now it's in a trie... now wh− Regular code table: <sym, freq, − Compressed code table (use thisz Website:at? code>s one) 8PA2: Huffman Encodingz What goes in the encoded data?:9PA2: Huffman Encodingz Review of what we need to do (reme1.) Create minheap class: can have <k2.) Create trie class3.) Read in input data (M&Ms) 4.) Put input data into minheap “keyed- This means lowest key at root5.) Construct trie (keep pulling off the - Remember: have to put sub-trie b6.) When trie is built, we can create the7.) Create compressed code table8.) For encoded data, just use the code:ember this is ONE way):key,object> paird” by frequencyroot of minheap to get pairs) back onto minheap sometimes!e codes for each symbole table to determine what goes where10Bit operationsz Is anyone having trouble with bit opz If so, let's address it now:perations for anything (rle, etc.)?11Questions?Any
View Full Document
Unlocking...