Problem 1: Extending assoc for Repeated Keys
Topics: Sequential search, assoc,
List recursion
As you may have noted, one potential deficiency of assoc
is that when multiple entries contain the same key,
assoc returns only the first entry with a particular
key.
Write, but do not document, a procedure, (assoc-all
key lst), that
makes a list of all the values in
lst whose car is key.
You need not check the preconditions for this procedure.
Note that assoc-all should return the empty list if
no entry contains the desired key.
For example,
(define people
(list (list "Adams" "Amy" "Architecture")
(list "Jones" "Jack" "Geography")
(list "Jones" "Jane" "Geology")
(list "Smith" "Sarah" "Science")
(list "Jones" "Jenna" "Genetics")))
> (assoc-all "Jones" people)
(("Jones" "Jack" "Geography") ("Jones" "Jane" "Geology") ("Jones" "Jenna" "Genetics"))
> (assoc-all "Smith" people)
(("Smith" "Sarah" "Science"))
> (assoc-all "Davis" people)
()
Problem 2: Documenting assoc-all
Topics: Documentation, Preconditions
Write the six-P documentation for assoc-all.
Problem 3: Finding the First Element
Topics: Binary search, vectors, divide-and-conquer, numeric recursion
As you've observed, when a key is repeated, binary search picks
one value with that key, but not necessarily the first value with
that key. Write, but do not document, a variant,
binary-search-first, that
uses the ideas of binary search to find the first
element in the vector that contains the given key.
You should strive to make your procedure as efficient as possible.
While one strategy for implementing binary-search-first
is to find some value with the given key (which binary search already
does) and then to step left in the vector until you find the first
value with that key, stepping through elements one-by-one is inefficient.
Write your version so that it continues to
“divide and conquer” in its attempt to find the first
element with that key.
Part B: Computing Averages
Topics: Lists, pairs, trees, tree recursion
Finding the average of a list of numbers can be a fairly
straightforward process. For example, if we have
the sum procedure from the list recursion
reading, we could use something like the following.
(define list-sum
(lambda (numbers)
(if (null? numbers)
0
(+ (car numbers) (list-sum (cdr numbers))))))
(define list-length
(lambda (lst)
(if (null? lst)
0
(+ 1 (list-length (cdr lst))))))
(define average-v1
(lambda (numbers)
(/ (list-sum numbers) (list-length numbers))))
However, this implicitly makes two passes over the list, once to do
the sum and once to calculate the length. If we
have very long lists, we might wish to compact
this into a single pass by keeping track of both a sum of the
elements in the list (so-far) as well as the count of the number of
elements in the list (so-far). Essentially, performing the
operations of both code
and length at the same time. For example:
(define average-v2
(lambda (numbers)
(let kernel ((sum-so-far (car numbers))
(count-so-far 1)
(remaining (cdr numbers)))
(if (null? remaining)
(/ sum-so-far count-so-far)
(kernel (+ sum-so-far (car remaining))
(+ count-so-far 1)
(cdr remaining))))))
Alternately, we might try something like the following.
; Given a list of numbers, simultaneously compute the sum and
; length of the list.
(define numbers-info
(lambda (numbers)
(if (null? numbers)
(list 0 0) ; 0 sum, 0 length
(let ((results (numbers-info (cdr numbers))))
(list (+ (car numbers) (car results))
(+ 1 (cadr results)))))))
(define average-v3
(lambda (numbers)
(let ((info (numbers-info numbers)))
(/ (car info) (cadr info)))))
Show the steps used in computing the average of the list
(2 5 7) using average-v2 and
average-v3. That is,
show the key steps the Scheme interpreter goes through in figuring out
this average. For example, if we were showing the steps for
average-v1, we might write:
(average-v1 (2 5 6))
=> (/ (sum (2 5 6)) (length (2 5 6)))
=> (/ (+ 2 (sum 5 6)) (length (2 5 6)))
=> (/ (+ 2 (+ 5 (sum 6))) (length (2 5 6)))
=> (/ (+ 2 (+ 5 (+ 6 (sum ())))) (length (2 5 6)))
=> (/ (+ 2 (+ 5 (+ 6 0))) (length (2 5 6)))
=> (/ (+ 2 (+ 5 6)) (length (2 5 6)))
=> (/ (+ 2 11) (length (2 5 6)))
=> (/ 13 (length (2 5 6)))
=> (/ 13 (+ 1 (length (5 6))))
=> (/ 13 (+ 1 (+ 1 (length (6)))))
=> (/ 13 (+ 1 (+ 1 (+ 1 (length ())))))
=> (/ 13 (+ 1 (+ 1 (+ 1 0))))
=> (/ 13 (+ 1 (+ 1 1)))
=> (/ 13 (+ 1 2))
=> (/ 13 3)
=> 13/3
Problem 5: Garnering Info on Trees
Consider the problem of averaging the values in a number tree.
In one sense, it's very easy: We might use sum-of-number-tree
to sum the values and leaves-in-number-tree (or a variant
thereof) to count the values. But that requires us to traverse
the tree twice.
If our only criterion is conciseness of code, we might even flatten
the number tree and then use one of the procedures from the previous
problem. However, flattening a tree is a relatively expensive procedure
due to the repeated appending within tree-flatten.
Is it possible to do both the summing and counting in trees like we
did with lists? Of course! However, we must take a slightly
different approach than the tail
recursive average-v2. Instead of passing along
results-so-far, we must use basic recursion (as
in numbers-info) to compute the results from
the bottom upward.
Write, but do not document, a procedure
(number-tree-info
ntree)
that returns a list whose first item is the sum of all the numbers in
the tree and whose second item is the total count of numbers in the
tree.
> (number-tree-info (cons 1 (cons 2 (cons (cons 3 4) (cons 5 6)))))
(21 6)
Hint: Think carefully first about your base
case. Then, how will you combine the results of the recursive calls?
Note that once we've written this procedure, computing the average is quite
easy, remarkably like the average-v3 procedure
above.
(define number-tree-average
(lambda (number-tree)
(apply / (number-tree-info number-tree))))
Topics: Trees, higher-order procedures
Document number-tree-info.
Part C: Strings, Characters, and Ciphers
Topics: Characters, strings, higher-order procedures
A substitution cipher is a code that simply replaces one character
with another in a one-to-one fashion. This is the kind of code that
must be broken when solving the typical newspaper puzzle called a
"cryptogram." A special case of this code is called a Caesar cipher,
named for the Roman emperor Julius Caesar, who used it to
communicate with his generals. A Caesar cipher simply shifts each
character to another a certain number of places down the
alphabet. In a Caesar cipher with a shift of 3, the letter A
(character 0) would become D (character 3), P (character 15) would
become S (character 18), and so on. Typically, Y (character 24)
would wrap-around to the front of the alphabet to become B
(character 27, or, actually character 1).
Problem 7: Shifting Characters
Write and document a procedure, (char-shift
character amount) that
shifts the given character the number of places, ignoring any wrap-around.
Problem 8: Making Encoders
Of course, Caesar ciphers are much more interesting when applied
to strings, rather than to individual characters. It is also
natural to think of a cipher as a function from strings to strings,
rather than from numbers to strings. Hence, we'd like a procedure
that builds ciphers.
Write, but do not document, a procedure
(shift-encoder
amount) that returns a procedure
that takes a string as input and produces a string where each character is
replaced by another whose collating sequence number differs from
the original by amount.
You should strive to make your procedure as concise as possible.
> (define encode-1 (shift-encoder 5))
> (encode-1 "HELLO")
"MJQQT"
> (define encode-2 (shift-encoder 2))
> (encode-2 "MJQQT")
"OLSSV"
> (define decode-12 (shift-encoder -7))
> (decode-12 "OLSSV")
"HELLO"
> ((o decode-12 encode-2 encode-1) "WORLD")
"WORLD"
Part D: Playing with Polynomial Procedures
Topics: Higher-order procedures
Problem 9: Terms in a Polynomial
Document and write a procedure, (polynomial-term
c n) that returns
the function c*xn.
For example,
> (define two-x-cubed (polynomial-term 2 3))
> (two-x-cubed 1)
2 ; 2 * 1 * 1 * 1
> (two-x-cubed 3)
54 ; 2 * 3 * 3 * 3
> (two-x-cubed 5)
250 ; 2 * 5 * 5 * 5
> (define three-x-squared (polynomial-term 3 2))
> (three-x-squared 1)
3 ; 3 * 1 * 1
> (three-x-squared 3)
27 ; 3 * 3 * 3
> (three-x-squared 5)
75 ; 3 * 5 * 5
> ((polynomial-term 5 4) 2)
80 ; 5 * 2^4
Problem 10: Polynomial Functions
Write, but do not document, a procedure
(polynomial coefs)
that takes a list of coefficients for the terms x0,
x1, x2, ... of a
polynomial and produces a
function that takes a single value, evaluating the polynomial given
those coefficients at that value.
> (define line (polynomial (list 1 4))) ; Create the polynomial f(x) = 1*x^0 + 4*x^1 = 1 + 4*x
> (line 5) ; Evaluate f(5) = 1 + 4*5
21
> (define cubic (polynomial (list 1 4 3 -2))) ; Create the polynomial g(x) = 1 + 4*x + 3*x^2 - 2*x^3
> (cubic 5) ; Evaluate g(5) = 1 + 4*5 + 3*5^2 - 2*5^3
-154
Note: You should try to make your solution as
concise as possible (even at the potential cost of some efficiency).
Note: Since a polynomial normally has at least one
term, you may assume that the list has at least one term. You need not
check this precondition (or any precondition, for that matter).
