CSC151.01 2014F, Class 52: Merge Sort
=====================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Non-Exam Questions.
    * Exam Questions.
* Divide and conquer, revisited.
* Quiz.
* Lab.

Preliminaries
-------------

### Admin

* Sit wherever you want!  (Provided it's in this room.)
* Friday PSA.

### Upcoming Work

* Exam 4 due MONDAY, December 8.  (Extra day for those in plays,
  dance recitals, and swim-a-thons.)
    * Prologue due TONIGHT.  Please make sure to get it done.
* Reading for Monday:
  [Objects in Scheme](../readings/objects-reading.html)
* No lab write-up for today.  (I think we're done with lab write-ups
  for the semester.)

### Extra Credit Opportunities

#### Academic

* Inside Grinnell Thursday the 11th at noon in JRC 101: Grinnell's 
  Endowment: What Can and Can't it Do?

#### Peer Support

* Karan's radio show 11pm Thursday nights on KDIC 
* Evan's radio show 5pm Friday nights on KDIC
* Donna's radio show Sunday midnight on KDIC
* Noteworthy at the Dance performance (Once Upon a Time, Splintered), 
  December 5 in Flanagan
* One acts, December 6 and 7 in Roberts
* Pioneer Swim Meet, December 5 and 6 in the Osgood.  Time and get paid!
* Jazz Band, Dec. 13 8pm Gardner

### Non-Exam Questions and Comments

### Exam Questions and Comments

_Are the problems intentionally more challenging / harder to read?_

> No.

_What does `vector-index-of-extreme` do?_

> Gives the largest/smallest/whatever value in a vector.  That is, the
  one value that every other value may precede.  If we compare with <=, 
  it should give the largest value.  If we compare with >=, it should
  give the smallest value.

_Should I sort to find the extreme value?_

> **No!**  We're finding the extreme value so that we can sort.

_On problem 2, can I think about that quiz problem where we returned a procedure?_

> Yes, that may be helpful.

_On problem 3, could you explain what you mean by reasonable number
for the number of leaves in each subtree?_

> Suppose we want 5 leaves in the whole tree.  It would not make sense to have 0 leaves in the left subtree.  Similarly, it would not make sense to have 5 leaves in the left subtree.  So, a reasonable number would be a number greater than 0 and less than 5.

_On problem 5, it seems like counters are the best way to determine the 
 number of calls to `cons`._

> Yes.  The other strategies I've seen people use are ugly and fraught with 
  complexity.  And yes, you should cite them.

_I hate test suites._

> Sorry.  It's important that you learn to consider lots of cases when
  writing your procedures._

_I did not understand what you meant by "three vectors of length three with repeated elements."_

> If you have three slots, the values are ordered, and one element appears 
  more than once, then there are only three options: `#(v1 v1 v2)`, 
  `#(v1 v2 v2)`, and `#(v1 v1 v1)`.  If we don't require the values to
  be ordered, we have one other option: `#(v1 v2 v1)`.

_Does the binary search in problem 7 sometimes recurse forever?_

> Yes.  That's why you have to fix it in problem 8.

_Can we test preconditions?_

> Certainly.

Divide and conquer, revisited
-----------------------------

* Break our list/vector into two halves
* Sort the two halves
* Merge the two halves
* That last merge requires that we do one comparison for each value
  we have.

Quiz
----

Lab
---