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.
You’re already seen a sample HOP problem. But students asked for another. I wrote an evil one.
Consider the following procedure.
(define silly
(lambda (lst)
(map (lambda (x) (sqr (+ 1 x)))
(filter odd? lst))))
Rewrite the procedure using o and section so that it has no lambdas.
Notes:
o when you want to sequence actions. (Do this to the parameter,
then this to the result, then this to the next result, and so on and
so forth.)section when you want to fill in one or more parameters to a procedure, thereby creating a new procedure.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 of 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)
"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")
Design and write functions (potentially recursive functions) that utilize vectors.
Consider the following recursive procedure that adds all of the numbers in a vector of numbers.
(define vector-sum
(lambda (vec)
(let ([len (vector-length vec)])
(letrec ([helper
(lambda (pos)
(if (< pos len)
(+ (vector-ref vec pos)
(helper (+ pos 1)))
0))])
(helper 0)))))
Trace the evaluation of (vector-sum (vector 3 5 7 11)). You can skip to the consequent or alternate of the if without showing the if iteself. You can also do simple steps (e.g., adding one or looking up a value in a vector) in parallel.
(vector-sum '#(3 5 7 11))
--> (helper 0)
; 0 < 4
--> (+ (vector-ref vec 0) (helper (+ pos 1)))
--> (+ 3 (helper 1))
Design and write functions (potentially recursive functions) that utilize vectors.
Consider the following recursive procedure that adds all of the numbers in a vector of numbers.
(define vector-sum
(lambda (vec)
(let ([len (vector-length vec)])
(letrec ([helper
(lambda (pos sum-so-far)
(if (< pos len)
(helper (+ pos 1)
(+ sum-so-far (vector-ref vec pos)))
sum-so-far))])
(helper 0 0)))))
Trace the evaluation of (vector-sum (vector 3 5 7 11)). You can skip to the consequent or alternate of the if without showing the if iteself. You can also do simple steps (e.g., adding one or looking up a value in a vector) in parallel.
(vector-sum '#(3 5 7 11))
--> (helper 0 0)
; 0 < 4
--> (helper (+ pos 1) (+ 0 (vector-ref vec pos)))
--> (helper 1 (+ 0 3))
--> (helper 1 3)
Design and write functions (potentially recursive functions) that utilize vectors.
Write a procedure, (vector-swap-neighbors! vec) that takes an even-length vector as a parameter and swaps the neighboring elements (those at indices 0 and 1, those at indices 2 and 3, etc.).
> (define vec (vector 'a 'b 'c 'd 'e 'f))
> (vector-swap-neighbors! (vector 'a 'b 'c 'd 'e 'f))
> vec
'#(b a d c f e)
Hint: You will find a let binding helpful.
Note: I have not mad the vector as a result of vector-swap-neighbors!. You may choose to do so if you’d like.
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.
As you may recall, we wrote a roll-a-die procedure that we used in our initial explorations of randomness.
;;; (roll-a-die) -> integer?
;;; Simulate the rolling of a die by returning an unpredictable
;;; integer between 1 and 6, inclusive.
(define roll-a-die
(lambda ()
(+ (random 6) ; a value in the range [0 .. 5]
1))) ; now in the range [1 .. 6]
Of course, not all dice are six-sided. Write a procedure, (roll-n-sided-die n), that rolls an n-sided die.
;;; (roll-n-sided-die n) -> integer?
;;; Simulate the rolling of a die by returning an unpredictable
;;; integer between 1 and n, inclusive.
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 you’ve written recursive procedures over vectors, you may have discovered a problem: Recursive vector procedures require us to sequence steps in a different way than normal. Rather than nesting expressions to sequence, we really need to say “do this expression and then do this independent expression”. The if keyword doesn’t seem to work for that.
Consider the following procedure, which attempts to add one to each element in a vector of numbers.
;;; (vector-increment? vec) -> vectorof integer?
;;; vec : vectorof integer?
;;; Add one to all elements in vec.
(define vector-increment!
(lambda (vec)
(let ([len (vector-length vec)])
(letrec ([helper!
(lambda (pos)
(if (= pos len)
; If we've reached the end, return the vector
vec
; Otherwise, increment the given position
(vector-set! vec pos (+ 1 (vector-ref vec pos)))
; And move on to the next position
(helper! (+ pos 1))))])
(helper! 0)))))
If we try to run this code, we get the following error.
if: bad syntax in: (if (= pos len) vec (vector-set! vec pos (+ 1 (vector-ref vec pos))) (helper! (+ pos 1)))
Why? Because if can only have one consequent.
You should know at least five ways to write a procedure that sequences expressions, although not all may be applicable to this particular situation. Give three.
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 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.