Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• The problem of sorting.
• Writing sorting algorithms.
• Examples.
• Formalizing the problem.

Preliminaries

Admin

• New partners!
• Review session tonight at 7pm.
• Quiz 12 returned.
  
  • If you have questions, go to the review session tonight (or talk to me, or talk to a tutor, or email me)
• Today is another discussion-style day.

Upcoming Work

• Projects due tomorrow night. Read the instructions!
• Exam 4 assigned, due next Monday.
  • Prologue due Friday night!
• No lab writeup.
• Reading for Tuesday: Sorting

Extra Credit Opportunities

Academic

• Toward an Embodied Liberal Arts, Tonight, 8pm, JRC 101
• PBK Convo, Wednesday.

Peer Support (Afternoon Section)

• Baseball, Saturday, Noon and 2:30, Sunday 10:00 and 12:30.

Miscellaneous

• Donate to UNICEF or Red Cross to support recovery in Nepal. Read the campus memo for more info.

Other Good Things (no extra credit)

• Donate even more to UNICEF or Red Cross or other organizations

Notes on the Exam

• Electronic due Monday, printed due Tuesday.
  • Gives me time to try to get you grades sooner.
  • Experience shows most class have work due later in the week.
  • I will discuss extensions.
• Starts with a pre-set Racket file to make it easier for you and for me.
• Seven problems, as always.
• Four problems are on a new model of trees.
• Comparing lists to trees
  • cons -> node
  • pair? -> node?
  • null -> nil
  • null? -> nil?
  • car cdr -> root-value, left-subtree, right-subtree
• You do not need to cite the initial code file.

Notes on the Project

• Yes, separate helpers are a good idea for development. 4Ps suffice, as does reasonable shorthand. ;;; (fishy! image n) ;;; Draws the nth fish on the image.
• Make sure to review the requirements, including the rubric.
• Scaling is essential. Stretching (switching aspect ratios) may be needlessly difficult.
  
  • If your images don't stretch, DOCUMENT IT!
  • If your images look better at certain aspect ratios, NOTE IT!
• One folder, one email

Questions

• When is the final?
  • Tuesday or Wednesday of finals' week
  • 9am or 2pm
• We will talk about the final a week from Wednesday.

The problem of sorting

• Binary search - Searches an ordered non-empty vector for an entry (entries are often lists)
• So ... we want a way to put vectors in order.

Writing sorting algorithms

Examples: Insertion, selection, etc

Formalizing the problem