These are sample individual learning assessments of the approximate type and difficulty that you will encounter. They represent the LAs for the third Set of Learning Assessments. In some cases, I’ve included multiple problems to help you explore issues in different ways, especially for more recent topics.
Design and write recursive functions over the natural numbers.
Write a recursive procedure, (bounded-power-of-2 n), that finds the largest power of 2 less than or equal to the positive number n.
(check-equal? (bounded-power-of-2 1)
1
"edge case/base case: 2^0")
(check-equal? (bounded-power-of-2 2)
2
"edge case/base case: 2^1")
(check-equal? (bounded-power-of-2 3)
2
"normal case: small non-power-of-two")
(check-equal? (bounded-power-of-2 7)
4
"normal case: small non-power-of-two")
(check-equal? (bounded-power-of-2 16)
16
"normal case: relatively small power of 2")
(check-equal? (bounded-power-of-2 17)
16
"normal case: relatively small non-power-of-two")
(check-equal? (bounded-power-of-2 72)
64
"normal case: somewhat larger non-powr-of-two")
(check-equal? (bounded-power-of-2 (expt 2 123))
(expt 2 123)
"edge case: large power of 2")
(check-equal? (bounded-power-of-2 (+ (expt 2 123) 123))
(expt 2 123)
"edge case: large non-power of 2")
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.
Design and write functions (potentially recursive functions) that utilize vectors.
Write a procedure, (vector-product nums) that finds the product of the numbers in in a vector that contains only numbers.
(check-equal? (vector-product (vector 4 1 3))
12
"normal case: short vector with 1")
(check-equal? (vector-product (vector -3 1 7 2))
-42
"normal case: includes negatives")
(check-equal? (vector-product (vector 2 3+4i))
6+8i
"normal case: mixed types, includes complex")
(check-equal? (vector-product (vector))
1
"edge case: empty vector")
(check-equal? (vector-product (vector 1 2 3 0))
0
"edge case: includes 0")
Describe or diagram the layout of memory for lists and vectors/arrays.
Consider the following pair structure represented in ASCII art.
+---+---+ +---+---+ +---+---+ +---+---+
| * | *--->| * | *--->| * | *--->| * | / |
+-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+
v | v v
"a" | "e" "f"
v
+---+---+ +---+---+ +---+---+
| * | *--->| / | *--->| * | / |
+-|-+---+ +---+---+ + | +---+
v v
+---+---+ +---+---+
| * | / | | * | * |
+-|-+---+ +-|-+-|-+
v v v
+---+---+ "c" "d"
| / | * |
+---+-|-+
v
"b"
Write the Racket expression to build this structure. (And yes,
you can use cons.)
Here’s an approximate key for ASCII-art pair structures.
(cons "a" "b"): +---+---+
| * | * |
+-|-+-|-+
v v
"a" "b"
(cons "a" null): +---+---+
| * | / |
+-|-+---+
v
"a"
(cons null "b"): +---+---+
| / | * |
+---+-|-+
v
"b"
(cons null null): +---+---+
| / | / |
+---+---+
(cons "a" (cons "b" null)): +---+---+ +---+---+
| * | *--->| * | / |
+-|-+---+ +-|-+---+
v v
"a" "b"
Write programs that produce unpredictable output.
Grinnell has suggested that we make up “random ids” for the students in our classes that we can use in online platforms.
Write a procedure, (random-id), that creates a random six-letter identifier of the form consonant-vowel-consonant-vowel-consonant-vowel, with all letters uppercase.
> (random-id)
PALEQO
> (random-id)
ZEDUMI
Isn’t that fun?
Read and interpret programs involving side-effects, in particular, mutation.
As a part of a vector procedure, a student has the following local recursive helper function.
(define vec-proc
(lambda (v)
(let ([go (lambda (vec a b)
(let ([new-b (vector-ref vec a)]
[new-a (vector-ref vec b)])
(vector-set! vec a new-a)
(vector-set! vec b new-b)))])
........)))
Describe what the go procedure accomplishes. For example, if I call (go v 0 1), what will be the result? Will there be an output?
Write procedures that take procedures as parameters or return procedures as results.
Write a procedure (pipe val list-of-procedures), that takes a value and a list of procedures, and returns the result of applying each procedure in turn. You may not use composition in implementing pipe.
> (pipe "reverse" (list string->list reverse list->string))
"esrever"
> (pipe (string->list "reverse") (list reverse list->string))
"esrever"
> (pipe (reverse (string->list "reverse")) (list list->string))
"esrever"
> (pipe (list->string (reverse (string->list "reverse"))) '())
"esrever"
> (pipe 8 '())
8
> (pipe 9 (list decrement))
8
> (pipe 3 (list sqr decrement))
8
> (pipe 2 (list increment sqr decrement))
8
> (pipe 1 (list increment increment sqr decrement))
8