Homework 4

Due Tuesday, April 14 at 11:59pm via Turnin. myWPI questionnaire due 45 minutes later (closing at 12:45am). Once you access the questionnaire, you will have only 30 minutes to submit your answers.

1 Testing Functions with Multiple Correct Answers

This part may be done in pairs

Our data structure functions have introduced a couple of functions that could return one of several answers: remElt on BSTs has this property, as do the addElt and remMinElt functions on heaps.

Writing test cases for such functions clearly requires more than writing a specific, concrete answer (as you are used to doing). Instead of writing a concrete answer, you have to write a function that checks whether your answer is correct, and run that function within your test case. In other words, rather than checking whether you got _the_ correct answer, you have to check whether you got _a_ correct answer. This assignment is teaching you how to write tests situations when you need "_a_ correct answer".

Your job here is to write two functions: addEltTester takes a heap, an integer, and a heap, and returns true if the second Heap is a valid result of adding the given integer to the first Heap. In other words, you want to fill in:

[Revised Saturday Apr 11, 7:30pm]

boolean addEltTester(Heap Horig, int elt, Heap Hadded) {

<code to compare Horig and Hadded around elt as appropriate>

}

You can use this to test a given addElt implementation by writing a test such as:

boolean test1(Tester t) {

t.checkExpect(addEltTester(H1,5,H1.addElt(5)),true);

}

Or, you can provide the second Heap "manually", as in:

boolean test1(Tester t) {

t.checkExpect(addEltTester(H1,5,H2),true);

}

where H1 and H2 are example heaps that you defined.

[Revisions end here]

remMinEltTester is similar (but tests remMinElt). The idea here is that you capture the requirements of a correct answer in a function, then call that function to check whether the function you are testing produces a correct answer.

The behavior of the required functions (and hence what your tester must confirm) is as follows:

• The binary tree returned by each must be a heap.

• addElt must retain all elements that were in the original heap, while adding only the new element one time.

• remMinElt must retain all elements that were in the original heap other than removing one occurrence of the smallest element.

You may assume that the heap operations do not modify the input heap. Heaps may have duplicate elements.

1.1 Logistics

Put both of these methods in a new class called HeapTester.

You do not need to implement addElt or remMinElt. We are giving them to you. Here are both a binary tree implementation and an initial correct heap implementation to use in writing your tester.

If you need additional methods on Heaps or BinTrees, modify the classes in these files as needed with your additional methods. Please do not change the names of the classes or make your own subclasses (that will break our testing). Just edit these classes and/or interfaces.

Exceptions are not required.

1.2 Testing the Testers

Put your test cases in an Examples class, as usual. Your test cases need only to use addEltTester and remMinEltTester. Limit yourself to no more than six (6) tests for each of these methods. Your job is to check as well as you can within 6 tests per method.

1.2.1 What Makes for Good Tests?

Good tests will capture various ways that addElt and remMinElt might fail. Here’s another way to think about it. If you have a good addEltTester, then your tests will all pass if you use a correct implementation of addElt. If you use a broken implementation of hasElt, then ideally one of your test cases would fail (because the addElt used inside addELtTester would produce the wrong answer).

Put differently, assume you wanted to add 8 to the following heap:

4

/

5

Imagine that the addElt code you were using returned

8

/ \

4   5

(which is wrong because it isn’t a heap [with min elts on top, as we are using here]). Then your addEltTester would return false, because the produced heap is not a valid answer when adding 8 to the original heap. A good set of test cases here, then, will cover different elements to add to different configurations of heaps, looking for ways in which addElt might go wrong.

1.2.2 Checking on bad heaps

If you want to see whether your tester is detecting bad implementations of the Heap operations, you can use this Java file file (put it in your directory). It contains several incorrect heap implementations (each a separate class that extends DataHeap). You can build a broken heap doing something like

The tests in your final Examples class should just be written using DataHeap, not these broken implementations. The broken implementations are just to help you in checking your work.

2 Programs That Do More Than Traverse Data

This part must be done individually. Submit your java file for this problem as a solo in Turnin (which you can do even if you submit part 1 under a pair).

Up until now, all of the programs you have had to write (here and in CS1101 if you took it) needed a straightforward traversal of the input data (in CS1101 terms, they followed the templates). Often, we need to write programs that combine multiple tasks on the same data. Then we have to think about how to organize the code. This organizational task is called planning.

For this part of the assignment, we’re asking you to write two programs that involve multiple tasks. We will use these to set up lectures for later next week, so the goal is for you to think about how to do this, as much as to produce code. These will be graded on the correctness of answers that they produce.

Create a class called Planning and put both of the following methods in that class.

• Write a program called rainfall that consumes a LinkedList<Double> representing daily rainfall readings. The list may contain the number -999 indicating the end of the data of interest. Produce the average of the non-negative values in the list up to the first -999 (if it shows up). There may be negative numbers other than -999 in the list (representing faulty readings). If you cannot compute the average for whatever reason, return -1.

  For example, given a list containing (1, -2, 5, -999, 8), the program would return 3.

• Write a program called maxTripleLength that consumes a LinkedList<String> and produces the length of the longest concatenation of three consecutive elements. Assume the input contains at least three strings.

  For example, given a list containing ("a", "bb", "c", "dd"), the program would return 5.

Just above each method, we also want you to provide a comment containing up to four lists that you think are good for testing it. We are not asking you to submit formal test cases (because then you would have two Examples classes for this assignment, which will cause confusion). You should still test your code (we will), but all we want to see are the input lists you think are interesting to use here. Your comment can take the form:

/* Inputs for Testing

* List 1 : [5, 9, 2]

* List 2 : [0, 1, 0]

*/