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

Homework #4.2

Due: Mon 5-Feb-2007 at 8:00pm (online submission).

Place these programs in hw4.2.zip. Remember to just submit your .java files, and not your .class files, random .jpg files, or miscellaneous Eclipse or other IDE-related files.

1. Gaussian Elimination with Partial Pivoting
(This is a verbose question, but with very little code to write in the end. –DK)

In class, we wrote a simple version of GaussianElimination.java. First, carefully review the lecture notes (which describe how the algorithm works) and then study the code – you are responsible for it!

While this code is useful for learning purposes, it is not a very good solver of linear systems of equations. For example, it is easy enough to make it crash by giving it an unsolvable system:

// Unsolvable system (two parallel lines)
private static double[][] unsolvableSample = {
{ 1, 1, 1 }, // x + y = 1
{ 1, 1, 2 } // x + y = 2 (these lines are parallel)
};
When our solver runs on this example, it produces the “solution”:
x = -Infinity
y = Infinity

Not a good situation! But it is perhaps tolerable because we at least are dealing with an unsolvable system (though it would be nice to handle this case more deftly than we presently do!). Here, however, we’ll consider a worse flaw.

Consider the following system:
private static double[][] thisWorks = {
// x = 3, y = 2, z = 1
{ 4, 0, 3, 15 }, // 4x + 0y + 3z = 15
{ 0, 1, 2, 4 }, // 0x + 1y + 2z = 4
{ 5, 6, 0, 27 } // 5x + 6y + 0z = 27
};

Our program handles this system just fine. Great! Unfortunately, what happens if we simply rearrange the first two equations? Naturally, this does not change the problem at all, so we should expect the same answer. Well, try it. Start with this:

private static double[][] thisFails = {
// x = 3, y = 2, z = 1
{ 0, 1, 2, 4 }, // 0x + 1y + 2z = 4
{ 4, 0, 3, 15 }, // 4x + 0y + 3z = 15
{ 5, 6, 0, 27 } // 5x + 6y + 0z = 27
};

And when you run it, you see that something went terribly wrong, and our answer is that x, y, and z all equal NaN (“Not A Number”). Yikes!

What happened? Well, the first thing our solver does is try to place a “1” in the first coefficient of the first equation (that is, in c[0][0]). It does this by dividing the first equation by whatever value is there. This is done in this code:
// 1. set c[row][row] equal to 1
double factor = c[row][row];
for (int col=0; col<cols; col++)
c[row][col] /= factor;
But what happens if “factor” is zero (0) – which is precisely the case here (see the 0 in the top-left corner of our array)? Then we divide by zero! If the division were integer division, our program would throw an exception and crash right there. But since it is double division, instead the answer is NaN (“Not A Number”) and the computation proceeds despite being hopelessly broken.

Your task is to fix this problem, at least for most cases. To do this, copy GaussianElimination.java to a new file, GaussianWithPartialPivoting.java. In that file, you will implement partial pivoting.

What is Partial Pivoting?

As we just observed, when the element on the diagonal is a 0, we cannot divide to make it equal 1. In this case, we find the first non-zero element in the same column but below this element (so, in a higher row, since rows increase as we move down), and then we swap the two rows (so we are pivoting about this element). This places a non-zero element on the diagonal so we can continue our algorithm. Interestingly, if there is no non-zero element below the offending diagonal element, then we are in an unsolvable case (either there are no solutions, as with parallel lines, or there are infinitely many solutions, as when solving two lines that are in fact the same line). So you can print out a reasonable message in this case, rather than continue “solving” the unsolvable system.

In the example above, your code would see that c[0][0] equals 0, and would search downwards, noting that c[1][0] equals 4, and so would swap rows 0 and 1, which produces a solvable problem (we know this since we solved it above!).

Remember that we do not use == for doubles (why not?), so you cannot have code that reads:
if (factor == 0) …
Instead, you have to test if factor is very nearly zero. That is, if its absolute value (Math.abs) is less than some value epsilon, which should be a very small number (how small? 10^-10? 10^-20? You decide!).

Demonstrate that your partial pivoting code works on the example above, and provide another example where the original code fails and the partial pivoting code succeeds, but where the failure does not occur in the first column (as it did here) but in a subsequent column during the solution process. Include this example in your solution.

2. Bullseye!
Starting from BasicGUI.java, write a program, BullseyeApp.java, that draws the following bullseye pattern:


Your BullseyeApp should extend IntroCsApplication, and it should create an instance of Bullseye, that extends IntroCsComponent, as such:

public class BullseyeApp extends IntroCsApplication {
public static void main(String[] args) { new BullseyeApp(); }
public void init() {
add(new Bullseye());
}
}

class Bullseye extends IntroCsComponent {
// your code goes here!
}

