This class will be recorded! Its use is limited to members of the class. Please do not share with others.
Approximate overview
Info:
Activities
Mini Projects
Readings
Quizzes
Other
Why was one of the reverse implementation so much slower than the other?
;;; (list-append l1 l2) -> list?
;;; l1, l2 : list?
;;; Returns the list formed by placing the elements of l2 after the elements
;;; of l1, preserving the order of the elements of l1 and l2.
(define list-append
(lambda (l1 l2)
(write (list 'list-append l1 l2)) (newline)
(cond
[(null? l1)
l2]
[else
(cons (car l1)
(list-append (cdr l1) l2))])))
;;; (list-reverse l) -> list?
;;; l : list?
;;; Returns l with the elements in the opposite order.
(define list-reverse-1
(lambda (l)
(match l
['()
null]
[(cons x tail)
(list-append (list-reverse-1 tail) (list x))])))
(define list-reverse-2
(lambda (l)
(letrec ([helper
(lambda (l so-far)
(match l
['()
so-far]
[(cons x tail)
(helper tail (cons x so-far))]))])
(helper l null))))
What did we discover about list-reverse-1 and list-reverse-2?
list-reverse-1 takes a lot more time than list-reverse-2.list-reverse-2 ahd approximately n recursive calls for a list
of length n.list-reverse-1 also had approximately n recursive calls for a list
of length n.list-reverse-1 calls list-append, list-append is recursive, and so there are lots of calls to list-append.We also studied alphabetically-first
Will the documentation SoLA be easier to finish this time?
I hope so. Fewer subtleties, but still some.
Are there seven new questions for SoLA 4?
Yes. Read tree recursion. Write tree recursion. Analysis. Searching and Sorting. Divide and conquer. Computational thinking.
For the Information Hiding one, which one should we change?
Only the ones whose code has to change.
I don’t feel like I have enough experience writing tree procedures. Beyond the practice, what can I do?
Invent your own problems. What’s something you might do with a tree? Think about things we’ve done with lists that we haven’t (yet) done with trees. Note:
tree-removeis hard. Non-binary trees are hard. Other: tally (specific or general), mapping (specific or general), filtering (removing is hard, but you could filter into a list), convert to a vector.
Redo ones we’ve done already:
tree-size,tree-depth,tree-sum,tree->list,tree-max,tree-level,tree-contains,bst-find, …
Are there trees other than binary trees?
Yes! Definitely. If you think about the original example of a corporate hierarchy, the president usually has more than two vice-presidents.
Biological trees.
How many total quizzes / lab writeups / readings will there be?
Sam needs to update the count.
We have the beginning-of-semester assumptions posted. Sam will scale.
How can we tell how many tokens we have?
You can’t. It’s a secret.
Over-use: You’ve done more things that require tokens you have.
If you over-use it gets used against labs, readings, whatever.
What costs tokens?
Arriving to class after John or Nameera has taken attendance. (Usually about 8 min past the start of class.)
Missing class without a clear reason/explanation. (Costs 2)
Late mini-projects (or late quizzes or late labs or …) without pre-arrangement/rationale.
Second redo on mini-projects.
I went to CS Table in Week 2. Can I still send the reflection.
Agh!
Sure.
Are there still things that earn tokens?
Yes, see above.
lb)
and an upper-bound (ub).
lb >= ub.Cancelled. Maybe Sam will fix it up for the SoLA.
Vectors, Idea 1
How long does this take?
Vectors, Idea 2
Vectors, Idea 3
Lists, Idea 1
Lists, Idea 2
Lists, Idea 3
We did not cover this issue.
Here’s a sample list.
(define cat (list "c" "a" "t"))
+---+---+ +---+---+ +---+---+
cat --> | * | -----> | * | *----> | * | / |
+-|-+---+ +-|-+---+ +-|-+---+
v v v
"c" "a" "t"
Here’s an attempt to “change” that list (build a new list)
(define hat (cons "h" (cdr cat)))
+---+---+ +---+---+ +---+---+
cat --> | * | -----> | * | *----> | * | / |
+-|-+---+ +-|-+---+ +-|-+---+
v v v
"c" "a" "t"
What has happened?
letIncorrect comment from some students: “The let introduces a temporary
change to a vector.”
Consider the following code.
;;; (vector-swap! vec i j) -> vec
;;; vector : vector?
;;; i : integer?
;;; j : integer?
;;; Swap the elements at indices i and j of vec, returning the
;;; now-modified vector.
;;; Pre: 0 <= i < (vector-length vec)
;;; Pre: 0 <= j < (vector-length vec)
(define swap
(lambda (vec)
(let ([tmp (vector-ref vec i)])
(vector-set! vec i (vector-ref vec j))
(vector-set! vec j tmp))))
;;; (vector-something! vec i) -> any?
;;; vec : vector?
;;; i : integer?
;;; Swap elements at positions 0 and i, returning the old value
;;; at position i.
;;; Pre: 0 <= i < (vector-length vec)
(define vector-something!
(lambda (vec i)
(let ([newvec (vector-swap! vec 0 i)])
; Temporary: Verify that the vector changed
(write newvec) (newline)
(vector-ref vec 0))))
What do we expect for the following?
> (define sample (vector "c" "a" "t")
We did not cover this issue.
Why was alphabetically-first so slow for lists arranged last to first?
;;; (alphabetically-first string) -> string
;;; strings: both (listof string?) nonempty?
;;; Find the alphabetically first string in the list.
(define alphabetically-first-1
(lambda (strings)
; (counter-increment! AFC 'alphabetically-first-1)
(cond
[(null? (cdr strings))
(car strings)]
[(string-ci<=? (car strings) (alphabetically-first-1 (cdr strings)))
(car strings)]
[else
(alphabetically-first-1 (cdr strings))])))
(define alphabetically-first-2
(lambda (strings)
; (counter-increment! AFC 'alphabetically-first-2)
(if (null? (cdr strings))
(car strings)
(first-of-two (car strings)
(alphabetically-first-2 (cdr strings))))))
;;; (first-of-two str1 str2) -> string?
;;; str1 : string?
;;; str2 : string?
;;; Find the alphabetically first of str1 and str2.
(define first-of-two
(lambda (str1 str2)
(if (string-ci<=? str1 str2)
str1
str2)))
We did not cover this issue.
Aka: Making your brain hurt a little bit more.
Our normal pattern for tree recursion.
(define tree-proc
(lambda (tree)
(if (empty-tree? tree)
base-case
(combine (process (btt tree))
(tree-proc (btl tree))
(tree-proc (btr tree))))))
For tree-size,
(define tree-proc
(lambda (tree)
(if (empty-tree? tree)
base-case
(combine (process (btt tree))
(tree-proc (btl tree))
(tree-proc (btr tree))))))
For tree-sum
(define tree-proc
(lambda (tree)
(if (empty-tree? tree)
base-case
(combine (process (btt tree))
(tree-proc (btl tree))
(tree-proc (btr tree))))))
For tree->list
(define tree-proc
(lambda (tree)
(if (empty-tree? tree)
base-case
(combine (process (btt tree))
(tree-proc (btl tree))
(tree-proc (btr tree))))))
For tree-increment
(define tree-proc
(lambda (tree)
(if (empty-tree? tree)
base-case
(combine (process (btt tree))
(tree-proc (btl tree))
(tree-proc (btr tree))))))
Hmm … we’re doing a lot of boring, repetitive work. Isn’t that what computers are good for?
;;; (make-tree-proc base-case combine process) -> procedure?
;;; base-case : value
;;; combine : procedure?
;;; process : procedure?
;;; Create a procedure for processing trees using the standard template
(define make-tree-proc
(lambda (base-case combine process)
(letrec [(tree-proc
(lambda (tree)
(if (empty-tree? tree)
base-case
(combine (process (btt tree))
(tree-proc (btl tree))
(tree-proc (btr tree))))))]
tree-proc)))
Does this really work?
Let’s see.
(define tree-size
(make-tree-proc 0 + (lambda (x) 1)))
(define tree-sum
(make-tree-proc 0 + (lambda (x) x)))
(define tree->list
(make-tree-proc null append list))
(define tree-increment
(make-tree-proc empty-tree btn (section + 1 <>)))
(define tree-depth
(make-tree-proc 0 (lambda (x y z) (+ 1 (max y z))) (lambda (x) 0)))