Real talk: Come to class (but if you can’t, let us know, and it’s lecture captured). There will be Reef polling!

Come see guest speakers. These people are awesome and there will be coffee.

Last time: The weaknesses of testing

• Won’t catch unforeseen problems (i.e. an intuition gap)
• Tests can be wrong
• Not exhaustive
• What about nondeterminism?

Today: We want to sort records of the form {first :: String, last :: String}

Turn ‘n Talk: What tests would you write for an algorithm that sorted records of this form?

• Corner cases: sort([]) → [], sort([{A, B}]) → [{A, B}]
• Preserves duplicates: sort([{A, B}, {A, B}]) → [{A, B}, {A, B}]
• Volume testing
• Sort by first name: sort([{A, B}, {A, C}]) → ???

• Either [{A, B}, {A, C}] or [{A, C}, {A, B}]  is right unless we specify
• This algorithm is not stable

Turn ‘n Talk: Think about another situation where this comes up.

Hint: It involves a data structure you’ve all seen in your previous classes.

• Graph algorithms (e.g. Dijkstra’s). Your choice of algorithm for shortest-path determines which shortest path you get if there are multiple

Strategy: Step back and write down the types (e.g add1 :: num → num). In our case,

• sort :: list(rec) → list(rec)
• suite :: (list(rec) → list(rec)) → bool
• runtest :: (input :: list(rec) X output :: list(rec) X f :: list(rec) → list(rec)) → bool
          We eliminate the output parameter and instead determine if f(input) is reasonable

What’s a reasonable test? For sorting [{Tim, Nelson}, {Andrew, Wagner}, {Chantal, Toupin}, {Sol,

Zitter}]

• [A, C, S]: Unreasonable because lists are different lengths
• [A, T, C, S]: Unreasonable because T is in the wrong spot
• [A, C, T, S, S]: Unreasonable because lists are different lengths

Question: How fast should our validator (runtest) need to be? Aren’t we redoing a lot of the work of the thing that we’re testing?

• In this case, we’re faster anyway
• But in general, longer verification isn’t such a bad thing (you only have to verify once per version of the algorithm; your algorithm is the (maybe) faster thing that will be used more often)

Idea: Use computers to generate inputs! We won’t focus much on randomizing inputs, but if you’re interested see QuickCheck.

Problem: Integer factorization. “Easy” to generate random inputs (just random numbers).

Turn ‘n Talk: Why might validation for integer factorization be a problem?

• Hard: You have to figure out whether each number in the output is prime, which depends on having an implementation for the very problem you’re testing!
• Easy: Multiply the numbers together to see if they equal the input number

Problem: Sudoku. “Easy” to validate (just follow the rules). Hard: generating inputs, since there needs to be a unique solution.

Idea 1: Sometimes algorithms are nondeterministic so we use validator functions to test properties about the algorithm.

Idea 2: Use computers to generate (random) inputs.

Idea 1 + Idea 2 = Oracle