Computer Science 15-111 (Sections A & B), Spring 2007

Homework #3 (part 2)

Due: Mon 29-Jan-2007 at 8pm (online submission).

Place the written portions of the following problems in the file “hw3-written.txt” in your online submission of hw3.2.zip. Remember: Show your work!

1. The version of WordSearch.java that we wrote in class used an ArrayList<String> as the representation of the board. This was useful since we did not know ahead of time how many rows to read in (and, hence, how large an array to allocate). But this also complicated other parts of our code – specifically, accessing characters in the board. It would be more natural (hence, preferable) to store the board as a two-dimensional array of char’s, as in:
char[][] board;
Write a program, WordSearch1.java, that does just that. It still reads in the input using an ArrayList<String>, but then it converts that input to a 2d array of chars once you know the appropriate dimensions to use. Modify the code to use this representation of a board. Also, make the printed report nicer by printing human-readable directions (“Up”, “Up-Left”, “Down-Right”, etc) rather than (drow,dcol) when matches are found. Finally, add a few more well-chosen comments and be sure to generally study the code and understand how every aspect of it works.

2. Write a program, WrappingWordSearch.java, that is a modification of your WordSearch1.java program. Here, you should not fail as you run off the board during a match. Rather, you should wraparound. So, for example, the following board would contain the words DOG and CAT with wraparound:

O D X C G
T X X X X
X X X X A

DOG at 0,1 heading LEFT
CAT at 0,3 heading UP-RIGHT

3. Carefully read Appendix A.3 on manipulating bits. Then confirm each of the following by converting the arguments to signed int’s (32-bit 2’s complement), performing the operation, and converting the answer back into decimal.

a. First we consider bitwise and (&), or (|), xor (^), and not (~):
(17 & 5) == 1
(17 | 5 ) == 21
(17 ^ 5 ) == 20
~17 == -18
~17 + 1 == -17 (we expected this – negation in 2’s complement!)

b. Ignoring overflow, left-shifting is the same as multiplying by powers of 2 (why?), and right-shifting positive numbers is the same as dividing by powers of 2 (again, why?). To demonstrate this, confirm the following:
(-5 << 3) == -40 (which equals -5 * 2³)
(87 >> 4) == 5 (which equals 87 / 2⁴)

c. Right-shifting negative numbers, though, whether sign-extended (a >> b) or not (a >>> b), is not the same as dividing by powers of 2. To demonstrate this, confirm the following:
(-87 >> 4) == -6 (which does not equal -87 / 2⁴)
(-87 >>> 4) is positive (and very large!)

d. As discussed in class, we combine shifting and bitwise operators to get and set bytes from within int’s. For example, we can obtain the second byte of an int by first shifting 8 bits to the right (thus moving our target bits into the lowest byte) then &’ing against the mask 0xFF to set all the bits except the lowest byte to 0 (how does it do this?). That is:
int secondByte = (x >> 8) & 0xFF;
Now, a nibble is half a byte (cute, huh?), or 4 bits. It is represented by a single hex digit, as in 0xF. A 32-bit integer contains 4 bytes and so it contains 8 nibbles. Write an expression (not a statement, just an expression, like the one above for finding the second byte) that uses shifting and &’ing to get the kth nibble (where the least-significant 4 bits are the 0^th nibble, the most-significant 4 bits are the 7^th nibble, and you can presume k is in [0,7]). You may use a Java compiler to check your work along with this (not very stylistic) sample code (which, of course, you are expected to fully understand, too!):

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String hexDigits = "0123456789ABCDEF";
int x;
while (true) {
System.out.print("Enter an int (or 'quit' to exit): ");
if (!scanner.hasNextInt()) {
if (scanner.next().equals("quit")) break;
else { System.out.println("Huh?"); continue; }
}
x = scanner.nextInt();
// Print the hexadecimal value of x using kth-nibble
System.out.printf("%d = 0x",x);
for (int k=7; k>=0; k--) {
int kthNibbleOfx = (YOUR EXPRESSION GOES HERE);
if ((kthNibbleOfx < 0) || (kthNibbleOfx > 15))
System.out.println("\nkthNibbleOfx out of range!");
else
System.out.print(hexDigits.charAt(kthNibbleOfx));
}
System.out.println();
}
}

