Sample Learning Assessment Problems (LAP 4)

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.

Write higher-order procedures

Write procedures that take procedures as parameters and return procedures as results.

Write, but do not document, a recursive procedure (split pred? lst), that takes a predicate and a list as parameters and returns a two-element list, the first of which is all the elements for which the predicate holds, and the second of which is all the elements for which the predicate does not hold. You may assume that the predicate is applicable to all elements of the list.

> (split odd? (list 5 1 5 4 2 3 8))
'((5 1 5 3) (4 2 8))
> (split string->number? (list "11" "fred" "one" "22.1" "two"))
'(("11" "22.1") ("fred" "one" "two"))

Write higher-order procedures (Extra)

a. As you may recall, the (left-section proc left) procedure looks like this.

(define left-section
  (lambda (proc left)
    (lambda (right)
      (proc left right))))

In your own words, explain why we have two lambda expressions in `left-section.

b. Consider the following alternate definition of left-section.

(define left-section
  (lambda (proc left)
    (let ([result
           (lambda (right) 
             (proc left right))])
      result)))

Why might someone prefer this version of left-section?

c. Using the strategy of b, write a procedure, (make-multiplier n), that creates a procedure that takes one input and multiplies it by n.

;;; (make-multiplier n) -> procedure?
;;;   n : number?
;;; Create a procedure that multiplies its parameter by n
(define make-multiplier
  (lambda (n)
    undefined))

> (define mul5 (make-multiplier 5))
> (mul5 10)
50
> mul5 1.2)
6.0

Tail recursion

Transform recursive functions into tail-recursive functions.

At times, we may not be sure whether or not a random procedure we write will ever produce a value we expect. Consider, for example, the following procedure.

;;; (random-color) -> string
;;; Generates an "unpredictable" color, with colors appearing in
;;; different frequences.
(define random-color
  (lambda ()
    (let ([val (random 100)])
      (cond
        [(< val 50)
         "red"]
        [(< val 75)
         "blue"]
        [(< val 99)
         "purple"]
        [else
         "lavender"]))))

It can be time-consuming and annoying to type the procedure name again and again and check for the answer. For example, we might want to see if the procedure we wrote ever produces "lavender".

> (random-color)
"purple"
> (random-color)
"blue"
> (random-color)
"red"
> (random-color)
"red"
> (random-color)
"red"
> (random-color)
"blue"

Exciting, isn’t it?

What’s the solution? We can write a procedure that does lots and lots and lots of calls to random-color for us. I’ve generalized it.

;;; (random-experiment rproc val n) -> integer?
;;;    rproc : zero-parameter-procedure?
;;;    val : any?
;;;    n : integer?
;;; Runs rproc n times and counts how many times it equals `val`
(define random-experiment
  (lambda (rproc val n)
    (cond
      [(zero? n)
       0]
      [(equal? (rproc) val)
       (+ 1 (random-experiment rproc val (- n 1)))]
      [else
       (random-experiment rproc val (- n 1))])))

Let’s see how it works.

> (random-experiment random-color "lavender" 1000)
9
> (random-experiment random-color "lavender" 1000)
5
> (random-experiment random-color "red" 1000)
534
> (random-experiment random-color "violet" 1000)
0

Unfortunately, for the number of experiments we will typically do (in the thousands or more), this can build up a lot of delayed +1 expressions, which can slow down our computation. As you know, a typical solution to this problem is to use tail recursion.

Rewrite random-experiment using tail recursion.

Tree recursion

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 (bt "A" ...) 3) appends (tree-level (bt "B" ...) 2) and (tree-level (bt "C" ...) 2).

`(tree-level (bt “B” …) 2) appends …

…

Therefore, (tree-level (bt "B" ...) 2) returns …

(tree-level (bt "C" ...) 2) appends …

…

Therefore, (tree-level (bt "C" ...) 2) returns …

So the final result is …

Alternately, you can do a more traditional trace.

    (tree-level (bt "A" ...) 3)
--> (append (tree-level (bt "B" ...) 2) (tree-level (bt "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
  (bt "A"
      (bt "B"
          (bt "D"
              (bt "G"
                  (bt "K"
                      (empty-tree)
                      (leaf "P"))
                  (empty-tree))
              (leaf "H"))
          (empty-tree))
      (bt "C"
          (bt "E"
              (empty-tree)
              (bt "I"
                  (bt "L"
                      (leaf "Q")
                      (bt "R"
                          (empty-tree)
                          (leaf "S")))
                  (leaf "M")))
          (bt "F"
               (empty-tree)
               (bt "J"
                   (empty-tree)
                   (leaf "N"))))))

Tree recursion

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")

Running time

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)
       (bt/t tree)]
      ; If there's no left subtree, compare the top value to the
      ; largest in the right.
      [(empty-tree? (bt/l tree))
       (max (bt/t tree) (tree-largest (bt/r tree)))]
      ; If there's no right subtree, compare the top value to the
      ; largest in the left
      [(empty-tree? (bt/r tree))
       (max (bt/t tree) (tree-largest (bt/l 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 (bt/t tree) 
            (tree-largest (bt/l tree)) 
            (tree-largest (bt/r tree)))])))

Here’s a sample tree.

(define sample
  (bt 5
      (bt 3
          (bt 6
              (empty-tree)
              (leaf 2))
          (empty-tree))
       (bt 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

Sorting and searchin

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: The vector is sorted.  That is,
;;;   (less-equal? (get-key (vector-ref vec i)) 
;;;                (get-key (vector-ref vec (+ i 1))))
;;;   holds for all reasonable i.  
(define binary-search
  (lambda (vec key get-key less-equal?)
    ; Search a portion of the vector from lower-bound to upper-bound
    (letrec ([search-portion 
               (lambda (lower-bound upper-bound)
                 ; 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)]))))])
      (search-portion 0 (vector-length vec)))))

Sorting and searching

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)

Sorting and searching

Update or modify fundamental searching and sorting algorithms or trace the execution of those algorithms over concrete inputs.

As you may have noted, our “divide and conquer” algorithms, such as binary search or mergesort, follow a common recursive pattern.

• If we have a base case, we’re done; return the “obvious” result.
• If we don’t have a base case
  • Split the input into two halves.
  • Recurse on one half or both halves. Trust the magic recursion fairy that the recursion works.
  • Combine the results back together.

The mergesort algorithm, which, if you have not learned already, you will soon learn, sorts a list as follows.

• Empty lists and singleton lists are already sorted.
• Otherwise
  • Split the list in some way that is convenient
  • Sort each half
  • Merge the two sorted halves together

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.

• Empty lists and singleton lists are already sorted.
• Otherwise
  • Pick a random value from the list
  • Split the list into (a) the values less than or equal to that number and (b) the values strictly greater than that value.
  • Sort each half.

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

Computational thinking

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.

Individual outcomes

Explain the applicability of course material to your own goals or work

Pick an area outside of computer science for which regular expressions might be useful. Describe the applicability of regular expressions to that domain.

Individual outcomes

Ideally, CSC-151 has helped you develop skills beyond just Scheme/Racket programming. Pick one skill you have developed in the class and explain how you intend to use it in the future.