Today, we will go over how to use some of the more powerful debugger functionalities. Your job will be to debug a variety of buggy classes, primarily using a debugger.
A Review of Debugging Tools
If you're still not familiar with debuggers, please take the time to review their documentation. You have a variety of options to choose from, but the two most popular debuggers are listed below.
In IntelliJ, in addition to traditional breakpoints you can also have conditional breakpoints. Understanding how to use them will be useful for this lab.
Exercise: Debugging an Implementation of Minimax
Now we'll take a closer look at a variation of the Minimax algorithm we saw in lecture. Consider the game Top-Bottom-Draw, wherein two players take turns drawing cards from the top or bottom of a deck. Player A's goal is to maximize her total score and Player B's goal is to minimize Player A's score.
Assume both players are playing optimally and know the order of all the cards in the deck. If Player A goes first, what is the maximum score she can achieve?
Player A only has two options: take the bottom card or take the top card. Her best choice is to take the maximum(value of top card + best score on deck after Player B takes a turn on deck with top card removed, value of bottom card + best score on deck after Player B takes a turn on deck with bottom card removed). Player B is playing to minimize Player A's score, so we can assume that he takes the minimum(Player A's best score on deck with top card removed, Player A's best score on deck with bottom card removed). Do you see why? If not, discuss the problem with a neighbor and try writing out a few examples.
This is what we want to achieve, but the code in TopBottomDraw.java is not working! Use your debugger of choice to find the error.
Exercise: A Debugging Mystery
An important skill to learn is how to exhaustively debug. When done properly, debugging should allow you to rapidly narrow down where a bug might be located, even when you are debugging code you don't fully understand.
Your company, Flik Enterprises, has released a fine software library called Flik.java that is able to determine whether two Integers are the same or not.
You receive an email from someone named "Horrible Steve" who describes a problem they're having with your library:
"Dear Flik Enterprises, Your library is very bad. See the attached code. It should print out 500 but actually it's printing out 128. (attachment: HorribleSteve.java)"
Using you choice of debugger, figure out whether the bug is in Horrible Steve's code or in Flik Enterprise's library.
Once you find the bug, fix it. You might find conditional breakpoints useful for this exercise.
Exercise: SortedList™ Helper
After the embarrassing incident in the previous part, Flik Enterprises rebranded itself as Flik Enterprises Corp, and sought to clear its name by releasing a new, improved library. This library allows for easy insertion and maintenance of sorted lists -- that is, lists whose elements are sorted in increasing order.
The Flik Enterprises Corp issued a press release assuring the public that this library was 100% bug free: after all, it ships with JUnit tests, and the tests pass! However, an anonymous whistleblower involved in the development of SortedList™ Helper tells you that they fear the provided tests are incomplete, and the library isn't so bug-free after all...
1. Add statements to the
testInsertIntoSortedList test in
SortedListTester to more thoroughly the behavior of
SortedListHelper#insertIntoSortedList. Feel free to use
SortedListHelper#isListSorted in your test.
Hint: edit the
@Test annotation above your test into
@Test(timeout=1000) to impose a time limit of 1000 milliseconds on your test.
insertIntoSortedList correct? If not, find and fix the bug.
Hint: if the code is taking an unusually long time to complete, run the code in Debug mode, and click the blue 'pause' button to arbitrarily suspend the execution of your program, allowing you to more easily figure out what's taking so long.
After the demise of Flik Enterprises Corp in the previous part, you decide to leave the company and start your own software company, specializing in mathematical software.
Your first product is Plumbum|Beta, a computer algebra system (CAS) written in Java.
One of your software engineers submits an initial version of the SparseIntVector class (along with a SparseIntVectorTest) for review. To your dismay, you find that the provided tests don't pass. Note: a sparse vector is a vector (i.e. 1D ordered list of numbers) that contains very few non-zero elements.
Ignoring the fact that your engineer submitted code which clearly doesn't work, please fill in the static variables in
PlumbumBetaAnswers with your answers to the following questions as you find and fix the bugs in the code. You should only modify existing lines or replace the entire contents of a line marked
// replace this comment with something?.
- Start by running the provided test, which fails with an exception.
A. What is the name of the exception thrown?
B. Which line (in the format
SourceFile.java:239for an exception thrown on line 239 of SourceFile.java) is the exception thrown by? C. Is the line in the stack trace corresponding to the method which threw the exception on the top or bottom (of the stack trace)? Answer "top" or "bottom".
- Now fix the first bug. In one to two sentences, describe the cause of the bug.
- Run the tests again. Unfortunately, there's another bug. Find and fix this bug. A. Which line (in the same format as above) contained the bug? B. Describe the bug in a single phrase. C. Which line (in the same format as above) called the method that contained the bug? Hint: look at the stack trace thrown by the second exception.
Now, you want to add swizzling functionality to Plumbum|Beta.
Swizzling is an operation that reorders the elements of a vector (or list), given a list of indices into the list.
For example, the list
[2, 4, 6, 8, 10] may be swizzled with the list of indices
[0, 1, 2, 0, 0, 4], producing the output array
[2, 4, 6, 2, 2, 10].
i in the index arrays corresponds to an element in the output array, copying the
i-th element of the input array.
However, all of your engineers were busy, so you decided to hire an outside software firm to write the
Swizzler class for you. Unfortunately, the
Swizzler class you commissioned does not work.
Find the bug, and fix the code so that the tests pass.
Finally, you want to create a ListUtilities class for internal use. This class will provide several helpful utility methods for working on lists which will be used throughout the Plumbum|Beta codebase.
You start by creating
ListUtilities.filter, a method that takes an input list and a predicate (a function that takes a single argument and returns a boolean).
The intended functionality is for
filter to remove all of the elements from the input list that don't satisfy the predicate (that is,
predicate(element) returns false).
Despite this simple functionality (and short and simple implementation!), the
filter method is buggy.
As usual, find the bug and fix the code!
Please submit all of the Java files in the lab.