Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Quick notes on merge sort.
• Quiz.
• Lab.

Preliminaries

Admin

• Continue partners.
• I will continue to bring you food (or food-like substances) until I am caught up on grading.
  
  • Today: Cheetos and Donuts (coherency is not my strong suit)
• 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.
• A second section of CSC 161 has been added at 10 a.m. It even has a few open slots.
• Penultimate Friday PSA.

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 ???
  • Thursday at 10 am with SamR
  • Thursday at 8pm in CS commons with ???

Upcoming Work:

• No more readings!
• No lab writeup.
• Exam 4 due next Tuesday
  • Prologue due Friday night
  • Epilogue 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

• Finals week's Inside Grinnell. Tuesday, May 17 at noon in JRC 101. Food served.

Peer

• Rushdie's East/West, May 6/7 at 7:30 p.m. Flanagan. No tickets necessary. Get there early.
• Humans of Grinnell College on Facebook.
• KGY: Koreagraphy presents K-POP Gardner. Friday at 10:00 p.m.
• LINK is selling food in JRC lobby Saturday/Sunday 1-3 or 1-4.
• May 13, NC and company at Prairie Canary.
• May 14 improv workshops 1-6pm, Show 7:15-10:15 in Gardner lounge.

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
• Bollywood, Bear Dance Studio, Friday, 6-7
• Space Odyssey KDIC Fridays at Six NOT THIS WEEK
• Effective Altruism club, 2:30-3:30 Sundays in JRC 226.

Misc

Questions

Can I take the final on Wednesday afternoon instead of Thurssday morning?

Yes.

Quick notes on merge sort

• ATP/TF-Sort was: Find the median, divide into small and large. Recurse.
• How is merge sort like or not like ATP/TF sort?
• Why do you think we chose merge sort rather than ATP/TF sort? (What might be a hidden complexity of ATP/TF sort?)

How is merge sort like ATP/TF sort?

• Both sorting algorithms involve dividing the population into two and then recursing.
• Both have a base case of "one or zero elements"
• Both usually create new lists, rather than change an existing vector.

How is merge sort different from ATP/TF sort?

• For merge sort, you just break in half, you don't pay attention to what goes in each half.

How do you put them back together?

• In ATP/TF sort? Shove the now-sorted small list in front of the now-sorted large list. (append)
• In merge sort? Look at the first element of each list. Take whichever is smallest/largest. That's the first element of your new list. And then do the same thing again and again.

Lab

Lab writeup: NONE

The experiment procedure is your friend.

Reflection

Since it's so easy to merge in ATP/TF sort (that is, the "divide into small/large, sort, shove together" sort), why do we use merge sort instead?

Maybe dividing into small and large is difficult.

Finding the median usually involves sorting. Non-sorting mechanisms that the class came up with are slow.

Why do we have two versions of merge sort?