Design and write functions that utilize dictionaries.
Suppose counts is a dictionary whose keys are words and whose values are integers that represent how many times the word appears in a text. Write a procedure, (total-words counts), that determines the sum of all the numbers in the dictionary.
Note/hint: As you may recall, (hash-keys hash) returns the list of all the keys in a hash table.
Read and write programs involving recursive behavior over trees.
Consider the following procedure.
(define tree-level
(lambda (tree n)
(cond
[(empty-tree? tree)
null]
[(= n 0)
(list (btt tree))]
[else
(append (tree-level (btl tree) (- n 1))
(tree-level (btr tree) (- n 1)))])))
Summarize the steps involved in computing (tree-level t 3) for the
following tree. (You need not do a full trace.)
"A"
/ \
"B" "C"
/ / \
"D" "E" "F"
/ \ \ \
"G" "H" "I" "J"
/ / \ \
"K" "L" "M" "N"
\ / \
"P" "Q" "R"
\
"S"
Your answer will look something like the following.
(tree-level (btn "A" ...) 3)appends(tree-level (btn "B" ...) 2)and(tree-level (btn "C" ...) 2).
`(tree-level (btn “B” …) 2) appends …
…
Therefore,
(tree-level (btn "B" ...) 2)returns …
(tree-level (btn "C" ...) 2)appends …
…
Therefore,
(tree-level (btn "C" ...) 2)returns …
So the final result is …
Alternately, you can do a more traditional trace.
(tree-level (btn "A" ...) 3)
--> (append (tree-level (btn "B" ...) 2) (tree-level (btn "C" ...) 2))
--> ...
Space for answer
Explain, in your own words, what tree-level computes.
Space for answer
Note: You can access the binary-tree library we’ve been using with
(require csc151/binary-trees-from-lists).
Note: Here’s the code for the tree above.
(define sample
(btn "A"
(btn "B"
(btn "D"
(btn "G"
(btn "K"
empty-tree
(leaf "P"))
empty-tree)
(leaf "H"))
empty-tree)
(btn "C"
(btn "E"
empty-tree
(btn "I"
(btn "L"
(leaf "Q")
(btn "R"
empty-tree
(leaf "S")))
(leaf "M")))
(btn "F"
empty-tree
(btn "J"
empty-tree
(leaf "N"))))))
Use a mental model of computation to count the relevant number of operations performed by a function.
The following procedure finds the largest numeric value in a tree of real numbers.
;;; (tree-largest tree) -> real?
;;; tree : treeof real?
;;; Find the largest value in a non-empty tree of real numbers
(define tree-largest
(lambda (tree)
(cond
; Empty trees are an error
[(empty-tree? tree)
(error "Boom!")] ; Isn't that helpful?
; The largest value in a leaf is the leaf
[(leaf? tree)
(btt tree)]
; If there's no left subtree, compare the top value to the
; largest in the right.
[(empty-tree? (btl tree))
(max (btt tree) (tree-largest (btr tree)))]
; If there's no right subtree, compare the top value to the
; largest in the left
[(empty-tree? (btr tree))
(max (btt tree) (tree-largest (btl tree)))]
; Otherwise, we want the largest of (a) the top element, (b)
; the largest in the left subtree, or (c) the largest in the
; right subtree.
[else
(max (btt tree)
(tree-largest (btl tree))
(tree-largest (btr tree)))])))
Here’s a sample tree.
(define sample
(btn 5
(btn 3
(btn 6
empty-tree
(leaf 2))
empty-tree)
(btn 1
(leaf 4)
(leaf 7))))
Determine how many times max will be called in evaluating (tree-largest sample).
You may either (a) use your mental model of computation, (b) instrument the code to print or count, or (c) logically analyze the code. In addition to the final count, show your work—either (a) an execution trace if you use your mental model, (b) the instrumented code if you instrument the code, or (c) an explanation of your analysis, if you analyze. You can also do more than one of those, if you’d like to check yourself.
Space for answer
Update or modify fundamental searching and sorting algorithms or trace the execution of those algorithms over concrete inputs.
The selection sort algorithm works by repeatedly finding the smallest or largest value in a list or vector and then putting it in the right position. Here’s a mediocre implement of selection sort with lists.
;;; (selection-sort nums) -> listof real?
;;; nums : listof real?
;;; Create a sorted version of nums. Each element is no larger than
;;; the next element.
(define selection-sort
(lambda (nums)
(letrec ([helper
(lambda (unsorted sorted)
(if (null? unsorted)
sorted
(let ([largest (reduce max unsorted)])
(helper (remove largest unsorted)
(cons largest sorted)))))])
(helper nums null))))
Trace the operation of selection-sort on the list '(6 1 2 8 4 7 3). You need not (and should not) show the steps in reduce or remove.
For example, if we started with the list '(1 3 5 4 2), you might write something like the following
(selection-sort '(1 3 5 4 3))
--> (helper '(1 3 5 4 3) '())
; largest is 5
--> (helper (remove 5 '(1 3 5 4 2)) (cons 5 '()))
--> (helper '(1 3 4 3) '(5))
; largest is 4
--> (helper (remove 4 '(1 3 4 2)) (cons 4 '(5)))
--> (helper '(1 3 3) '(4 5))
; largest is 3
--> (helper (remove 3 '(1 3 3)) (cons 3 '(4 5)))
--> (helper '(1 3) '(3 4 5))
; largest is 3
--> (helper (remove 3 '(1 3)) (cons 3 '(3 4 5)))
--> (helper '(1) '(3 3 4 5))
; largest is 1
--> (helper (remove 1 '(1)) (cons 1 '(3 3 4 5)))
--> (helper '() '(1 3 3 4 5))
--> '(1 3 3 4 5)
Understand and explain the perspective of those different from you, particularly as it may relate to the development or use of software.
Describe two cultural differences you encountered in working with other students (e.g., in terms of approaches to work, considerations of authority, willingess to accept errors) and how you were able to resolve them.