• New lab partners. Choose your own.
• Not quite food!

Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Problem: Incorrect algorithms.
• Strategy: Understand state.
• Loop invariants.
• Lab (communal).
• Lab (pairs).

Preliminaries

Admin

• Office hours
  • Normal (MThF 1:45-3:15; walking 1:15-1:45)
  • In the Grill 8:00-9:30 a.m. Fri
  • In my office 8:00-9:30 a.m. Thu
• GHC folks: We miss you. We hope you are having an awesome time. Bring back swag.
• Don't forget Q&A session on Thursday at 11:00!

Upcoming Work

• Exam 1 distributed. Due next Thursday (no, not tomorrow).
  • Required prologue and epilogue.
  • I tend to write tests and experiments for most problems. Your problem 1 is a test for problem 2. There are unit tests for problem
    1. There's an experiment with pseudo-tests for problem 4. I will distribute tests or an experiment for problem 5. Let me know what else you need.
• Reading for Friday:
  • Java on the Command Line (coming soon)

Cool Things Coming to Campus

• Two versions of Anna Christie!
• Live Streaming of Verdi's Macbeth, Saturday at 11:55 a.m.
• Pop-up Exhibit, Thursday October 9th, all day in BCA 132

Academic

• Grinnell Prize Events this week.
• Artist Talk, Wednesday October 8th at 4:15pm in BCA 152 Rewriting the Application Programming Interface (API) for Art Making
• BCC Faculty Chat, Tuesday, October 14, 7pm

Peer Support

• Ajuna's Radio show Mondays at 8pm. Listen to African music
• Ezra's Radio show Thursdays at midnight. Radio melodrama.
• GC Anna Christie (Mira did costumes), Thursday night, Satuday night, Sunday afternoon
• War in Animated Film ExCo, Friday ARH 107/122, 7pm

Miscellaneous

• Fill in the Grinnell College Web Survey at http://bit.ly/1ncPO5V

Questions

A Problem: Incorrect Algorithms

• Programmers write incorrect algorithms, even when a problem is carefully is specified and the algorithm is well known
• We need ways to help programmers write better algorithms
• (We might also need ways to formally verify algorithms.)

A (Partial) Solution: Consider State

• What values do all the variables have?
  • Concrete: "i is 2"
  • Abstract: "i is positive"
  • Objects, arraysf
    • Characteristics/abstract, rather than contents
• When thinking about binary search, I might note that i know the elements of the array are in order.
• When thinking about insertion sort in an array, I might note that part of the array of the array is sorted, part is not, and something about the relationship between the parts

• Pictures help!

  • Picture of insertion sort on the board

    +--------------+---------------+ | sorted | unsorted | +--------------+---------------+ | | | 0 i length

  • Picture of selection sort on the board

    +--------------+---------------+ |sorted, small | unsorted | +--------------+---------------+ | | | 0 i length

  • Picture of binary search on the board

    +---------+---------+---------+ | < val | unknown | > val | +---------+---------+---------+ | | | | 0 lb ub length

• Math (formality) helps, too!

  • For binary search
    • For all i, 0 <= i < lb, vals[i] < val
    • For all i, ub <= i < length, vals[i] > val
  • For selection sort
    • For all j, 0 < j < i, vals[j-1] <= vals[j]
    • For all j, k, 0 <= j < i <= k < length, vals[j] <= vals[k]
• The math helps us clarify the boundaries.

Loop Invariants

• Take the ideas above and make them a bit more formal
• Express knowledge about the state of the system in pictures and "math"
• For loops, make a model of the state of of the system s.t.
  • If it holds before you execute one iteration of the loop, it holds at the end of that iteration
  • You can guarantee that it holds before the loop starts
  • When the loop terminates, it helps us know that we've achieved the goal of our algorithm (loop)
• Easier said than done.
• Useful for formal proofs.

Lab (Collaborative)

+---------+---------+---------+---------+
|   red   |  white  | unknown |   blue  |
+---------+---------+---------+---------+
|         |         |         |         |
0         r         i         b         length

How might we represent this more formally (in Math/Code)

• For all j, 0 <= j < r, classifier.isRed(vals[j])
• For all j, r <= j < i, classifier.isWhite(vals[j])
• For all j, b <= j < length, classifier.isBlue(vals[j])

How might we arrange things so that this holds when our algorithm starts? (What values of r, i, and b guarantee those three characteristics?)

• r = 0, i = 0, b = length

  +---------+---------+---------+---------+ | | +---------+---------+---------+---------+ | | 0 length r b i

Given the following state, what can we do to shrink the size of unknown?

+---------+---------+---------+---------+
|   red   |  white  | unknown |   blue  |
+---------+---------+---------+---------+
|         |         |         |         |
0         r         i         b         length

If the value at position i is blue ...

+---------+---------+-----------+---------+
|   red   |  white  |b unknown x|   blue  |
+---------+---------+-----------+---------+
|         |         |           |         |

Swap it to right before the blue stuff

+---------+---------+-----------+---------+
|   red   |  white  |x unknown b|   blue  |
+---------+---------+-----------+---------+
|         |         |           |         |

Move the blue boundary

+---------+---------+----------+----------+
|   red   |  white  |x unknown |b   blue  |
+---------+---------+----------+----------+
|         |         |          |          |

If the element is white, move the white boundary up

+---------+---------+---------+---------+
|   red   |  white  |w unknown|   blue  |
+---------+---------+---------+---------+
|         |         |         |         |
0         r         i         b         length

+---------+----------+--------+---------+
|   red   |  white  w|unknown |   blue  |
+---------+----------+--------+---------+
|         |          |        |         |

If the element is red, things are a bit more complicated. You'll need to swap the element to the end of the reds and move the red boundary.

+---------+---------+---------+---------+
|   red   |x white  |r unknown|   blue  |
+---------+---------+---------+---------+
|         |         |         |         |
0         r         i         b         length

+-----------+-------+---------+---------+
|   red    r|white  |x unknown|   blue  |
+-------------------+---------+---------+
|           |       |         |         |
0           r       i         b         length

If our goal is to look at each element once, then it's concerning that we'll have to look at the x we passed by. But that x was in the white section, so we know it's white and can also increment the white boundary.

+-----------+---------+-------+---------+
|   red    r|white   w|unknown|   blue  |
+-----------------------------+---------+
|           |         |       |         |
0           r         i       b         length

Lab (Individual)

We didn't get here.