Warning! You are being recorded and transcribed, provided the technology is working correctly.
Approximate optimistic overview
Scholarly
Artistic
Multicultural
Peer
Musical, theatric, sporting, and academic events involving this section’s students are welcome.
Wellness
Misc
These do not earn tokens, but are worth your consideration.
(define (proc param1 ... paramn) body)
rather than (define proc (lambda (param 1 ... paramn) body)).
let bindings (and let* and letrec)cond blocks.cond blocks, generally put the guard and the consequent(s) on
separate lines.#t and #f.)
list.Can we get grade reports tonight?
Yes. (Readings and reflections may not be up to date.)
We made a fixed-size image. Can we just use scale to scale it?
No. Please take the width and height as parameters.
The original image is a square. What should I do with different aspect ratios?
Option 1: Stretch it in the longer direction.
Option 2: Make a smaller-by-smaller square and then pad on the sides.
Option 3: Make a larger-by-larger square and then truncate it.
What are some circumstances where “recursing on only half the tree” doesn’t work?
Finding the largest/smallest value in an unordered tree. Printing all of the elements in the tree. Converting the tree to a list or vector.
I really am struggling to trace the bst-find function, would you
mind explaining how to go about it?
;;; (bst-find bst str) -> boolean?
;;; bst : treeof string?
;;; str : string
;;; Look for a string in a binary search tree of strings.
;;; When we say that bst is a binary search tree, we mean it is a binary
;;; tree with the property that the left subtree contains smaller values
;;; the right subtree contains larger values, and the subtrees are both
;;; binary search trees.
(define bst-find
(lambda (bst str)
(if (empty-tree? bst)
#f
(let ([root (bt/t bst)])
(cond
; If we find the value at the root, we're done
[(string-ci=? str root)
#t]
; If the value is less than the root, we should look in the
; left subtree. (And don't need the right subtree.)
[(string-ci<? str root)
(bst-find (bt/l bst) str)]
; Otherwise, the value is greater than the root. We should
; look in the right subtree. (And it can't be in the left
; subtree.)
[else
(bst-find (bt/r bst) str)])))))
It’s hard to trace
bst-findusing our traditional mechanisms because trees are generally bigger than the values we regularly trace. We’ll look on the board.
Can we go over the reading questions?
The lab goes over
binary-tree-largest.
What are some common uses of binary search trees? They seem like a helpful way of organizing datasets. Are they used in hash tables?
Yes, they are used to implement dictionaries. (Hash tables use a different algorithm, one covered in 207.) “Self balancing binary trees” are probably used to implement immutable hashes in Scheme.
Does BST find only work when the tree is organized in the BST order? (Smaller things left, larger things right)
Yes!
Ah, the joy of counting.
Size 0: One shape.
Size 1: One shape.
Size 2: Two shapes. (0 left and 1 right; 1 left and 0 right)
Size 3: Either 0 left and 2 right (2), 1 left and 1 right (1), or 2 left and 0 right (2). Total: Five different shapes.
Size 4: Either 0 left and 3 right (5), 1 left and 2 right (2), 2 left and 0 right (2), or 3 left and 1 right (5). Total: Fourteen different shapes.
Size 5: Either 0 left and 4 right (14), 1 left and 3 right (5), 2 left and 2 right (2x2 = 4), 3 left and 1 right (5), or 4 left and 0 right (14). Total: 42.
Size 6: Either 0 left and 5 right (42), 1 left and 4 right (14), 2 left and 3 right (2x5 = 10), 3 left and 2 right (10), 4 left and 1 right (14), 5 left and 0 right (42). Total: 132 (I think)