Homework 3: Programs with Lists and Testing Heaps

An individual part is due Monday November 16 at noon (before class). The second part (which can be done with partners) is due Tuesday Novmber 17 11:59pm as usual. We will have separate InstructAssist submission areas for each part.

I realize the individual part will seem particularly easy for those with prior Java experience. However, there’s a bigger point to those questions which we will discuss starting on Monday. Please trust that you’re being asked to do these seemingly easy problems for a reason.

1 Individual Part: Programming with Lists

This part must be done individually, not with partners. Submit your work for this part in the "Homework 3 – Lists" assignment in InstructAssist.

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 upcoming lectures, 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 (double is the type for real numbers in Java). 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 (for "bb", "c", "dd").

  You don’t have to actually concatenate the strings to solve this, but if you want to, you can do this with +, as follows

  "go " + "goats"

Also provide an Examples class with up to four test cases for each of these two methods. We will not run either of these for throughness against broken implementations, but we are interested in seeing what cases you would choose to check within four test cases.

Submit your Planning and Examples classes either as a zip or as a single .java file.

2 Testing Functions with Multiple Correct Answers

This part may be done in pairs. Submit your work for this part in the "Homework 3 – Heap Testing" assignment in InstructAssist.

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 binary tree (in that order), and returns true if the binary tree is a valid result of adding the given integer to the first Heap. In other words, you want to fill in:

boolean addEltTester(IHeap Horig, int elt, IBinTree 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(myHeap,5,myHeap.addElt(5)),true);

}

Or, you can provide the binary tree "manually", as in:

boolean test1(Tester t) {

return t.checkExpect(addEltTester(myHeap,5,myBinTree),true);

}

where myHeap and myBinTree are data that you defined. Note that every heap is also a binary tree, so you can use addElt to generate binary trees from heaps.

Also provide remMinEltTester, which is similar (but tests remMinElt). For this, fill in

boolean remMinEltTester(IHeap Horig, IBinTree Hremoved) {

<code to compare Horig and Hremoved around as appropriate>

}

2.1 What should addEltTester and remMinEltTester actually do?

Each of these methods checks whether the binary tree is a valid result of performing addElt or remMinElt (respectively) on the original heap. A valid result is defined by the following conditions:

• The binary tree returned by each must satisfy the definition of a heap (smallest element on top, left and right subtrees both heaps).

• 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 running addElt or remMinElt on a heap does not modify the heap (this lets you reuse the same heap data in multiple test cases).

For this assignment, heaps may have duplicate elements.

2.2 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. You are getting both files because we build the heaps on top of the binary tree files.

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.

2.3 Testing the Testers

Put your test cases in an Examples class, as usual. Your test cases need only to use addEltTester and remMinEltTester. They may use addElt and remMinElt if you wish. 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.

Note that since your methods are in the HeapTester class, your Examples class will need a HeapTester object in order to call the methods. This means your test cases will look like:

class Examples {

Examples(){}

HeapTester HT = new HeapTester();

...

boolean test1(Tester t) {

return t.checkExpect(HT.addEltTester(myHeap,5,myBinTree),true);

}

}

where myHeap and myBinTree are data defined in your Examples class.

2.3.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.

2.3.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. Either delete or comment out any tests that used the TestHeap classes before you submit.