teaching machines

CS 145 Lecture 23 – Optimization and Accumulation

October 28, 2015 by Chris Johnson. 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