Finally, study the code in PixelImages.java (which we covered briefly in class) which uses bit operations to get and set bytes within an ARGB (Alpha-Red-Green-Blue) integer. You are responsible for that code, too!

4. To further help you in your study of bit manipulations, here is a program, BitQuiz.java, that generates problems using random arguments and randomly-chosen operators from { &, |, ^, ~, <<, >>, >>> }. First, compile the code and use it to practice (since you do need to know how to do bit manipulations by hand!). Then, study the code itself, since you are responsible for all of it. Answer the following questions:

a. What does random.nextInt(n) return?

b. Why can’t we use a switch statement to select the operator in the “eval()” method? That is, what is wrong with this code:
switch (operator) {
case "&": return (arg1 & arg2);
case "|": return (arg1 | arg2);
// ... //
default: System.out.println("oops"); return 0;
}

c. Why do we need the “+ 1” in this code:
int arg1 = min + (random.nextInt(max - min + 1));

d. Consider the line:
int result = (byte)eval(arg1,operator,arg2);
Give specific values for arg1, operator, and arg2 where the value of result would differ if the cast to byte were not present.

5. In class, we briefly reviewed code to display pixels. Here is an updated version of that code: PixelImages.java. First, compile and run the code. Then, study the code itself, since you are responsible for the first half of the file. Answer the following questions:

a. Read Sections 6.1 and 6.2 then, in just a few words, briefly describe an advantage of declaring FadeType as an enum, rather than declaring each enum element as a static int, such as:
public static int HORIZONTAL_FADE = 1;
public static int VERTICAL_FADE = 2;
…

b. Note that this code uses (x,y) notation which is typical for graphics rather than the (row,col) notation which is typical for matrices (even though both use 2d arrays!). For example, we used (row,col) notation in WordSearch.java. Confusing these two approaches is quite common and leads to many errors. In (row,col), the first dimension is the vertical dimension (rows go up-and-down), whereas in (x,y) the first dimension is clearly the horizontal direction. Either way, for most programming tasks, we conventionally place (0,0) in the top left (unlike graphing in math, where it is usually in the lower left). There is nothing to submit for this part of the question, just be sure you understand it.

c. Write the following method:
public static void fillCircle(int[][] pixels,
int cx, int cy, int radius,
int alpha,
int red, int green, int blue)
This method should fill in a circle of the given color centered at (cx,cy) with the given radius. While it is possible to do this with trigonometry, there is an easier way. Just iterate over the pixels in the enclosing square, as in fillRect, and for each point (x,y) simply check if the distance from that point to (cx,cy) is less than or equal to the radius. If so, fill the pixel in, otherwise skip it. Test your method by adding a filled yellow circle with radius 50 placed against the lower-right corner of the picture. (Note: yellow is red + green with no blue.)

d. Write the following method:
public static void removeRed(int[][] pixels,
int left, int top,
int width, int height)
This method removes all the red from the pixels in the given rectangle (that is, sets the red component of the ARGB to 0x0), leaving the alpha, blue, and green unmodified. Note that there are methods in the code to get the color components (alpha, red, green, blue) at a given pixel. Demonstrate your code works by calling removeRed on the left half of the yellow circle drawn above, and seeing that half turn green (since yellow is red plus green, removing red leaves just green).

6. BONUS: This is optional but strongly encouraged. Unlike extra credit which is factored in at the end of the semester, bonus is factored immediately into your grade on this assignment (thus allowing scores over 100). But, again, it is entirely optional, and not doing the bonus will in no way detract from your score.

a. [2.5 pts] Modify the fadeValue() method so that it supports a RADIAL_FADE, where value0 is the value at the center and value1 is the value at the edges of the rectangle. To make this easier, it is ok to assume that the rectangular is a square, and to use the smaller rectangular dimension as the square’s side. Then, find the distance from (x,y) to the center, and divide this by the radius. That is the fraction of the fade that should occur, right? Anyhow, test your method by adding a 75x75 square, radially fading from blue to red, in the top-right corner of the picture.

b. [2.5 pts] Add a method fillOval which works like fillRect but instead fills in only the oval that fits inside the enclosing rectangle. In a clear and concise comment at the head of your method, explain the math behind your approach.