(expmod a b c)
from the book which efficiently
computes the value a^b mod c
(define (square x) (* x x)) (define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m)) (else (remainder (* base (expmod base (- exp 1) m)) m))))
expmod
to verify that the cipher text you found
above decrypts properly back to the numeric encoding for
abstract.
(nk) =
n!/k!*(n-k)!
This exercise requires to use the recursive process described in the
exercise instead of using the factorial function.
(define x (list (list 1 2) (list 3 4))) STk> (fringe x) (1 2 3 4) STk> (fringe (list x x)) (1 2 3 4 1 2 3 4)
string-to-frequency-list
. This procedure
should take in a string, and return a list of symbol-frequency
pairs. An example of symbol-frequency pair is the list (#\h
2)
. #\h
is the symbol (remember #\h
is a character, not an actual scheme symbol), and 1 is the frequency, or
the number of times #\h
appeared in some string we wanted
to encode. str2frequency-list
must return a list of
these frequency pairs, one pair for each unique character in the
string passed to string-to-frequency-list.
(string-to-frequency-list "hello")
should return the list:
((#\h 1) (#\e 1) (#\l 2) (#\o 1))
, or a similar list with
a different ordering of the symbol-frequency pairs.
The procedure string->list
is built into STk, and may be
useful to you. It takes in a string and returns the list containing
each of the characters in the string in the order they appear in the
string. So for instance (string->list "hello")
would return
the list (#\h #\e #\l #\l #\o)
.
string-to-frequency-list
is more complicated
than procedures in prior labs. Plan how to decompose the problem into
simpler problems before you start writing your procedure.
You can come up with your own solution, or follow the steps outlined here:
(unique L)
which will examine a
list and return a sublist with all duplicates removed. For example
(unique (list 3 1 3 4 1))
would return a list like
(3 1 4)
which has the duplicate elements removed.(member x lst)
to check if x
is list
lst
. (count-occurrences obj L)
which
will count the number of times obj
appears in the list
L
.=
operator, but this only works for numbers. To test
if x
and y
are the same for more general
kinds of data you can use (eqv? x y)
. unique
and string->list
functions.) Ideally you you will use the map
function to
recurse over this list.
Use count-occurences
to generate the frequencies
for each unique character during your recursive or iterative process.
Useful procedures for the bonus question:
(member obj lst)
returns a
nonfalse value if obj
is found in list lst
or
#f
otherwise. More precisely, if obj
is
in the list lst
it will return the list starting at
obj
.(eqv? obj1 obj2)
returns
#t
if obj1
and obj2
are the same.
It works for numbers, characters, and symbols, but not for lists.
To compare characters you can also use (char=? char1 char2)
(string->list str)
returns a list of characters contained in string str
.(set-color! (draw-line 0 0 20 0) 'green)
to set the color of the line to green.
(random n)
returns a random number in the
interval 0 to n.
(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))We define the memoizer as
(define (memoize f) (let ((table (make-table))) (lambda (x) (let ((previously-computed-result (lookup x table))) (or previously-computed-result (let ((result (f x))) (insert! x result table) result))))))The memoized version of the fibonacci procedure is
(define memo-fib (memoize (lambda (n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (memo-fib (- n 1)) (memo-fib (- n 2))))))))
(fib 30)
and
(memo-fib 30)
.
Did you notice a difference in the time to compute them? fib
for increasingly larger numbers.
Stop when the computation takes approximatively more than 1 minute.
Write down the largest number for which you computed fib
.
memo-fib
.
What is the largest number for which you can compute memo-fib
?
Is this much larger than what you found for fib
?
memo-fib
computes the nth Fibonacci number in
a number of steps proportional to n instead of being exponential in n
as for fib
.
memo-fib
still work if we had simply defined
memo-fib
to be (memoize fib)
?
Why or why not? explain your reasoning.