Homework 4 Clarifications

Last updated Sun 2-10-2013

Problem 1

• For b and e, give your recurrence relation as we have done elsewhere in the course, in terms of n. So T(n) = .... where n refers to solving a problem of size n.

Problem 3

• The Iterator just "magically" gives you an Integer out of thin air - you do not get to use any memory "vacated" by the value given to you by the iterator. You are NOT allowed to go through the iterator more than once - you are only presented each value once.
• You only get 2MB memory TOTAL.
• If you want to precisely calculate the size of structures used in your solution (which you do want to do) I would recommend using Java primitives whose size is precisely defined - e.g. byte, short, int.
• You may assume that phone numbers will not start with 0, although they may contain zeroes otherwise.
• Here is some info on bitwise operators.
• Here is another ref this page with more info on bit-wise operators - please feel free to post links to others you find helpful on the message board.
• For those who did Huffman coding in cse143, that may have been the closest time you were directly exposed to thinking about the underlying representation of data types in Java. For this question, the point is that bitwise operators allow you to act as if you have a "bit" data type in Java. You can use the bitwise operators to set and read individual bits. We cannot directly declare an array of bits, but we can declare an array of another Java primitive type whose size we know: int (32 bits), short (16 bits), byte (8 bits), and this gives a way to be sure of how much memory we are using. We can then use bitwise operators to treat the memory we have allocated as if it were an array of bits.
• You should *NOT* use the Java BitSet class for this problem. It simplifies the problem a bit(ha!) too much - and does not give us the level of control about data size that we want to really know about. This is kind of like how we also avoid using things from the java collections in implementations of our projects. So using BitSet will not be a full credit answer (it would be a partial credit answer).
• If you run out of time and cannot understand how to do the problem using actual Java primitive types then I would suggest just doing the problem assuming that you can create arrays of bits, and come up with a solution that will work for that. This will NOT be a full credit answer, but it will be a partial credit answer.
• An approach that used math calculations rather than bit manipulations is also o.k. - the main point is not to assume that you have an array of bits than can be indexed directly - you need to make use of primitive Java data types whose size we know. The smallest of these is a byte (8 bits) but you can also use ints (32 bits).

Problem 4

• You are NOT being asked to sort only the first "enough" elements (and ignore the rest of the contents of the array). You are being asked to find the smallest "enough" values and place them in the first "enough" locations in the array. For example, if you are passed enough=5, then you should find the 5 smallest values in the array, and place them in locations 0-4 of the array.