# teaching machines

## CS 145 Lecture 23 – Optimization and Accumulation

October 28, 2015 by . Filed under cs145, fall 2015, lectures.

### Agenda

• what ?s
• loop patterns:
• optimization
• accumulation

### TODO

• Read chapter 5 in your book. You’ve already read section 5.3. Write down 2-3 questions or observations on a 1/4 sheet for Friday.

### Note

Today we continue our discussion of loop patterns. Last time we look at the pervasive loop and a half. Now we look at the optimization and accumulation patterns. Let’s start with a little exercise:

Write pseudo-Java a method that finds the longest whitespace-separated String in a sentence.

The code you wrote here probably falls into the optimization pattern. An optimization algorithm traverses a collection of data and extracts out the element that best meets some criteria. Most instances of optimization involve maximizing or minimizing some numerical value, and they tend to look like this:

initialize bestSoFar
for each item
if item is better than bestSoFar
bestSoFar = item
end
end

What about that initialization step? What do you initialize bestSoFar to?

We’ll look at an example of normalizing an image.

Next we observe the accumulation pattern, where a loop iterates through a collection and accumulates values in some variable of larger scope. Accumulations tend to look like this:

initialize soFar
for each item
integrate item into soFar
end
use soFar to some other end

We’ll look at an example of calculating a linear approximation of a dataset.

### Code

#### LongestString.java

/usr/lib/ruby/2.7.0/rubygems/dependency.rb:311:in to_specs': Could not find 'coderay' (>= 0) among 56 total gem(s) (Gem::MissingSpecError)
Checked in 'GEM_PATH=/.gem/ruby/2.7.0:/var/lib/gems/2.7.0:/usr/lib/ruby/gems/2.7.0:/usr/share/rubygems-integration/2.7.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/2.7.0:/home/johnch/.gems', execute gem env for more information
from /usr/lib/ruby/2.7.0/rubygems/dependency.rb:323:in to_spec'
from /usr/lib/ruby/2.7.0/rubygems/core_ext/kernel_gem.rb:62:in gem'
from ./coderay:24:in '


#### Exposer.java

/usr/lib/ruby/2.7.0/rubygems/dependency.rb:311:in to_specs': Could not find 'coderay' (>= 0) among 56 total gem(s) (Gem::MissingSpecError)
Checked in 'GEM_PATH=/.gem/ruby/2.7.0:/var/lib/gems/2.7.0:/usr/lib/ruby/gems/2.7.0:/usr/share/rubygems-integration/2.7.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/2.7.0:/home/johnch/.gems', execute gem env for more information
from /usr/lib/ruby/2.7.0/rubygems/dependency.rb:323:in to_spec'
from /usr/lib/ruby/2.7.0/rubygems/core_ext/kernel_gem.rb:62:in gem'
from ./coderay:24:in '


### Haiku

Prince Charming’s routine
while (!footFits) try next foot He found his false love