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
• 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