Note that this pattern must abide by the following:

a. It must be enclosed in a blue square.

b. It must have 5 concentric circles, alternating red and black, with the innermost circle being red, with the outermost circle exactly fitting inside the square, and each consecutive circle’s radius different by a constant.

c. The square must be centered in the window at all times (even after resizes).

d. The square’s side changes with resizes. To find the square’s side length S:
A = the lesser of the window’s width and its height
B = the smaller of 250 and A/2
S = the smallest multiple of 10 at least as large as B
(Thought question: why is it convenient for the square’s side length to be a multiple of 10?)

3. Drag and Resize
Starting from BasicGUI.java, write a program, DragAndResizeApp.java, that draws a simple 50x100 orange rectangle originally placed at (10,10), and has two buttons, “Drag” and “Resize”, as such:


Remember to use “addButtons()” to add the buttons! These buttons switch between Drag mode and Resize mode, where the application starts by default in Drag mode.

In Drag Mode:

When in Drag Mode, mouse presses inside the rectangle will begin a “drag” operation, where the rectangle moves with the mouse and stops moving at the mouse up.

Note #1: Mouse presses outside the rectangle have no effect. Do not start a drag operation in this case!

Note #2: You must keep the mouse positioned in the same part of the rectangle throughout this operation. So if the user clicks in the lower-right corner of the rectangle, for example, the mouse will remain in the lower-right corner of the rectangle throughout the drag operation.

Note #3: At least 10 pixels of each dimension of the rectangle must always stay in the window during a drag. So as you move off the right edge, for instance, the left of the rectangle cannot exceed (window’s width – 10). Also, for example, as you move off the top edge (heading up), the bottom edge (not the top edge!) of the rectangle cannot be less than 10.

In Resize Mode:

When in Resize Mode, mouse presses within 5 pixels in each dimension from any corner of the rectangle will begin a “resize” operation, where that corner of the rectangle moves with the mouse (with the opposite corner never moving) and stops resizing at the mouse up.

Note #1: Mouse presses beyond 5 pixels in either dimension from a corner have no effect.

Note #2: Do not resize either dimension of the rectangle to less than 10 pixels, and do not “flip” the rectangle if the user drags beyond the opposite corner.

Note #3: Do not resize the rectangle beyond the visible portion of the window. Note that it is possible that a rectangle is already partly offscreen (due to a prior drag) at the start of a resize. This is ok, and that portion of the rectangle will remain offscreen throughout the resize.

4. Simple Game
Again starting from BasicGUI.java, write SimpleGame.java, which is (not surprisingly) a simple game. There is a ball that moves (on a timer) back and forth across the top of the window. There is a paddle that moves in response to left and right arrows back and forth across the bottom of the window. When the user hits the space bar, a projectile is fired up the screen towards the ball. If it hits the ball, the user scores points, and if it misses, the user loses points. Show the points at all times. Have the user win or lose at reasonable times. Clicking with the mouse anywhere at any time will start the game over.

This game is underspecified. Even in such a simple game, there are plenty of decisions you need to make. Make good ones! You will be graded on correctness (matching the description above), but also on how nice your Graphical User Interface (GUI) is, as well as how stylistic your code is. Don’t go too overboard, though, since you should save your energy for the bonus, time and interest permitting!

5. Little Bonus (up to 5 points, or ½ letter grade): Pong
Make a game of Pong, where you play an air-hockey-like paddle game against a computer opponent. How does Pong work? It’s easy to find sample Pong applets on the web (for a randomly-chosen example, try: http://www.xnet.se/javaTest/jPong/jPong.html). Note: as will be the case with many of our assignments, it is also easy enough to find actual source code on the web for Pong. Remember the course policy: if you are to submit a Pong program for this course, then you may not look at Pong source code until after you have submitted your own code! In any case, this is meant as a “little bonus”, so don’t make the problem too hard.

6. Big Bonus (up to 10 points, or one full letter grade): NxN Tic-Tac-Toe
You have everything you need to write a decent tic-tac-toe game. Start with a 3x3 game. Users should take turns, and they should click where they want to move. Your code should determine when there is a win or a tie and display a message for a short while then restart the next game. Always display the score, too. Also, have a few buttons: “larger”, “smaller”, and “reset”. Larger and smaller should change the size of the board while always keeping it square. Each time you click “larger”, the board size should increase by 1 in each dimension (3x3 to 4x4, then 4x4 to 5x5, etc). Smaller does this in reverse. Don’t allow boards smaller than 3x3 or larger than 10x10. Finally, you should pick an interesting rule for how to win an NxN game, since 3-in-a-row is too easy for, say, 6-by-6, but 6-in-a-row may be too hard. You decide. Have fun with this!