THE PROJECT FOR PROBLEM 3 ALSO CONTAINS THE CODE FOR PROBLEM 4.  

There are many, many techniques for sorting lists of data.   In this problem we will look at a modification of a the popular "Selection Sort" technique.    In a nutshell, selection sorting is the process one goes through to pick a basketball team by going to a group of people and picking out your players in order by their height.   Selection sorting is a relatively simple algorithm that is fast and efficient for small data sets, but is generally too slow for large data sets. 

We will write an IAlgo algorithm called SelectSort that will mutate an unsorted LRStruct into a sorted list using the described selection sort algorithm.

In overview,  the algorithm is as such:

1. Find where the minimum value, as determined by a supplied Comparator, is located in the list.

2. Remove and temporarily save that minimum value.

3. Sort the remaining list.

4. Insert that minimum value at the beginning of the list

5. Return the original, now mutated, host list.

Forward accumulation is a classic technique for finding the minimum value in a list so we will use it here.   A skeleton of the code to do the forward accumulation has been provided.

As soon as  the empty case of the forward accumulation process is encountered, the location of the minimum value will be known.   It is at this point that steps 2-5 above can now be performed. 

More information about the details of the algorithm can be found in the supplied Javadocs in the  SelectSort class.   

Problem 3.a.  Inductive case (5 pts)

Write the inductive case of the forward accumulating helper of the SelectSort algorithm.

 Problem 3.b.  Base case (10 pts)

Write the base case of the forward accumulating helper of the SelectSort algorithm.

THE CODE FOR PROBLEM 4 CAN BE FOUND IN THE SAME PROJECT AS PROBLEM 3.

Experimental data often comes as a long list of values.   These real-world data points usually exhibit some level of "noise" or randomness due simply to natural causes or are artifacts of the experimental procedure.   To see the underlying trends represented by the experimental data, it is almost always necessary to perform some sort of averaging or "smoothing" procedure to the data to reduce the noise level on the signals.   One of the classic techniques is the "sliding window" method, where the raw data values are replaced by the average value over some "window" of values, usually those preceding that data value.  

A window size of 5 would mean that any given value would be replaced by the average of the last 5 values (inclusive of the current given value).   A window size of 20 would mean replacing every value with the average of the last 20 values.   Clearly, the larger the window, the greater the ability to average out any variations in the data.   A window size of 1 would mean no smoothing at all.   If the window size is too large, then it can actually wipe out any trends or changes that the experimenter is trying to see, so it is important to be able to adjust the window size to match the situation at hand. 

To see the effect of sliding window smoothing, examine the graph below.   In the graph, the raw data is the zigzag blue line with the individual values shown at each data point.  Two different window sizes are shown, one is 4 data points wide and the other is 8 data points wide.  The red sinusoidal-looking line with the square data points is the averages computed using the 4-point window while the green line with the triangular data points is averages computed using the 8-point window.   Imagine the window sliding across the data from left to right, computing the average value of the raw data points within the window at any given moment.  The calculations are show for the windows at their displayed location in the data.    Note that the average is computed for all the raw data points preceding the smoothed data point, including the raw data point at the same location as the smoothed data point.

See how the bigger window size produces a much greater smoothing effect.   If the experimenter wanted to see the up-and-down variance in the data, the 8-point window would probably be too much smoothing. 

One problem with sliding window smoothing is starting the off at the beginning of the list of raw data points.  There aren't enough points yet to fill the window, so the average has to be calculated for only those values that have been encountered so far.   That's why the 4-point and 8-point window lines above match each other for the first 4 data points.  The first smoothed point is just the raw value because there's nothing to average.   The second is the average of the first two, the third the average of the first 3, etc. until the window size is reached and the window can begin to slide along.

So, how do we go about creating an algorithm that performs the sliding window smoothing?   The first thing we need to do is to represent the sliding window itself.   We need a data structure that can hold all the raw data values within the bounds of the window, but easily allow us to add the newly encountered values we slide along but also to easily discard the values that have fallen off the back end of the window.

A beautiful data structure that works very well for this purpose is the "ring buffer" or "doubly-linked circular list".   Fundamentally, a ring buffer is a circular list that has links in both directions, not just in one as in all the lists we have worked with so far.  Think of the circular list as a regular list where the end of the list has been pulled around and is right next to the beginning of the list.  With the two-way navigation capability, we can work down the list as normal, or go backwards and in one step, go from the very beginning of the list to the very end of the list.    This will be most useful, because we will want to add the new data values into the beginning of the list, but remove the old values from the end of the list.  

As in the spirit of LRStruct, to make a mutable ring buffer, we encapsulate the entire ring structure behind an encapsulation barrier.   This gives us full and unfettered control over what happens to the ring.  The user only sees the encapsulating RingBuffer class, and has no access to the actual ring "nodes" behind the scenes.  At any given moment, only one of the nodes is directly accessible and hence only one of the pieces of stored data can be accessed (a "first" as it were).  The doubly-linked nature means that in effect, there are two "rests" that can be used to access the rest of the ring.  We will call the two directions "next" and "prev" (previous).   It is useful to equate "next" with the traditional forward direction of "rest" and "prev" as going backwards through the list.

There are only a few operations of the ring buffer that are of interest here (see the diagrams below for reference):

• RingBuffer.getFirst():  Returns the value stored in the currently accessible ring node.

• RingBuffer.insertFront(Object data): Mutates the ring by inserting the supplied data value in the next direction.   This is exactly analogous to LRStruct.insertFront(Object data).   The inserted data becomes the new first and the ring grows larger   See the diagram below to see which way the inserted data moves in the ring (clockwise).   This method is thus the exact opposite of removeFront.

