• New partners!
• Random numbers for the exam distributed.

Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Exam Questions.
  • Other Questions.
• Preparation.
• Lab.

Preliminaries

Admin

• Welcome back! I hope you had a relaxing break.
• Tomorrow we will look at your project images.
• Wednesday we will look at your project code.

Upcoming Work

• Exam 4 due Monday, December 8.
  • Due Monday because I need time to grade before Friday.
  • Printed copy due Tuesday
  • Prologue due this Friday.
• Lab writeup: Problems 2e and 4f: http://bit.ly/151-2014F-w49
• No reading for Tuesday (or Wednesday).

Extra Credit Opportunities

Academic

• CS 207 presentations Wednesday at 11:00 a.m.: Sports Scheduling
• CS Extras Thursday the 4th: Summer Opportunities in CS

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 4 and 5 in Flanagan
• One acts, December 5 and 6 in Roberts
• Pioneer Swim Meet, December 5 and 6 in the Osgood

Questions on the Exam

Other Questions

Preparation

Four minutes with your partner ...

• What is the key idea in insertion sort?
• How does insertion sort differ in lists and vectors?
• Why do we provide you with three different kinds of list-based insertion sort (and four kinds of insertion sort)?
  • (numbers-insertion-sort numbers)
  • (list-insertion-sort lst may-precede?)
  • (list-keyed-insertion-sort lst get-key may-precede?)
  • (vector-insertion-sort! vec may-precede?)
• What murkiness remains?

Key Idea

• There are ways to sort lists and vectors.
• There is not one right way to sort.
  • But some are faster.
• Insertion sort (and many sorts) sorts by comparing elements
• Base idea: Inserting into lists (or subarrays)
  • Conceptually separate elements into two parts
    • Things that we know are in order
    • Things we haven't looked at yet
    • Repeatedly grab a thing from the second sequence and insert it into the right place in the first sequence

Sorting Vectors vs. Sorting Lists

• To sort lists, you have to build new lists.
• To sort vectors, you have to rearrange the vector
  • That means you need to keep track of an implicit "boundary" between the part of the vector that is sorted and the part that is not sorted. (In the example, sorted things are to the left.)

Murkiness

Lab

• If you have not done so already, do Check 2. (You should have done so already, but I realize that it was break.)
• In writing insert-string, you may find it useful to look at insert-number.