• New partners!

Overview

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

Preliminaries

Admin

• Review session tonight at 7pm.
• I continue to try to add office hours.
• 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.
• Welcome to our prospective!

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 (Morning Section)

• KY's radio show, "We Think We're Funny", 9-10pm Mondays (TONIGHT). TBD.
• Julia's radio show, "The Hot Box". Wednesday night/Thursday morning 1:00-2:00 a.m.
• Baseball, Saturday, Noon and 2:30, Sunday 10:00 and 12:30.

Miscellaneous

None at the moment.

Other Good Things (no extra credit)

None at the moment.

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.
  • cons becomes node
  • pair? becomes node?
  • null becomes nil
  • null? becomes nil?
  • car and cdr become root-value, left-subtree, right-subtree

Notes on the Project

• Yes, separate helpers are a good idea for development. 4Ps suffice, as does reasonable shorthand. ; (butterfly! image n) ; Draws a really cool butterfly on the image, with ; the wing shape depending on n.
• 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!
• You will not get comments back on your proposals.

Questions

The problem of sorting

• Binary search!
  • Divide vectors into two sections, look in appropriate section
  • Vectors must be in order! (by key)
• Problem: If we have an unordered vector, how do we put things in order? The problem of sorting!

Writing sorting algorithms

• Let's think about some examples and how we'd do them by hand.

Examples: Insertion, selection, etc

Three sorting algoritms

• Move through the vector, swapping elements that are out of order (and again, and again, and again, and again)
• Create a new vector, repeatedly put the next element in the correct place in the new vector. "Insertion sort"
• Create a new vector, repeatedly grab the largest remaining element
• Which is best?
  • Theoretically, these are essentially equivalent in terms of cost.
  • But some are better for certain inputs.

Key operations

• Repeat (and know when to stop, and repeat repetitions)
• Compare two elements
• Swap two elements

Improving

• Break it in half, sort each half
• Do compare and swap simltaneously
• Break into sections and put it at the end of the new vector.

Formalizing the problem

    ;;; Procedure:
    ;;;   sort
    ;;; Parameters:
    ;;;   vec, vector
    ;;;   may-precede?, a binary predicate
    ;;;   get-key, a unary operation
    ;;; Purpose:
    ;;;   Create a new vector that contains the values in vec,
    ;;;   in order from smallest to largest.
    ;;; Produces:
    ;;;   sorted, a vector
    ;;; Postconditions:
    ;;;   See the preconditions for binary search.  The vector
    ;;;   should meet those preconditions.