What was the question
 

The question is long so I will sumarize. There are 4 questions on the test and the test booklet is 16 pages long just to give you an idea.
The kids are talking about part b of the fourth question on the AB exam. There is an A exam and an AB exam. The AB covers a lot more matterial than the A exam.

In any case. The method CharToBitsHelper for the CodeTree class returns a binary representation of the the path to a specific letter in a binary tree of letters. Taking the left branch is indicated by a 0 and takingthe right branch is indicated by a 1. So if you take a left and two rights to find the letter CharToBitsHelp returns "011".

The actual method prototype (I have it in front of me) is

apstring CodeTree::CharToBitsHelper(char ch, Node * T, const apstring & pathSoFar) const
// postcondition: if ch is in subtree T, return code for ch

I'll post my solution shortly. I want to read part A before I start.

my solution
 

Node * Temp = T; // Pointer to use for traversal
apstring rtn = ""; // Return string

while (Temp != null && Temp.letter != ch)
{
if ( ch > Temp.Letter)
{
rtn += "1";
Temp = Temp->right;
}
else
{
rtn += 0;
Temp = Temp->left;
}
}
if (Temp.letter == ch)
return rtn;
else
return "";

The last bit is importent because you have to handle the case where the char is not found in the tree. My guess is that you will lose at least one point (of 4/5 for part b) if you leave that out.
You will probably also lose a point if you did not create your own temp pointer for the traversal. But that's just a guess.

my school must really suck, because there's only Visual Basic here for programming, and there are absolutely NO AP computer courses, I wish though.

VB
 

Visual Basic is a great language. But I'm biased as our school uses a VB text book I wrote. :)

BTW I think there is a problem with my solution to the AP question. I realized that there isn't a letter in the nodes only the leaves. So you have to recursively search each path and return the one that is good. A whole different set of code. Back to the drawing board.

Basically, they constructed a huffman encoding tree, and they asked us to write a function, that given a letter and the tree (and a third argument, string_so_far, which is initially empty), we return the path to that letter. Of course, them being the ap people, they don't expect us 'dumb' kids to know what huffman encoding is, so they never actually called it huffman encoding, and they gave us hints in the question in how to answer it (like 'we suggest you use string_so_far in a recursive algoritm ...').

Oh, and yep, Mr. Thompson, you're right, the letters are only in the leaves. You can look at my solution or Rucky G's solution for a right anser. The only difference between ours is that I check to see if the letter is found in the left subtree before I look in the right subtree, he looks in every node of the tree in all cases. So, mine is more effecient, but I think his looks more elegant, since he takes advantage of the fact that if the letter is not found, he returns the empty string, and thus can be appended to the answer without changing it.

Stephen

IMO, I did well enough to get a four on the comp sci A exam, and should I have done miraculously well on the part I, I might even have pulled a five. However, my answer to the case study part II would probably cause me to lose a few points here and there.

See, I looked at the fish maybe, uh, once, so I had no clue and knew as much going into the test. So my answer for #3 was to define 527 different variables.

You never know, I could always get a partial credit point or something maybe.... :rolleyes:

That's not going to work either because the tree is not set up so that the letters go to the left or right because they're greater or less than. It was a random set up from the beginning, otherwise the encryption would be very easy to hack.

Yeah I realized that after I posted. Sloppy work on my part. What can I say, it's been a long year. For people who are interested in good solutions there is a set at http://cs.colgate.edu/APCSWeb/APCSDo...eResp2000.html that is very good. How good? Well the guy who wrote them tells the graders what to accept and what not to accept.

I suppose it could be a random setup, but that's not most likely. Usually, in huffman encoding schemes, the most commonly used letter would have the shortest path, the second most commonly used letter would have the second shortest path, and so on. It is not used as a secure encryption method, but rather it is used to map letters into binary representations a computer can understand. In ascii, all leters are 8 bits, even if 7 of them are 0s, it still takes up a whole byte, while in huffman encoding, the length varies in each letter, which usually results in a shorter file.

Stephen