These are sample individual learning assessments of the approximate type and difficulty that you will encounter. They represent the LAs for the fourth LA period.
In some cases, I’ve included multiple problems to help you explore issues in different ways, especially for more recent topics. Some of these problems are likely to be longer than the corresponding problem on the SoLA.
Design and write recursive functions over trees.
(Note that this problem focuses more on tracing tree recursion than on implementing it. We’ve found that tracing tree recursion is too time consuming for a SoLA. But we leave it on as an eample of a kind of procedure you might write.)
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-list). You may have to update your
csc151 library in order to do so.
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"))))))
Design and write recursive functions over trees.
Write the following procedure.
;;; (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.
Space for answer
Note: You can access the primary tree procedures by updating the csc151 library and then using (include csc151/binary-trees-from-lists).
Here are some tests.
(define one-of-many
(lambda (n i primary secondary)
(let ([vec (list->vector (make-list n primary))])
(vector-set! vec i secondary)
(vector->tree vec))))
(check-false (bt-find empty-tree "A")
"Base case: Nothing is in the empty tree")
(check-equal? (bt-find (leaf "A") "A")
"A"
"Simple case: At root, same capitalization")
(check-equal? (bt-find (leaf "a") "A")
"a"
"Simple case: At root, different capitalization")
(check-equal? (bt-find (leaf "alphabet") "ALPHAbet")
"alphabet"
"Simple case: At root, different capitalization")
(check-false (bt-find (leaf "B") "A")
"Simple case: Not in small tree")
(check-false (bt-find (one-of-many 10 2 "C" "D") "E")
"Normal case, not in big tree")
(check-equal? (bt-find (one-of-many 10 0 "E" "zero") "ZERO")
"zero"
"Big tree zero")
(check-equal? (bt-find (one-of-many 10 1 "F" "one") "ONE")
"one"
"Big tree one")
(check-equal? (bt-find (one-of-many 10 2 "G" "two") "TWO")
"two"
"Big tree two")
(check-equal? (bt-find (one-of-many 10 3 "H" "three") "THREE")
"three"
"Big tree three")
(check-equal? (bt-find (one-of-many 10 4 "I" "four") "FOUR")
"four"
"Big tree four")
(check-equal? (bt-find (one-of-many 10 5 "J" "five") "FIVE")
"five"
"Big tree five")
(check-equal? (bt-find (one-of-many 10 6 "K" "six") "SIX")
"six"
"Big tree six")
(check-equal? (bt-find (one-of-many 10 7 "L" "seven") "SEVEN")
"seven"
"Big tree seven")
(check-equal? (bt-find (one-of-many 10 8 "M" "eight") "EIGHT")
"eight"
"Big tree eight")
(check-equal? (bt-find (one-of-many 10 9 "N" "nine") "NINE")
"nine"
"Big tree nine")
Design data structures to separate interface from implementation.
As you saw in the design of trees and directory entries, when we create a new way to structure data, there’s a value of separating the interface to the structure (the procedures we call) from the implementation of the struture (the particular details, such as whether we use an array or list or whatever).
You may recall that we said that names are complex. Some people have only one name. Some people have multi-word last names. Some people have middle names and others do not. Some people have suffixes, like “Jr.”, “Sr.”, or “III”. Some people might also have prefixes to their names, like “King” or “Pope”, but we will ignore those for now.
Here’s the start of a library that is intended to represent the various possibilities for names.
#lang racket
(require csc151)
(require rackunit)
;;; (make-name given middle surname suffix) -> name?
;;; given : string?
;;; middle : string? or #f
;;; surname : string? or #f
;;; suffix : string? or #f
;;; Create a new name from the appropriate components.
(define make-name
(lambda (given middle surname suffix)
(list given middle surname suffix)))
;;; (make-name-1 given) -> name?
;;; given : string?
;;; Create a name for those who have only one name, such as Prince,
;;; Madonna, Cher, or Simon.
(define make-name-1
(lambda (given)
(make-name given #f #f #f)))
;;; (make-name-2 given surname) -> name?
;;; given : string?
;;; surname : string?
;;; Create a name for those who have only a given name and a surname.
;;; One of the most common forms.
(define make-name-2
(lambda (given surname)
(make-name given #f surname #f)))
;;; (make-name-3 given middle surname) -> name?
;;; given : string?
;;; middle : string?
;;; surname : string?
(define make-name-3
(lambda (given middle surname)
(make-name given middle surname #f)))
;;; (make-name-gs given suffix) -> name?
;;; given : string?
;;; suffix : string?
;;; Make a name for someone who has only a given name and a suffix,
;;; such as Elizabeth II or Henry IV.
(define make-name-gs
(lambda (given suffix)
(make-name given #f #f suffix)))
;;; (name? val) -> boolean?
;;; val : any?
;;; Determine if val appears to be a name created by `make-name`
;;; of any of the similar procedures.
(define name?
(let ([string-or-false? (lambda (val) (or (string? val) (not val)))])
(lambda (val)
(and (list? val)
(= 4 (length val))
(string? (given-name val))
(string-or-false? (middle-name val))
(string-or-false? (surname val))
(string-or-false? (suffix val))))))
;;; (given-name name) -> string? or false
;;; name : name?
;;; Determine the given name for a name. Returns false
;;; if there is no given name.
(define given-name
(lambda (name)
(car name)))
;;; (middle-name name) -> string? or false
;;; name : name?
;;; Determine the middle name for a name. Returns false
;;; if there is no middle name.
(define middle-name
(lambda (name)
(cadr name)))
;;; (surname name) -> string? or false
;;; name : name?
;;; Determine the surname for a name. Returns false if there
;;; is no surname.
(define surname
(lambda (name)
(caddr name)))
;;; (suffix name) -> string? or false
;;; name : name?
;;; Determine the suffix for a name. Returns false if there
;;; is no suffix.
(define suffix
(lambda (name)
(cadddr name)))
;;; (name->string) -> string?
;;; name : name?
;;; Convert a name to one of the standard forms, approximately
;;; Given Middle Surname, Suffix
(define name->string
(lambda (name)
(let ([given (given-name name)]
[middle (middle-name name)]
[surn (surname name)]
[suff (suffix name)]
[use (lambda (word pre) (if word (string-append pre word) ""))])
(cond
; Special case: Only first and suffix. We don't use a comma
; before the suffix here.
[(and (not middle) (not surn) suff)
(string-append given " " suff)]
; Normal case
[else
(string-append given
(use middle " ")
(use surn " ")
(use suff ", "))]))))
;;; (name->dirstring) -> string?
;;; name : name?
;;; Convert a name to the standard form used for alphabetization
;;; of names, approximately,
;;; Surname, Given Middle Suffix
(define name->dirstring
(lambda (name)
(let ([given (given-name name)]
[middle (middle-name name)]
[surn (surname name)]
[suff (suffix name)]
[use (lambda (word pre) (if word (string-append pre word) ""))])
(string-append (if surn (string-append surn ", ") "")
given
(use middle " ")
(use suff " ")))))
Here are a few tests of the various procedures working in conjunction.
(check-equal? (name->string (make-name "Barack" "Hussein" "Obama" "II"))
"Barack Hussein Obama, II")
(check-equal? (name->dirstring (make-name "Barack" "Hussein" "Obama" "II"))
"Obama, Barack Hussein II")
(check-equal? (name->string (make-name-3 "George" "Herbert Walker" "Bush"))
"George Herbert Walker Bush")
(check-equal? (name->dirstring (make-name-3 "George" "Herbert Walker" "Bush"))
"Bush, George Herbert Walker")
(check-equal? (name->string (make-name-3 "George" "W." "Bush"))
"George W. Bush")
(check-equal? (name->dirstring (make-name-3 "George" "W." "Bush"))
"Bush, George W.")
(check-equal? (name->string (make-name-2 "Kamala" "Harris"))
"Kamala Harris")
(check-equal? (name->dirstring (make-name-2 "Kamala" "Harris"))
"Harris, Kamala")
(check-equal? (name->string (make-name-1 "SamR"))
"SamR")
(check-equal? (name->dirstring (make-name-1 "SamR"))
"SamR")
(check-equal? (name->string (make-name-gs "Elizabeth" "II"))
"Elizabeth II")
(check-equal? (name->dirstring (make-name-gs "Elizabeth" "II"))
"Elizabeth II")
Update the name structure (the procedures above) to use vectors rather than lists.
Space for answer
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.
Consider the following vector, represented in a way that makes indices and elements clear.
0 : "Addison"
1 : "Adrian"
2 : "Aisley"
3 : "Bailey"
4 : "Beverly"
5 : "Blake"
6 : "Brett"
7 : "Brook"
8 : "Dakota"
9 : "Dallas"
10 : "Dana"
11 : "Ellery"
12 : "Harley"
13 : "Hillary"
14 : "Hunter"
15 : "Jamie"
16 : "Lesley"
17 : "Mackenzie"
18 : "Madison"
19 : "Morgan"
20 : "Parker"
21 : "Quinn"
22 : "Reese"
23 : "Riley"
24 : "Sammie"
25 : "Shawn"
26 : "Taylor"
27 : "Temple"
28 : "Val"
As you may recall, the core of binary-search (code at the end) keeps track of a lower-bound (inclusive) and upper-bound (exclusive) within which we should be able to find the value, if it’s in the vector. For this vector, the lower-bound starts out as 0 and the upper-bound starts out as 29.
a. Give the values of lower-bound, upper-bound, midpoint, and middle-key in each step as binary-search searches this vector in the following call.
(binary-search names "Quinn" (lambda (x) x) string-ci<=?)
For example,
lower-bound: 0, upper-bound: 29
midpoint: 14, middle key "Hunter".
"Quinn" should follow "Hunter".
lower-bound: 15, upper-bound: 29
midpoint: 22, middle key: "Reese"
"Quinn" should precede "Reese"
lower-bound: 15, upper-bound: 22
midpoint: ??: middle-key: ??
...
Space for an answer.
b. Give the values of lower-bound, upper-bound, midpoint, and middle-key in each step as binary-search searches this vector in the following call.
> (binary-search names "Charlie" (lambda (x) x) string-ci<=?)
Space for an answer.
c. Here is the binary search tree created by vector->tree from that vector. How does a binary-tree search that tree relate to the binary search algorithm on the corresponding vector?
> (vector->tree names)
'("Hunter"
("Brook"
("Bailey"
("Adrian" ("Addison" ◬ ◬) ("Aisley" ◬ ◬))
("blake" ("Beverly" ◬ ◬) ("Brett" ◬ ◬)))
("Ellery" ("Dallas" ("Dakota" ◬ ◬) ("Dana" ◬ ◬)) ("Hillary" ("Harley" ◬ ◬) ◬)))
("Reese"
("Madison"
("Lesley" ("Jamie" ◬ ◬) ("Mackenzie" ◬ ◬))
("Parker" ("Morgan" ◬ ◬) ("Quinn" ◬ ◬)))
("Taylor" ("Sammie" ("River" ◬ ◬) ("Shawn" ◬ ◬)) ("Val" ("Temple" ◬ ◬) ◬))))
Space for an answer.
Here’s the binary search algorithm, in case you need it.
;;; (binary-search vec key get-key less-equal?) -> integer?
;;; vec : vector?
;;; get-key? : procedure? unary?
;;; less-equal? : procedure? binary?
;;; Search the vector for a value whose key is key. Returns
;;; the index of the matching element or #f.
;;; get-key is used to extract the keys and less-equal?
;;; specifies the ordering.
;;; Pre: (less-equal? (get-key (vector-ref vec i)) (get-key (vector-ref vec (+ i 1))))
;;; holds for all reasonable i. That is, every element "comes before" the next
;;; element.
(define binary-search
(lambda (vec key get-key less-equal?)
; Search a portion of the vector from lower-bound to upper-bound
(let search-portion ([lower-bound 0]
[upper-bound (vector-length vec)])
; If the portion is empty
(if (>= lower-bound upper-bound)
; Indicate the value cannot be found
#f
; Otherwise, identify the middle point, the element at that
; point and the key of that element.
(let* ([midpoint (quotient (+ lower-bound upper-bound) 2)]
[middle-element (vector-ref vec midpoint)]
[middle-key (get-key middle-element)])
(cond
; If the middle key equals the value, we use the middle value.
[(and (less-equal? key middle-key)
(less-equal? middle-key key))
midpoint]
; If the middle key is too large, look in the left half
; of the region.
[(less-equal? key middle-key)
(search-portion lower-bound midpoint)]
; Otherwise, the middle key must be too small, so look
; in the right half of the region.
[else
(search-portion (+ midpoint 1) upper-bound)]))))))
Update or modify fundamental searching and sorting algorithms or trace the execution of those algorithms over concrete inputs.
(Note: This is a sorting question. You will not receive a sorting question in Spring Term 1 2021. It is left to give you a sense of the kinds of algorithms we normally consder.)
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)
Update or modify fundamental searching and sorting algorithms or trace the execution of those algorithms over concrete inputs.
(Note: This is a sorting question. You will not receive a sorting question in Spring Term 1 2021. It is left to give you a sense of the kinds of algorithms we normally consder.)
As you may have noted, our “divide and conquer” algorithms, such as binary search or mergesort, follow a common recursive pattern.
The mergesort algorithm, which, if you have not learned already, you will soon learn, sorts a list as follows.
Mergesort works relatively well, and is generally faster than insertion sort or selection sort.
However, there are other sorting algorithms. The Quicksort algorithm, discovered by C.A.R. Hoare in the late 1950’s, works similarly to Mergesort, except that the split is a bit more complex. Here’s a variant of Quicksort, tailored to lists.
Consider the list (5 1 9 4 6 3 0 7 8 6). Suppose we pick 6 as the random
value from the list.
a. What values will be in the first sublist (those less than or equal to 6)?
Space for answer
b. What values will be in the right sublist (those strictly greater than 6)?
Space for answer
c. Suppose the magic recursion fairy sorts the first sublist for us. What list will be get?
Space for answer
d. Suppose the magic recursion fairy sorts the second sublist for us. What list will we get?
Space for answer
e. How do we combine those two lists to get a sorted version of the original list?
Space for answer
Explain the details or relevance of some aspect of computational thinking.
In a short note on computational thinking [1], noted computer scientist Jeannette Wing writes,
Computational thinking is used in the design and analysis of problems and their solutions, broadly interpreted. The most important and high-level thought process in computational thinking is the abstraction process. Abstraction is used in defining patterns, generalizing from instances, and parameterization. It is used to let one object stand for many. It is used to capture essential properties common to a set of objects while hiding irrelevant distinctions among them. For example, an algorithm is an abstraction of a process that takes inputs, executes a sequence of steps, and produces outputs to satisfy a desired goal. An abstract data type defines an abstract set of values and operations for manipulating those values, hiding the actual representation of the values from the user of the abstract data type. Designing efficient algorithms inherently involves designing abstract data types. Abstraction gives us the power to scale and deal with complexity.
In CSC 151, we implement algorithms as procedures. Explain in your own words how procedures serve as abstractions.
Space for answer
[1] Wing, Jeannette M. (17 November 2010). “Computational Thinking: What and Why?” Online document available at https://www.cs.cmu.edu/~CompThink/resources/TheLinkWing.pdf. Accessed 13 December 2020.
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.