This class will be recorded! Its use is limited to members of the class. Please do not share with others.
This eboard will be removed at the end of the semester.
Approximate overview
Mini Projects
Readings
Quizzes
Other
How do I update the csc151 library?
Go to File->Install Package
Enter
https://github.com/grinnell-cs/csc151.git
Click “Update”
Can we take advantage of other knowledge on the LAs, such as numeric recursion on the list recursion problem?
Yes
Will you answer questions on individual LAs?
No. Not everyone is taking the LAs at the same time, so we won’t get uniformity of access to Sam’s answers.
Will you fix errors on the LAs if we notice them and tell you?
Yes.
Will you answer questions on comments on previous SoLAs?
Not in public.
Tell me about SoLA 5
SoLA 5 assigned Monday morning.
You can do as many or as few problems as you’d like.
I would not recommend re-doing any you have credit for.
Look at the targets
Can we really get an A with one R on the MPs?
Yes
Do we have to speak in letters?
No.
Do we still have 28 LAs?
Yes.
Do we still have 25 quizzes, reading self-checks, and labs
Probably not. I’ll have numbers tomorrow.
When are we getting grades for readings and labs?
Probably this weekend. Maybe sooner.
(define sample
(btn 5
(btn 3
(btn 11
empty-tree
(btn 6
(leaf 4)
(btn 1
(leaf 2)
(leaf 4))))
empty-tree)
(btn 7
(leaf 8)
(btn 9
empty-tree
(leaf 0)))))
(define bt-sum
(lambda (tree)
(if (empty-tree? tree)
0
(+ (btt tree))
(bt-sum (btl tree))
(bt-sum (btr tree)))))
Option 1: Like normal, eliding as necessary
(bt-sum sample)
---> (bt-sum (btn 5 (btn 3 ...) (btn 7 ...)))
---> (+ 5 (bt-sum (btn 3 ...) (bt-sum (btn 7 ...))))
---> (+ 5 (bt-sum (btn 3 (btn 11 ...) empty-tree)) (bt-sum (btn 7 ...))_
---> (+ 5 (+ 3 (bt-sum (btn 11 ...)) (bt-sum empty-tree)) (btn 7 ...))
---> (+ 5 (+ 3 (+ 11 (bt-sum empty-tree) (bt-sum (btn 6 ...))) (bt-sum empty-tree)) (bt-sum (btn 7 ...)))
---> (+ 5 (+ 3 (+ 11 0 (bt-sum (btn 6 ...))) (bt-sum empty-tree)) (bt-sum (btn 7 ...)))
---> ...
Option 2: With the magic recursion fairy, returning later
(bt-sum sample)
---> (bt-sum (btn 5 (btn 3 ...) (btn 7 ...)))
---> (+ 5 (bt-sum (btn 3 ...)) (bt-sum (btn 7 ...)))
---> (+ 5 31 24)
---> 60
Left subtree
---> (btsum (btn 3 (btn 11 ...) empty-tree))
---> (+ 3 (bt-sum (btn 11 ...) empty-tree))
---> (+ 3 28 0)
---> 31
Right subtree
...
Sam likes the latter as a way of checking the design of recursive procedures. If the recursive calls work, am I getting what I expected?
Elided
Elided
Elided
Elided
Elided
Elided
Elided
What kinds of problems might you ask for divide-and-conquer
We’ve seen three major divide-and-conquer algorithms
I might ask you to trace one of those.
I might ask you to trace a variant of one of those.
I might ask you to figure out a variant of one of those.
I usually add displays
The normal form is
(display "STRING") (newline)
Detailed example elided
If we change the value associated with a key, what happens to the old value?
Bye bye.
So what do we do if we want to keep the old value?
Temporary: Use a variable (e.g., let statement).
Longer term: Associate it with another key.
Elided
;;; (bt-find tree str) -> string? or boolean?
;;; tree : treeof string?
;;; str : string?
;;; Find a string equal to string (ignoring case) in tree. If
;;; no such string exists, return false.
(define bt-find
(lambda (tree str)
(if (empty-tree? tree)
#f
(or (if (string-ci=? str (btt tree)) (btt tree) #f)
(bt-find (btl tree) str)
(bt-find (btr tree) str)))))
Let’s employ the ZoB.
(define bt-find
(lambda (tree str)
(if (empty-tree? tree)
#f
(or (and (string-ci=? str (btt tree)) (btt tree))
(bt-find (btl tree) str)
(bt-find (btr tree) str)))))
(define bt-find
(lambda (tree str)
(and (not (empty-tree? tree))
(or (and (string-ci=? str (btt tree)) (btt tree))
(bt-find (btl tree) str)
(bt-find (btr tree) str)))))
Note: (and E1 E2 E3) returns
Note: (or E1 E2 … En) returns
Aother approach: start with tree-contains?
(define binary-tree-contains?
(lambda (tree val)
(cond
[; The empty tree contains no values
(empty-tree? tree)
#f]
[; If the value is at the top, the tree contains the value
(equal? (btt tree) val)
#t]
[; If the left subtree contains the value, the tree contains the value
(binary-tree-contains? (btl tree) val)
#t]
[; If the right subtree contains the value, the tree contains the value
(binary-tree-contains? (btr tree) val)
#t]
[; If none of these cases hold, the tree does not contain the value
else
#f])))
(define bt-find
(lambda (tree str)
(cond
[; The empty tree contains no values
(empty-tree? tree)
#f]
[; If the value is at the top, the tree contains the value
(string-ci=? (btt tree) str)
(btt tree)]
[; If the left subtree contains the value, the tree contains the value
(bt-find (btl tree) str)
]
[; If the right subtree contains the value, the tree contains the value
(bt-find (btr tree) str)
]
[; If none of these cases hold, the tree does not contain the value
else
#f])))