CSE 143: Computer Programming II, Spring 2014

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 parent 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.

Add a println to the constructor of your node class that will report the character value for every leaf node that it constructs. Remember that nodes are supposed to be added to the PriorityQueue in increasing character order. If you see any values that are out of order, then you have a bug.

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.

You can write some testing code that repeatedly calls remove on your PriorityQueue, printing the frequency of each node as it is removed from the PriorityQueue. You should see an increasing sequence of values (from low frequency to high).

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

A: Go to Encode.java and set its DEBUG flag to true. Then re-compress the file. Now it will actually write out the file as ASCII zeroes and ones instead of actual bits so you can read and debug it. Note that you won't be able to decode that file.

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. 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 decompress is empty?"

A: We will not 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.