CS 145 Lecture 27 – Array Patterns
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:
- Homework 5 is posted, and dates have also been added for the remaining homeworks. If you want to avoid stress and crunch time, work ahead.
- Lab 9 is posted. Feel free to start early!
See you next class!
P.S. It’s Haiku Friday!
Dear Mr. Santa
Please bring lots of boxed numbersihas 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; } }