The Bonus competition -- As opposed to writing two versions of the compressor RevAdaptive, or two compression functions, one that outputs the header, and one that doesn't, you will implement two different compressors entirely. The RevAdaptive should always use the inefficient header that I provided most of; this is simply a list of 256 32-bit numbers. This will keep everyone's output the same for grading purposes. I've added another compressor, Bonus, which does not in fact compress the file at all, it only outputs a header; this is where all competition work should be done.
Note -- Header information should not be considered when asked about sizes of files in questions 1-4, I'm only interested in the file that not the header.
Question 3 -- Should be slightly re-worded. No better should be repalced with better by no more than one bit.
The final decisions have been made about the programming part of the project. Sorry for the delay. You will be implementing 10 short (5..20 lines each) functions in an array version of the adaptive tree data structure. These fuctions are: exchangeWithLeader, slideAndIncrement, update, encode and decode and the reverse adaptive versions of the same functions. The rest of the software package will be provided to you. You are encouraged to explore all of the code in order to see where your work fits in. The array structure will be described in class, and I will have a detailed explenation posted soon.
In the 4th sections of Vitter's paper, at the bottom of the 15th page of the paper, there is a typo in the SlideAndIncrement code. Due to the "if (_ and _) or (_ and _) then" clause, there are cases when you don't actually ever adjust p to point to some parent or increase the weight of the node p points to. There should be and "else p's weight := wt+1; := parent of p" between the two end statements. This is a bug because, suppose that neither p the referance p nor the weight of the node it points to changes; In the main loop: while "q is not the root ..." since q never changes, it will loop forever.
When implementing the update function for the Vitters algorithm (OptAdaptive), there should be a slight correction to the psudo-code in the paper. This comes from the fact the in Vitters actual implementation with floating trees, there was no real root node per se. In our array implementation we need to add a line after whe main while loop, but before the if (special case) statement that says "Increment the weight of the root". The weight of the root doesn't get updated by the main loop.
In the questions in the homework, header information is to be IGNORED when computing the length of the output, headers are free for rev-adaptive and for huffman.
You should use the command turnin --submit whunt project1 (filename) to submit your answers. man turning if you are confused about the turnin program.
Many students had forgotten some basic properties of logs necessairy for Question 5. a*log(b) + c*log(d) = log(b^a) + log(d^c) = log((b^a)*(d^c))
Notice for question 1 that we already have all the letters in the alphabet present in the tree before you start doing any work. This means that the optimization of removal of the empty node has taken place. In short: there is no escape node present in the trees you will be looking at, the only leaves are A, B and C.
Ignore anything stated about returning a double from compress, that requirement has been removed. It was a small feature that alowed you to check your compression ratios. You shouldn't really be changing those files anyway.
This, after failing many many times to post to the newsgroup. First off, I'm the world's worst newsgroup person, I don't like them, and I barely know how to use them (don't). From what I've read in this newsgroup so far, I think people have pretty much the right idea. Slide and swap are two different things, and behave as the post described. Exchange with leader takes a node and moves it to the head (highest address) in it's equivelance class. The reason for doing this is that it makes this nodes parent also the highest in it's equivelance class and so forth, think about it to know it's true. Slide and increment should first increment the weight of a node and then slide it right (higher address) until it fits, basically a while (this > next) move over. Slide and inc returns the address of its parent, (new or old) look at the diagrams for slide and inc in section 4 of the paper. If you guys have lots of questions, I appoligise, but the newsgroup is not the best place to ask them to me. If you post to the newgroup, your classmates may respond in a timely manner, and I will try. If you have a question it would be best just to email me directly, I should be within earshot of this computer until Monday morning, exception only a few hours each evening/night. If enough people ask the same question, I'll set up a hints/clerifications section on the website, check that, and check for urgent updates also on the website. My email is whunt@cs. good luck, Warren
I will be in Taylor basement 10:30->12:00 sunday 10/2/2005 assisting anyone w/ questions, feel free to stop by.
!!! -> There is a typo in the removeZero function: this probably hasn't caused you much trouble yet, but there are cases which make it break. the lines: for ( i = 1 ; treeData[0].compareTo(treeData[i]) == 0 ; i++ ) place(i - 1, treeData[i]); the treeData[0] should be treeData[1] If you notice that treeData[1].compareTo(treeData[i]) == 0 for i = 1, we may replace these lines witht the following: place(0, treeData[1]); for ( i = 2 ; treeData[0].compareTo(treeData[i]) == 0 ; i++ ) place(i - 1, treeData[i]); sorry!
!!! Do NOT use the following IO functions: readByte, writeByte, reset or flush. readByte should be replaced w/ readBits(8) writeByte(data) should be replaced w/ writeBits(data, 8) this has to do with alignment issues in the IO streams. you have no need to call reset. Flush is called once, by the compressor, at the end of the encoding. If you call flush more often than that, you'll be outputing a bunch of padding.
If you can not get something to work, document it! Explain why you think it fails, maybe give a test case or two, show understanding of what you were supposed to do. I won't give an A for something that doesn't work, but you can still do well even if you have bugs that you haven't been able to track down yet.
!!! - The list of what you should turnin has changed a little, since you only modified AdaptiveTree (we cut parts of the project), you only have to turn in AdaptiveTree.java, readme.txt and if you changed it, Bonus.java.