CSC 151.01, Class 27: Trees

Overview

• Preliminaries
  • Notes and news
  • Upcoming work
  • Extra credit
  • Questions
• Quiz
• A bit more on vectors
• A bit about trees
• Lab
• Debrief (?)

Preliminaries

News / Etc.

• New partners!
• Welcome back to our backup mentor, Smarly!
• It would have been nice to see students take a creative approach to the burrito challenge. (E.g., “If every person in every class gives $1, we’ll all be at 100% and we’ll all get burritos.”)

Upcoming work

• Exam 3
  • Prologue due TONIGHT via email
  • Exam due Tuesday via email
  • Epilogue due Wednesday via email
  • Cover sheet due in class
• No lab writeup! Due before class Monday.
• Reading for Monday
  • Higher-order-procedures, revisited
• Flash Cards due Wednesday at 5pm.
  • Optional.

Extra credit (Academic/Artistic)

• Roxane Gay talk TODAY noon in Harris Cinema.
• Tabla concert TONIGHT
• Visit the two exhibits at the Faulconer Gallery. (Are there still two exhibits in the Faulconer gallery?)
• Retrospectively watch last night’s talk (Marlon James) if you can find it online.

Extra credit (Peer)

• Drag show April 14

Extra credit (Recurring peer)

• Listen to KDIC Wednesdays at 6pm - Witty banter with other personalities and/or co-host. Also Indian, Arabic, and Farsi music.
  (Up to two units of extra credit.)
• Peer editing with SS. Talk to SS about the details. Make your English Lit more literate.

Extra credit (Misc)

• Host one or more prospective students.

Other good things

• Grinnell Singers in Concert on Sunday at 2pm in Sebring Lewis.

Friday PSA

• Please take care of yourselves. I do care about you and I’m fortunate to have you in the class.

Questions

How do you shorten long and rambly code?

• Sometimes pull things out and make a separate procedure.
• If you have a complex expression, name it as a separate procedure.
• Write higher-order procedures, like we did last class.
• Practice with other people and critique.

Quiz

Remember: If you finish early, revel in the chance to sit quietly.

Continued debrief on vectors

Vectors have two important characteristics.

• Fast access to every element.
• Vectors are mutable -> You can replace an element in a vector without building a new vector. (Lists require that you build a new list.)

In contrast, lists are dynamic - they can grow and shrink.

Some folks also prefer immutable structures.

I hear that there are two approaches you saw to vector-sum. What were they?

• One approach is to use a tail-recursive helper that keeps track of both the position in the vector and the running sum. We introduced a new list sum using this technique.
• Another aproach is to use direct recursion, as in the vector-largest procedure from the reading. Or in the orignal list-sum.
• Let’s look at both.

(define list-sum-tr
  (lambda (lst)
    (let kernel ([remaining lst]
                 [sum-so-far 0])
       (if (null? remaining)
           sum-so-far
           (kernel (cdr remaining)
                   (+ sum-so-far (car remaining)))))))

(define vector-sum-tr
  (lambda (vec)
    (let ([len (vector-length vec)])
      (let kernel ([pos 0]
                   [sum-so-far 0])
        (if (>= pos len)
            sum-so-far
            (kernel (+ 1 pos)
                    (+ sum-so-far (vector-ref vec pos))))))))

(define list-sum-direct
  (lambda (lst)
    (if (null? lst)
        0
        (+ (car lst) (list-sum-direct (cdr lst))))))

(define vector-sum-direct
  (lambda (vec)
    (let ([len (vector-length vec)])
      (let kernel ([pos 0])
        (if (>= pos len)
            0
            (+ (vector-ref vec pos)
               (kernel (+ pos 1))))))))

Note that we can also compute this right-to-left rather than left-to-right.

(define vector-sum-tr-alt
  (lambda (vec)
    (let kernel ([pos (- (vector-length vec) 1)]
                 [sum-so-far 0])
      (if (negative? pos)
          sum-so-far
          (kernel (- 1 pos)
                  (+ (vector-ref vec pos) sum-so-far))))))

(define vector-sum-direct-alt
  (lambda (vec)
    (let kernel ([pos (- (vector-length vec) 1)])
      (if (>= pos len)
          0
          (+ (vector-ref vec pos)
             (kernel (- pos 1)))))))

Why am I getting weird errors when I try to use the result of vector-set!?

• Because vector-set! returns nothing. You’re probably trying to use the result in some future computation.
• You’ll see a slightly different pattern of recursion for procedures in which you modify vectors.
  • Call vector-set! to modify
  • and recurse
• We now have multiple consequents after a guard. We should therefore use when or cond, depending on the situation.

Example: An incorrect approach to “double all the values”

(define vector-double!
  (lambda (vec)
    (let ([len (vector-length vec)])
      (let kernel ([pos 0]
                   [vec vec])
        (if (>= pos len)
            vec
            (kernel (+ pos 1)
                    (vector-set! vec pos (* 2 (vector-ref vec pos)))))))))

A bit about trees

There wasn’t time for this.

• Trees provide a third alternative for organizing information.
• [Sam may go over other issues on Monday]

Lab

Not enough time; Sam spent too much time talking about vectors.

We will continue the lab on Monday. Same partners!

Debrief

Why consider trees?

• Can provide an efficient way to organize information. (The finding in trees examples illustrates that.)
• Important conceptual idea: We can separate a way of thinking about organizing information (nodes) with the way we actually implement it (with lists or vectors).
  • This technique is a form of “abstraction”
  • Abstraction generally involves ignoring (“abstracting away”) underlying details. We find it useful as a way to approach both data and procedures.