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
Can I use a token for an extension until Friday?
No. You get a free extension until Friday.
Can I use a token for an extension until Sunday?
I’d prefer that you did not, but yes.
Will there be mentors available Friday evening?
I’m seeing if I can arrange that.
Where should I put my helpers?
I like them at the top. But the bottom is fine, too.
How do I know if my randomness is computationally efficient?
Mental math. Ask evening tutors or Sam or classmates or ….
How do I see my grade on Gradescope?
Um, you don’t. You count what percent of labs, quizzes, and such you have credit for and compare to the guidelines in the syllabus.
Sorry for the confusion!
What should I do when my lab shows as gobbledygook?
File -> Save Other -> Save Definitions as Text …
You will almost always get gobbledygook if you use “Comment with boxes”
What if that doesn’t work?
Computers are evil. Contact Sam.
Is it okay if Gradescope says it’s too long?
I think so.
Can we still use comment with boxes?
Sure. I prefer
#| ... |#, which seems safer.
Can you explain string-ci<=?
It’s just doing alphabetical comparison, as in a dictionary.
> (string-ci<=? "alpha" "omega")
#t
> (string-ci<=? "sam" "john")
#f
> (string-ci<=? "samr" "samuel")
#t
Can you go over the trace from the reading?
Sure.
Overview of binary search
> Is the tree empty?
> Is the value at the root (top) of the current tree?
If so, we're done
> Is the value less than the root (top)? (Alphabetically precedes)
If so, look in the left subtree.
> The value is greater than the root (top). (Alphabetically follows)
Look in the right subtree.
Tree is not empty. Look at “Mongoose”. “Skink” comes afterwards, so we look to the right.
Tree is not empty. Look at “Pidgeon”. “Skink” comes afterwards. So we look to the right.
Tree is not empty. Look at “Yak”. “Skink” comes earlier. So we look to the left.
Tree is not empty. Look at “Skink”. We found it! We’re done.
Could you make that look more like normal traces?
(bst-search '("Mongoose" L R) "Skink")
; Skink comes after Mongoose
--> (bst-search '("Pidgeon" L R) "Skink")
--> (bst-search '("Yak" L R) "Skink")
--> (bst-search '("Skink" L R) "Skink")
--> "Skink"
Could you trace the search for “Hippo”?
(bst-search '("Mongoose" L R) "Hippo")
; Hippo comes before Mongoose, look left --> (bst-search '("Iguana" L R) "Hippo")
; Hippo comes before Iguana, look loeft --> (bst-search '("Emu" L R) "Hippo")
; Hippo comes after Emu, look right --> (bst-search '("Gnu" L R) "Hippo")
; Hippo comes after Gnu, look right --> (bst-search empty-tree "Hippo"
; NOT THERE! --> #f ```
How did we know that “Hippo” is on the left?
The requirements of binary search trees.
- Everything on the left comes before the root. (or vice versa)
- Everything on the right comes after the root. (or vice versa)
- The subtrees are also binary search trees.
Could you go over the first self-check?
Sure.
We’ll get the same answer; we just do it in a different order.
As in the case of
reduce, if we use+, it won’t matter. But if use-or other things, it can matter.
Do we count underlines in the size?
No. The “if it’s empty, use 0” says “count 0 for the underlines”.
There are no values in the empty tree.
You know the drill.