CS 145 Lecture 23 – Optimization and Accumulation
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
Stringin 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/vendor_ruby/rubygems/dependency.rb:315:in `to_specs': Could not find 'coderay' (>= 0) among 94 total gem(s) (Gem::MissingSpecError) Checked in 'GEM_PATH=/var/www/.local/share/gem/ruby/3.2.0:/var/lib/gems/3.2.0:/usr/local/lib/ruby/gems/3.2.0:/usr/lib/ruby/gems/3.2.0:/usr/lib/x86_64-linux-gnu/ruby/gems/3.2.0:/usr/share/rubygems-integration/3.2.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/3.2.0:/home/johnch/.gems' , execute `gem env` for more information from /usr/lib/ruby/vendor_ruby/rubygems/dependency.rb:327:in `to_spec' from /usr/lib/ruby/vendor_ruby/rubygems/core_ext/kernel_gem.rb:57:in `gem' from ./coderay:24:in `'
Exposer.java
/usr/lib/ruby/vendor_ruby/rubygems/dependency.rb:315:in `to_specs': Could not find 'coderay' (>= 0) among 94 total gem(s) (Gem::MissingSpecError) Checked in 'GEM_PATH=/var/www/.local/share/gem/ruby/3.2.0:/var/lib/gems/3.2.0:/usr/local/lib/ruby/gems/3.2.0:/usr/lib/ruby/gems/3.2.0:/usr/lib/x86_64-linux-gnu/ruby/gems/3.2.0:/usr/share/rubygems-integration/3.2.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/3.2.0:/home/johnch/.gems' , execute `gem env` for more information from /usr/lib/ruby/vendor_ruby/rubygems/dependency.rb:327:in `to_spec' from /usr/lib/ruby/vendor_ruby/rubygems/core_ext/kernel_gem.rb:57:in `gem' from ./coderay:24:in `'
Haiku
while (!footFits) try next foot
He found his false love