Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Some preparation.
• Lab.

Preliminaries

Admin

• New partners.
• I will continue to bring you food (or food-like substances) until I am caught up on grading.
  
  • Today: Cookies.
• Sunday is Mother's day. If you are fortunate enough to have a mother or mother equivalent who is important to you, make sure to let that person know.
  • SGA will help with their cool "send your mom a card" event on Thursday. JRC Lobby.

Reminders

• Office hours this week
  • See http://rebelsky.youcanbook.me.
  • Ask me about other available times.
• Tutor hours
  • Sunday, 3-5 p.m.
  • Sunday-Thursday, 7-10 p.m.
• Review Sessions
  • Wednesday at 8pm in CS commons with someone, we hope
  • Thursday at 10 am with SamR (I'll be a few minutes late)
  • Thursday at 8pm in CS commons with Alex

Upcoming Work:

• Quiz Friday
  • Association lists
  • Binary search
  • Sorting concepts
• Reading for Friday Merge Sort
• Lab Writeup: 2e, 3
  • Send email titled CSC 151 Lab Writeup 51 (Your Names)
  • Do not include the underscores.
  • Send to CSC151-02-grader@grinnell.edu
  • Due before class on Monday.
• Exam 4 due next Tuesday
  • Prologue due Friday night
  • Epilogue also due next Tuesday.

Extra Credit

• Send your reports to rebelsky@grinnell.edu with subject "CSC 151 Extra Credit". (Do not include the quotation marks.)
• Send opportunities to me before class with subject "CSC 151 EXTRA CREDIT OPPORTUNITY!"

Academic / Artistic

• Town Hall Thursday, Unpopular Identities. 11 a.m. and some other time.
• Thursday's CS Extra on STEM for the Blind. 4:15 p.m. in Science 3821. Food in the commons beforehand.
• Thursday, May 5, 8pm, the Science of Substances.
• Finals week's Inside Grinnell. Tuesday, May 17 at noon in JRC 101. Food served.

Peer

• Flute Ensemble, Thursday, 7:30, Bucksbaum Gallery.
• Rushdie's East/West, May 6/7 at 7:30 p.m. No tickets necessary.
• May 14 long-form and short-form improv workshop and then performance.
• Humans of Grinnell College on Facebook.
• KPop Gardner. Friday the 6th .... More details on Friday.

Regular Peer

• Social Dance Workshop Tuesdays 7:00-8:00 in Bucksbaum Dance Studio
• Post-break ExCo on British Politics Wednesdays at 8:00 in JRC 203.
  Just show up; you don't need to sign up.
• Pun club Saturdays at 4pm in Younker
• Electronic Potpourri on KDIC Fridays at Five
• Space Odyssey KDIC Fridays at Six
• Bollywood, Fridays, 7:30-8:30, Younker (NOT THIS WEEK)
• Effective Altruism club, 2:30-3:30 Sundays in JRC 226.

Misc

Questions

Preparation: A Few Questions on Insertion Sort

Did we talk about this sorting algorithm yesterday?

Nothing quite like this.

What is the key idea in insertion sort?

Two groups of items - Those that are alreay sorted (in order)

Then insert items from unsorted group into the correct place in the sorted group.

Problem: How do you put them in between?

See the insert-number algirthm.

How does insertion sort differ in lists and vectors?

For lists, we have two separate lists and keep building a new sorted list each time.

For vectors, we do it in place and keep track of an "imaginary boundary"

The imaginary boundary is an index in the vector that separates the portion that we know is sorted from the portion that we know is unsorted.

We have to "shift right" to put a new element in.

Why do we provide you with three different kinds of list-based insertion sort (and four kinds of insertion sort)?

One handled only numbers.

One of them uses a predicate, so it could deal with any type.

There was a third one that used a "get key" to tell what were sorting by.

Why would we use a "get-key"?

    (define list-keyed-insertion-sort
      (lambda (lst get-key may-precede?)

Example: We are sorting students. (LNAME FNAME FAVECOLOR BOX HOMELOG HOMELAT)

When sorting, we might say "We're sorting by box number". get-key is then (r-s list-ref 3). may-precede? is <=.

Lab

• Do the lab on insertion sort.
• Be prepared to reflect.
• Writeup 51: 2e, 3