CSE 143: Computer Programming II, Winter 2012

Homework 8 (Huffman) FAQ

Q: I don't understand what is going on in this assignment.

A: Take a look at the pictures in the assignment writeup and lecture slides. They explain how the priority queue works with the alogrithm we've given you. Be sure to also look over your section handouts for help on how to attach each node of the Huffman Tree to the new "daddy" node.

Q: "My tree doesn't get created correctly. How can I tell what's going on?"

A: Try adding debugging code or use the structure viewer in jGRASP to view your Huffman Tree. See if your tree is adding in nodes in the correct manner(pull off two, make a new node and attach them to it, re-insert into the priority queue). Take a look at the writeup for how to set up jGRASP in order to Look at the HuffmanTree. Be aware of the problem with \r characters that occur as new lines in some text-editors. Avoid such characters by making sure to right-click the input text files when you save them, rather than doing select-all, copy-paste into your editor.

Q: "The contents of my priority queue don't seem to be in sorted order. Why?"

A: A PriorityQueue's toString behavior (as well as the result of using an iterator/foreach, or viewing the PQ in jGRASP) does not show the elements in their sorted order, so it might be confusing to use these methods of debugging. Try looking at the Lectures page for more information on how to deal with priority queues.

Q: "How can I tell what bits are getting written to my compressed file?"

A: Go to the HuffMain and set its DEBUG flag to true. Then re-compress the file. Now it will actually write out the file as ASCII bytes instead of bits (example: input, output), so you can read and debug it. Or set your BitIn/OutputStream to full-byte mode by calling .setBitMode(false) on it.

Q: "Why are the EOF and last few bits missing from my file?"

A: If you don't close() your output streams, the last EOF and last few bits may not get written.

Q: "Why do I have some unexpected characters in my Huffman tree that were not in the sample output?"

A: Maybe you saved the input files improperly to your computer. Don't select-all and copy/paste. Instead, right-click the link to each file and choose Save As.

Q: "My program works for most files, but when I try to decompress hamlet.txt, I get a StackOverflowError. Why?"

A: Your algorithm is nesting too many recursive calls. Once you are done making one recursive walk down the tree, you should let the call stack unwind rather than making another recursive call to get back to the top of the tree.

Q: "My program runs really slowly on large files like hamlet.txt. How can I speed it up?"

A: This can happen if you try to build up one huge string for the entire file and then print that string. Try to print out one character or one binary encoding at a time. Also try running your program in the normal HuffMain rather than the GUI. Your program also might be slow because you're running it on a slow disk drive such as a USB thumb drive.

Q: "My priority queue crashes with a ClassCastException: Comparable. Why?"

A: The HuffmanNode class must implement the Comparable interface in order to perform effectively.

Q: "What should the Comparable ordering be if the two nodes' counts are equal?"

A: As the spec says, compare only the counts. If the counts are the same, consider the two nodes to be equal.

Q: "What should it do if the file to compress/decompress is empty?"

A: We won't test that case.

Q: "What is the default value for a char? What char value can I use to represent nothing, or the lack of a character?"

A: The default char value is '\0', sometimes called the 'null character'. (Not the same as null, the null object reference.) But it doesn't really matter what character you use in a node where the character is meaningless. The program won't examine that character anyway.