• Continue partners (through Friday)

Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Analyzing algorithmic efficiency.
• The problem of searching.
• Making searching more efficient using divide-and-conquer.
• A demo: Destructive binary search.
• Considering the parameters to binary search.

Preliminaries

Admin

• I will continue to bring you food (or food-like substances) until I am caught up on grading.
  
  • Today: Strawberries and Cookies
• The danger of having Sam having a physician for a partner, taking SHACS quizzes, and then talking about them.

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

Upcoming Work:

• Reading for Friday, which should sound familiar: Association Lists
• Lab Writeup: See end of this eboard
  • Send email titled CSC 151 Lab Writeup 47 (Your Names)
  • Do not include the underscores.
  • Send to CSC151-02-grader@grinnell.edu
  • Due before class on Monday.
• Projects due NEXT TUESDAY.
• Quiz Friday.
  • Higher-order procedures.
  • Files in Scheme - know structure of recursion over files.
  • Analyzing procedures - think about when we do implicit extra work.

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

• Scholars' Convocation: Dutch Global Horizons, Thursday, April 28, 11 am, JRC 101
• Damon Williams: Bigger Than The Cops, April 28, 4pm or 5:15 pm
• Met Opera, Saturday, April 30, talk at 11:30, Opera at noon.

Peer

• Friday, Break Beat Poets performing behind Eco House at 4:30 p.m.
  • Eco house is across from Cleveland.
• Maybe GMon, Thursday, 7:30 p.m., Loose Lounge.
• Rushdie's East/West, May 6/7 at 7:30 p.m.

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
• Effective Altruism club, 2:30-3:30 Sundays in JRC 226.

Misc

Not for Extra Credit

• Third year students, design a logo or something for a vinyl sticker.
  Gift card to PC!

Questions

Debrief on yesterday's lab

(define reverse
  (lambda (lst)
    (if (null? lst)
        null
        (append (reverse (cdr lst)) (list (car lst))))))

Beware the jabberwok, and things that depend on the length of the list.

In this case, append depends on the length of the list.

The reverse procedure also has to step through the list. We are going to have to deal with recursive procedures if we want to process a whole list.

But it's dangerous to call append at every step. Append is going to do a lot of work at every step.

Example with five element list.

    > (reverse '(1 2 3 4 5))
    > (append (reverse '(2 3 4 5)) '(1)) ; Sam skip steps
    > (append (append (reverse '(3 4 5)) '(2)) '(1)) ; Sam skip steps

    > (append (append (append (reverse '(4 5)) '(3)) '(2)) '(1)) ; Sam skip step))
    > (append (append (append (append (reverse '(5)) '(4)) '(3)) '(2)) '(1)) ; Sam skip step
    > (append (append (append (append (append (reverse '()) '(5)) '(4)) '(3)) '(2)) '(1)) ; Sam skip step
    > (append (append (append (append (append '() '(5)) '(4)) '(3)) '(2)) '(1)) ; 
    > (append (append (append (append '(5) '(4)) '(3)) '(2)) '(1)) ; 1 call to append
 ; We remember that (append (list-of-length-k) lst) represents k+1 calls
    > (append (append (append '(5 4)) '(3)) '(2)) '(1)) ; 2 more calls to append; 3 total

    > (append (append '(5 4 3) '(2)) '(1)) ; 3 more calls to append; 6 total
    > (append '(5 4 3 2) '(1)) ; 4 more calls to append; 10 total
    > '(5 4 3 2 1) ; 5 more calls to append; 15 total

If the list had six elements, it would have been 6 more or 21 total

If the list had seven elements, it would have been 7 more or 28 total

If the list had twenty elements, it would have been 1 + 2 + 3 + 4 + 5 + ... + 20.

Analyzing algorithmic efficiency

Computer scientists like to look at how efficient algorithms are. We saw two reversing algorithms. It turns out that one was much better than the other.

So we like to try to identify the general cost of an algorithm.

• Some take a constant number of steps times the size of the input. (E.g., reversing a list with a sensible approach takes about 5*n for a list of length n.)
• Some take a constant number steps independent of the size of the input. car takes the same amount of time, whether the list is 1 element or 10,000,000,000. (If you think about the diagram, you just have to follow one arrow.)
• Some take a constant times the square of the size of the input
• And there is much more.

Once we've analyzed an algorithm, we ask "Can we do this better."

The problem of searching

How can I tell there is a mentor in my set of cards?

Look through the cards one by one until a. You find Sarah OR b. You run out of cards

In Scheme

    (define find-mentor
      (lambda (lst)
        (cond
          [(null? lst)
           (error "Your mentor is missing.")]
          [(mentor? (car lst))
           (car lst)]
          [else
           (find-mentor (cdr lst))])))

If there are N students in my set of cards, how long will this take?

a. Best case? It's first: Some constant (null? + car + mentor?), but pretty fast.

b. Worst case? Go through the entire stack. Some constant times n.

c. Average case (whatever that is)?

How would I make this more efficient?

• Option 1: Give a card to every student. Ask "Does anyone have a mentor?".
• Option 2: Put them in order - takes a lot of time.
• Option 3: Put them in different groups (e.g., all students with last name "A" then all students with last name "B" ...)

A divide-and-conquer algorithm

• Look in the middle
• If the middle is too small throw away the left half, try again
• If the middle is too largea throw away the right half (larger elements), try again
• If the middle is just right you are done

A valid critique: This assumes that you can easily find the middle element and throw away half. We don't yet know how to do that.

A demo: Destructive binary search

• See the floor.
• If we were looking through a set of 2000 students, how many times do we have to look at a student name using this approach?
• Start with 2000
• Throw away half; down to 1000
• Throw away half; down to 500
• Throw away half; down to 250
• Throw away half; down to 125
• Throw away half; down to 63
• Throw away half; down to 32
• Throw away half; down to 16
• Throw away half; down to 8
• Throw away half; down to 4
• Throw away half; down to 2

• Throw away half; down to 1

• Throw away half; down to

Designing binary search

Suppose we represent each course at the College as a list of the form

'("ID" YEAR SEMESTER "TITLE" "PROF" "ROOM" "TIMES")`

For example, this course would be represented by the following list.

'("CSC 151.02" 2016 Spring "Functional Problem Solving"
  "Rebelsky" "Science 3813" "MTWF 3:00-3:50")

Suppose also that we are storing classes in an array and want to search for classes by class ID.

Write 6P-style documentation for binary search (that is, specify inputs, outputs, and expectations). Your procedure should accept different arrays of courses.

;;; Procedure:
;;;   binary-search-courses
;;; Parameters:
;;;   courses, an array of courses
;;; Purpose:
;;;
;;; Produces:
;;;
;;; Preconditions:
;;;   Each course in courses is a list of the form
;;;     '("ID" YEAR SEMESTER "TITLE" "PROF" "ROOM" "TIMES"),
;;;     where YEAR is an integer and SEMESTER is a symbol
;;;     ('Fall, 'Spring, or 'Summer).
;;;
;;; Postconditions:
;;;