EBoard 34: SoLA 4

This class will be recorded! Its use is limited to members of the class. Please do not share with others.

Approximate overview

• Prelimary chatter [~30 min]
• Administrivia [~0 min]
• Q&A [~40 min]

Administrative stuff

Notes and News

• Class attendance is definitely expected/required Friday. (Yay! You get to evaluate me.) (And the mentors.)

Upcoming activities and other token-earning things

Events

• Sunday, Mentor Session at 1pm.
• Monday, Mentor Session at 7pm.

Upcoming work

• SoLA 4 Thursday
  • Starts at 3:30pm Thursday.
  • 48 hours, until 3:30pm Saturday
  • The sooner you do it, the sooner you’ll get grades back.
• SoLA 5 released on Monday
• Class on Wednesday during Exam Time for those with last-minute questions

Q&A

Administrivia

I emailed you something. How will it get graded?

You will repeatedly remind me until I tell you I’ve uploaded it.

The graders will magically find it.

Do you have a rubric for computational thinking?

No.

I will mostly look to see if you’ve shown some understanding of whatever description of computational thinking I give.

Can you do a running time example? [x2]

Counting calls

How many times do we call cons in evaluating (list-reverse '(1 2 3 4)) given the following definitions?

(define list-append
  (lambda (lst1 lst2)
    (if (null? lst1)
        lst2
        (cons (car lst1)
              (list-append (cdr lst1) lst2)))))
; Observation: One call to `cons` for each element in `lst1`.

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

Option one: Think it through, with a trace.

    (list-reverse '(1 2 3 4))
--> (append (list-reverse '(2 3 4)) (cons 1 null))
--> (append (list-reverse '(2 3 4)) '(1)) ; 1 cons
--> (append (append (list-reverse '(3 4)) (cons '2 null)) '(1)) ; 1 cons
--> (append (append (list-reverse '(3 4)) '(2)) '(1)) ; 2 conses
--> (append (append (append (list-reverse '(4)) (cons '3 null))) '(2)) '(1)) ; 2 conses
--> (append (append (append (list-reverse '(4)) '(3)) '(2)) '(1)) ; 3 conses
--> (append (append (append (list-reverse '(4)) '(3)) '(2)) '(1)) ; 3 conses
--> (append (append (append (append (list-reverse '()) (cons 4 null)) '(3)) '(2)) '(1))
--> (append (append (append (append (list-reverse '()) '(4)) '(3)) '(2)) '(1)) ;4 conses
--> (append (append (append (append '() '(4)) '(3)) '(2)) '(1)) ; 4 conses
--> (append (append (append '(4) '(3)) '(2)) '(1)) ; 4 conses
--> (append (append '(4 3) '(2)) '(1)) ; 5 conses (1 for the append)
--> (append (append '(4 3 2) '(1)) ; 7 conses (2 for the append)
--> '(4 3 2 1) ; 10 conses (3 for the append)

Option two: Insert a counter or display

(define cans
  (lambda (a b)
    (display "constructing") (newline)
      (cons a b)))

> (list-reverse '(1 2 3 4))
constructing
constructing
constructing
constructing
constructing
constructing
constructing
constructing
constructing
constructing

Running times

A procedure is

• “Constant time” if the number of steps is independent of the size of the input.
• “Linear time” if the number of steps grows at the same rate as the size of the input.
• “Quadratic” if the number of steps quadruples every time we double the size of the input.

Some constant-time operations.

• vector-len (because Racket stores the number of elements in a vector)
• vector-ref (because Sam told you so, and we saw it in experiments)
• car (from our diagrams, taking the car is just following the arrow from the first box in the cons cell)

Some linear-time operations

• list-length is linear in the length of the list (because we must cdr through the list until we reach the end. Longer lists require more cdrs)
• vector-sum is linear in the length of the vector (because we need to look at each element in the vector once)
• list-ref is linear in the index, because we have to cdr though the list until we reach the right place.

Some quadratic-time operations

• If we consider the bad list-reverse from above, 1 + 2 + 3 + … + n, which is about n*n/2. If we double the input size from 5 to 10, go from 25/2 to 100/2, about four times as much.

What is binary-search in a full search tree?

• None of the above! Faster than linear, but slower than constant-time.
• For the math people, it’s “logarithmic” (Sam’s dad joke: dancing beavers)

Sorting and Searching

You will probably not get a sorting problem.

Searching.

(define tree-contains?
  (lambda (tree val)
    (if (tree-empty? tree)
        #f
        (if (equals? (tree-root tree) val)
            #t
            (if (tree-contains? (tree-left tree) val)
                #t
                (if (tree-contains? (tree-right tree) val)
                    #t
                    #f)
                #f)))))

Or, embracing the zen of Booleans

(define tree-contains?
  (lambda (tree val)
    (and (not (tree-empty? tree))
         (or (equals? (tree-root tree) val)
             (tree-contains? (tree-left tree) val)
             (tree-contains? (tree-right val) val)))))

          "Word"
        /       \ 
    "Other"    "Yellow"
   /     \        \
"Below" "Things"  "Zebra"

Our (tree-contains? tree val) procedure looks as follows. If we search for “Sam” in the tree above, what elements do we look at and in what order?

• Start at the root.
• “Word” Doesn’t match
• Go to the left subtree.
• “Other” Doesn’t match
• Go the left subtree
• “Below” Doesn’t match
• Go the left subtree. It’s empty. Nope.
• Go to Below’s right subtree. It’s empty. Nope.
• Go “Other” right subtree.
• “THings” doesn’t match
• Things’ left subtree is empty. Nope.
• Things’ right subtree is empty. Nope.
• Look at “Word”’s right subtree
• Etc.

Using bst-find, trace what values we look at in looking for Sam.

• Sam is too lazy to type what he said.

Supppose we represent each student as a vector of four elements

#("Sam" 94231221 "rebelsky@grinnell.edu" "641-269-4410")

Suppose also that we have arranged the vector by ID number in strictly increasing order.

What is the appropriate call to (binary-search vec get-key less-equal?) in order to find the student whose id is 1111111?

Answer: (binary-search students (lambda (x) (vector-ref x 1)) <=)

Answer: (binary-search students (section vector-ref <> 1) <=)

Generalize to write a procedure (search-students-by-id ...)

Practice SoLA on creating binary trees?

Write a recursive procedure, (tree-range lb ub) that creates a moderately balanced bst of all the integers between lb (inclusive) and ub (exclusive).

E.g.,

(tree-range 1 7)
      3
    /   \
   1    5
    \  / \
     2 4 6

Note: You may not write (vector->tree (list->vector (range lb ub))).

(define tree-range
  (lambda (lb ub)
    (if (> lb ub)
        empty-tree
        (let ([midpoint (quotient (+ lb ub) 2)])  
          (binary-tree midpoint
                       (tree-range lb (- midpoint 1))
                       (tree-range midpoint ub)))))))

GOod pattern for writing binary tree procedures.

(define binary-tree-sum
  (lambda (tree)
    (if (empty-tree? tree)
        0
        (+ (btt tree)
           (binary-tree-sum (btl tree))
           (binary-tree-sum (btr tree))))))