CS-2510 Lab 8

Purpose:

Equality, Random Access, and Loops.



Part 1: Equality

Remember the Bank Accounts from a few weeks ago? Lets write equality for those classes. We're going to use the "double-dispatch" technique, because it's important, and cool, and requires less boilerplate code (something always to be avoided).

Exercise 1:

Begin by recreating your Bank Accounts class hierarchy. You should have the classes somewhere, or you can rework them, but try to be efficient (time is money).

Exercise 2:

For each of the concrete classes (Checking, Savings, and Credit) design a method that compares instances of the same type.

While you're at it make these methods protected visibility, so that these methods are only visible within the classes and any subclasses. 
// In the Checking class
protected boolean sameChecking(Checking that){...}

// In the Savings class
protected boolean sameSavings(Savings that){...}

// In the Credit class
protected boolean sameCredit(Credit that){...}
Each of these should implement equality (when are they the same?).

Exercise 3:

Design the three methods in your abstract class (Account) that implement equality for the other classes, for when the types don't match: 

// In the Account class
protected boolean sameChecking(Checking that){...}
protected boolean sameSavings(Savings that){...}
protected boolean sameCredit(Credit that){...}

Exercise 4:

Now we need a public method within the abstract class that other parts of our programs can call. Give it the exact signature: 

// In the Account class
public boolean sameAccount(Account that){...}
This method will also be the default for our accounts, so it should return false.

Exercise 5:

Finally, add an implementation of sameAccount to each of the concrete classes that overrides the one inherited from Account.

Since each class knows what kind of account it is, it should call the particular 'same...' method on that account, passing itself as an argument (e..g, "I'm a checking account... are you the same as me?").

Exercise 6:

Test your sameAccount method with several different possibilities, mixing the types of accounts and where you expect both true and false results.

If you cover all the possibilities you should have at least 15 tests.



Part 2: Loops-1 (YAY!!)

Lets convert some simple recursive, accumulator-style methods into loops... We'll be writing methods over ArrayList<Integer>, then scaling it up for the next part.

Exercise 7:

Write a method that sums the numbers in a given ArrayList<Integer>. Your method should be static.

Be sure it's in recursive accumulator style!! Notice you will need two accumulators: one for the current-index, and one for the total.

Exercise 8:

Identify the following parts of your (helper) method:

  • BASE-VALUE: The starting value of any and all accumulators (index/total).
  • PREDICATE: When is the recursion/method complete?
  • CURRENT-ELEMENT: When/where do you access the current element of the collection (e.g., from the ArrayList)
  • UPDATE: Where is the accumulator updated?
  • ADVANCE: Where is the index/current-element setup for the next recursive call?

Exercise 9:

Write a new method that does the same job using a while loop. The header of the method and the BASE-VALUE become local definitions and initialization; here's a sketch you can fill in. 

int index = 0;
int acc = BASE-VALUE;
while(!PREDICATE){
    int curr = CURRENT-ELEMENT;
    acc = UPDATE;
    index = ADVANCE;
}
return acc;

Fill in those pieces and get it working.

Exercise 10:

Write the same method, but this time using a for loop. Here's a similar sketch: 

int acc = BASE-VALUE;
for(int index = 0; !PREDICATE; index = ADVANCE){
    int curr = CURRENT-ELEMENT;
    acc = UPDATE;
}
return acc;
Note the subtle semi-colons between the INIT, PREDICATE, and ADVANCE statements within the for statement.

Exercise 11:

Now it's your turn. Write a method that computes the product of a list of numbers.

Do it first with a while loop, then repeat the step with a for loop.

Exercise 12:

Unfortunately, not everything is ints, so let's mix it up.

Design a method (with a loop) that takes an ArrayList<Double> and returns a String of the numbers separated by spaces.

E.g.: 
new ArrayList<Double>(Arrays.asList(1.2, 3.4, 5.6))  --->  "1.2 3.4 5.6 "
Try it with both while and for loops.



Part 2: Loops-2 : Selection Sort

Here's a new sorting algorithm,well, new to you anyway.

Imagine you're trying to sort your friends for a picture. You want the tall people on the right, and the shorter people on the left.

So, you grab the shortest person (through a quick scan of the people), and move them all the way to the left. Now you've got one person in order, and you need to work on the others.

At any point in the algorithm we have two partitions: sorted and unsorted. At each step we select the smallest unsorted element, and swap it with the first unsorted element. Now the sorted part is one larger, and the unsorted one smaller.

We're done when the unsorted part is empty. This works nicely as a loop, since the partition always moves from left to right, one at a time. Notice also that we are mutating the list inplace; we don't produce a new list, but sort the given one.

Exercise 13:

Create an Algorithm class and design a method (minIndex) that computes the index of the minimum element in an ArrayList<Integer>, starting at a given index.

The "starting at the given index" part is the most important.

If you are comfortable, just loop-it-up! Otherwise, start with a recursive helper method, and work up to a loop.

Exercise 14:

Using your minIndex method, create a method that sorts a given list using selection algorithm.

For this you can use a loop that steps through the ArrayList, finds the minimum starting at i, then swaps that minimum into position i.

If you get stuck, create helpers for each part, and determine which part of the loop they belong to.

Exercise 15:

Test your algorithm, and make sure you understand it completely... really!

Exercise 16:

If you have extra time, convert your SpongeBob program from recursive methods into loops. We'll have something similar for HW next, so practice as much as possible.