•  RingBuffer.removeFront(): Mutates the ring by removing the current first value and moving in the first value from next direction.   This is exactly analogous to LRStruct.removeFront().   The inserted next's first becomes the new first and the ring gets smaller.   This method is thus the exact opposite of insertFront.

• RingBuffer.toNext():  Rotates the ring, without mutating the ring itself, from the direction of next.   That is, the node at next becomes the new accessible node.  In the diagram below, the ring would spin counterclockwise.

• RingBuffer.toPrev():  Rotates the ring, without mutating the ring itself, from the direction of prev.   That is, the node at prev becomes the new accessible node.  In the diagram below, the ring would spin clockwise

• RingBuffer.getCount():  A convenience method the returns the the number of nodes in the ring.   Since RingBuffer has complete control over all access to the ring itself, the count can be easily maintained simply by adding or subtracting 1 every time insertFront or removeFront is called, respectively, without having to traverse the actual ring.

So all we need to do to simulate our sliding window is to insert the new values and then with a quick rotation via a toPrev() call and a removeFront(), we can discard the oldest values in the window!  Note that this removal process will also automatically return us to the beginning of this list (oh, yes!).

And here are the magic words you've been waiting for:  The entire RingBuffer implementation has been supplied to you.

We will write an IAlgo algorithm called SmoothingAlgo that will mutate a given LRStruct by averaging the values as per a given sliding window size using a ring buffer.

The SmoothingAlgo visitor is defined as mutating the host list to have the smoothed values in it as per a sliding window whose size is determined by a given integer input parameter.

At first glance, in order to calculate the average value, it would look like we would need to go through the entire ring buffer adding all the elements together and then dividing by the ring's count.  But there's a much faster, simpler way!  

Remember that when one is trying to calculate the average value to replace any given raw data value, all of the previous average values in the list have already been calculated.   In particular, look at the immediate prior average value. If the window is N elements long, then that average value is the sum of the N raw data values preceding and including the raw data value that was at that position.    But that average is just the sum of all those values divided by N.   If we multiply that previous average value by N, we will retrieve the total sum of the raw data values, or we simply pass forward the current total sum as we recur through the list.

But now look at the average value we are currently trying to calculate:   It is just the sum of the N raw data values preceding and including the raw data value that was at this position.   Let's compare the total sum required here with the total sum used in the previous data element.  What's the difference?  

The difference between the total sum used to calculate the previous average value and the total sum used to calculate the current average value is that the previous total sum includes the raw data value from N positions before, while the current total does not include that value, but it does include the current raw data value.  

That is, when trying to calculate the total sum for the i'th data element we have, where the x's are the raw data elements,

Previous total sum:   Total_sum_i-1 =  x_i-N +  x_i-N+1 +...+  x_i-2 +  x_i-1

Current total sum:  Total_sum_i =  x_i-N+1 +  x_i-N+2 +...+  x_i-1 +  x_i  =  Total_sum_i-1  -  x_i-N  +  x_i

But the raw data value from N positions before (x_i-N) is just the last element in our ring buffer.   All we have to do is remove that last value from the ring, subtract if off of the previous total sum, add our current raw value to that sum (as well as insert it into the ring) and divide by N!   All we need are a couple of simple arithmetic operations that are completely independent of the size of the sliding window and do not require that that we look at anything but the last element in the ring.   Gotta love it.

And the kicker is that even at the beginning of the list, when the window isn't full yet, the count of the ring will always give us the correct value of N to divide the total sums by. 

What we are seeing is the fact that the proper choice of data structures to use can have a tremendous impact on the complexity of the algorithms needed to solve a problem.

The algorithm is thus as follows:

• Empty case:  (Problem 4.a - 5 pts)  Nothing to do here.  Return the host.

• Non-empty case:  There's no smoothing that can be done on a single element, so we must delegate to the rest of the list.   First we must set up the ring buffer and start counting down the elements until we reach the given window size:

  • Instantiate the RingBuffer and insert the current host's first into it.   The ring is now pointing at the newest element in the sliding window.

  • Delegate to rest, passing on a decremented window size value, the "countdown" value (we're counting it down to zero, and we've already put one value into the ring) as well as the the current total sum, which is just the raw value in first, since we only have one value so far. 

    • Empty case:  (Problem 4.b - 5 pts)  Nothing to do here.  We're done.  Return the mutated host

    • Non-empty case:   (Problem 4.c - 15 pts) Here's where we will calculate the average value from the sliding window:

      1. Start the calculation of the new total sum by adding the raw value from first to the previous total sum.

      2. Save the current raw value in the ring by inserting it.

      3. What we do now depends on whether or not the sliding window is full, i.e. whether or not the countdown value has reached zero or not:

         • countdown value > 0:   The sliding window is not yet full, so we don't want to pull any data out of the ring yet, thus we simply decrement the countdown value.   The current total sum is already properly calculated in this situation.

         • countdown value == 0:   The sliding window is full, so we have to pull out the oldest value:   The countdown value is already zero, so we don't need to do anything with it any more.

           1. Use toPrev() to rotate the ring one element to make the oldest element in the ring accessible.

           2. Use removeFront() to remove the oldest element from the ring.   Subtract that retrieved value from the current total sum, completing its calculation.  Note that the removal will automatically realign the ring to point back at the newest value in the sliding window.  Happy, happy.  :-)

      4. Now that the current total sum is complete, divide it by the count of the ring, which is the current number of data elements in the sliding window.    This is the average value we want, so save it back into the first of the current list.

      5. Recur to the rest of the list, passing on the countdown value and the current total sum.