teaching machines

CS 145 Lecture 27 – Array Patterns

November 11, 2016 by . Filed under cs145, fall 2016, lectures.

Dear students,

After you solve a few array problems, you start to see some regular patterns emerging in your algorithms. Today, we break down a few of those patterns. The payoff of cataloging these is that the next time we encounter an array problem, we can apply the general structure and save our labor and thinking for the parts that are different.

We’ll start with the optimize pattern. Optimization algorithms find the maximum, the minimum, the shortest, the longest, the nearest, or some other extreme value within a data set.

initiaze soFar to first item
for each remaining item
  if item is better than soFar
    soFar = item

Next up is the accumulate pattern. Accumulation algorithms collect all the data up into one big value. Finding the sum, mean, and product of a bunch of numbers fits this description. So does joining a bunch of strings, counting occurrences, checking if all items meet some criteria, and checking if any items meet some criteria. The accumulate pattern looks like this:

initialize runningValue
for each item
  accumulate item into runningValue

We turn to the map pattern, which involves transforming one array into another. We might turn an array of strings into an array of their lengths, an array of miles into an array of kilometers, an array of strings into their lowercase equivalents, and so on. The map pattern looks like this:

make destination array that's the same size as source
for each item i in source
  destination[i] = transform source[i]

Finally, we have the linear search, we scans an array for a particular item and reports its location. We might use this in a list of runners in a race, sorted by finish time. We search for a name and use its location to determine that runner’s place. The linear search pattern looks like this:

for each element
  if this element is the one we want
    return its index

Here’s your TODO list to complete before we meet again:

See you next class!

Sincerely,

P.S. It’s Haiku Friday!

Dear Mr. Santa
Please bring lots of boxed numbers
i has been real good

P.P.S. Here’s the code we wrote together…

Foo.java

package lecture1111;

import hw5.speccheck.Accidental;
import hw5.speccheck.Duration;
import hw5.speccheck.Letter;
import hw5.speccheck.Note;
import hw5.speccheck.WavIO;

public class Foo {
  public static void main(String[] args) {
    Note bFlat = new Note(Letter.B, Accidental.FLAT, 4, Duration.QUARTER, 1, false); 
    Note aFlat = new Note(Letter.A, Accidental.FLAT, 4, Duration.QUARTER, 1, false); 
    Note fSharp = new Note(Letter.F, Accidental.SHARP, 4, Duration.HALF, 1, false); 

    Note[] notes = new Note[3];
    notes[0] = bFlat;
    notes[1] = aFlat;
    notes[2] = fSharp;
    
    Note[] hotCrossBuns = {bFlat, aFlat, fSharp};
    WavIO.write(hotCrossBuns, 100, "/Users/johnch/Desktop/hotCrossBuns.wav");

  }
}

Map.java

package lecture1111;

import java.util.Arrays;

public class Map {
  public static void main(String[] args) {
    String[] numbersAsStrings = {
        "16", "9", "72", "72", "-45", "145", "146", "245", "252", "260", "268"
    };
    
    int[] numbers = numberfy(numbersAsStrings);
    
    Arrays.sort(numbers);
    
    System.out.println(Arrays.toString(numbers));
    
//    System.out.println(Arrays.toString(numberfy(numbersAsStrings)));
  }
  
  public static int[] numberfy(String[] numbersAsStrings) {
    int[] numbers = new int[numbersAsStrings.length];
    for (int i = 0; i < numbers.length; ++i) {
      numbers[i] = Integer.parseInt(numbersAsStrings[i]);
    }
    return numbers;
  }
}