If you are a Caltech CS 1 student, please do not consult these solutions before submitting your midterm. To do so is a violation of the Caltech honor code. Otherwise, scroll down.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
This exam is due Tuesday, November 6, at 5pm. Please submit your text answers electronically as the cs1man "assignment" called midterm.
The time limit on this exam is five hours. However, you are permitted to take the exam in non-consecutive sessions which add up to five hours, providing that you do not attend any CS 1 lecture, lab session, or recitation session between the time you start and the time you finish, and that you adhere to all of the rules below for the entire time between the time you start and the time you finish.
Note also that if you run out of time before you finish your exam, you may write on your exam where you ran out of time and continue after that. We will probably award partial credit for work done after the time limit, but don't overdo it (if it takes you too long, you're probably going to get it wrong anyway).
This is a closed-book exam.
This is a no reference exam, with these exceptions:
You may consult your lab submissions or a copy of them, as well as any responses from your TA to those submissions, during this exam.
You may consult the PDF versions of the CS 1 lectures. However, do not print out the lectures on the CS cluster printer (in Jorgensen room 154) unless you already have done so -- we don't want the CS cluster printer getting hammered during midterm week. If you own a printer you can print them out on that.
You may consult the Scheme standard, located here, if you want to check on the definition of any Scheme procedure. Be careful about this, though; you don't want to spend your exam time browsing through a lot of reference material (use the index!).
This is a closed interpreter exam. You may not use DrScheme or any other Scheme interpreter.
Here is how your exam should be formatted. Note that we will deduct a significant proportion of your midterm grade (up to 1/4 of the total grade) if you violate any of these rules. If you have any questions about these rules, contact us before starting the exam and we'll clarify them.
Type up your exam in any plain text editor of your choice.
We recommend that you use an editor like emacs that can
match parentheses, but you can use vi, pico,
gedit or any other editor that can save text in plain text
format.
You are not allowed to use DrScheme to write your exam, even if you just intend to use it as a text editor. Therefore, you might want to spend a little time before you start the exam getting familiar with another text editor.
Your midterm exam should all be in a single plain text file
called "midterm.txt" (that exact name; not
"cs1midterm", "midterm",
"mymidterm" or anything else). You should write your full
name and your CS cluster login name in the first couple of lines of the
file.
Do not submit code in non-plaintext form; Microsoft Word documents and PDFs are examples of non-plaintext formats. Again, Microsoft Word documents and PDFs are not acceptable submission formats! If you do not know what format your editor saves its files in, you should ask someone more knowledgeable (like your TA) to help you.
Make sure that all of the lines in your midterm file have no more than 80 characters in a line. We have to print it out to grade it, and our printer will truncate lines that are more than 80 columns. Most text editors will show you what column you're on as you're editing, so this will help you keep the line lengths to a maximum of 80 characters.
If you did not read the preceding formatting rules, go back and read them now. Remember: you will lose a lot of marks for not following the rules!
We recommend that you use an editor that matches parentheses (like
emacs), but know that we are not grading you on whether
your code is "perfect"; we have Scheme interpreters to tell us that.
Instead, we are looking for correctness at a higher level. A missing
parenthesis here or there will not affect your score (but don't overdo
it).
There is no collaboration on this exam. Show us what you know. Do not discuss the exam with anyone before the final due date for it, even if you both have turned in your answers already.
You may not attend any CS 1 lecture, recitation, or review session between the time you start the exam and the time you complete it. You should complete the exam before you attend it, start the exam after you attend it, or not attend it.
The exam will receive a floating-point score between 0.0 and 6.0, based on your performance across all of the problems. Each section is worth an equal amount (1.5 out of 6.0). The exam is thus worth 6.0 marks out of a maximum of 61.0 marks for the entire course, or about 10% of your final grade.
If you need a clarification of anything on the exam after you've started writing it, you may send email to Mike, Donnie, or Joseph. You can pause your exam while you wait for us to answer.
Each section is worth an equal amount of points: 1.5 marks out of 6.0 total. The subproblems in each section are also worth an equal amount unless otherwise indicated.
Please evaluate the following examples of Scheme code using the substitution model. Show all the steps in the evaluation. To save time, we will allow these shortcuts:
writing e.g. + ==> + instead of
+ ==> [primitive procedure +]
writing e.g. (lambda (x) ...) ==> itself
instead of copying the entire lambda expression
abbreviating the body of long lambda expressions using ellipses
(...); e.g. writing (lambda (x y z)
...)) instead of (lambda (x y z) (* (+ x z) (- y z)
(square (- x z)))). Only do this if it's clear from the context
which lambda expression you mean.
reducing single combinations which involve only numbers and primitive
procedures in one step
e.g. (= 2 0) ==> #f
and (- 2 1) ==> 1.
Note that if there are variables in the combination e.g.
(+ 2 x) then you have to evaluate it
explicitly.
However, aside from these shortcuts, do not skip any steps. In
particular, we want you to explicitly evaluate all defines and
explicitly desugar function definitions which don't use lambdas.
We also want you to explicitly evaluate numbers to themselves, unless they
are part of an expression which only contains numbers and primitive
procedures as described above. Also, indent your work appropriately to show
where you are in the evaluation; this will make it much easier to grade.
(define (f x y) (* (- x 5) (+ x y))) (define (g x) (+ (f x 9) (f (* 2 x) (- x 1)))) (g 4)
(define (f x y) (* (- x 5) (+ x y)))
* Desugar to (define f (lambda (x y) (* (- x 5) (+ x y))))
* define is a special form. Evaluate 2nd operand, bind to 1st operand.
* Evaluate (lambda (x y) (* (- x 5) (+ x y))) --> itself
* Bind lambda expression to name "f"
(define (g x) (+ (f x 9) (f (* 2 x) (- x 1))))
* Desugar to (define g (lambda (x) (+ (f x 9) (f (* 2 x) (- x 1)))))
* define is a special form. Evaluate 2nd operand, bind to 1st operand.
* Evaluate (lambda (x) (+ (f x 9) (f (* 2 x) (- x 1)))) --> itself
* Bind lambda expression to name "g"
(g 4)
* Evaluate 4 --> 4
* Evaluate g --> (lambda (x) (+ (f x 9) (f (* 2 x) (- x 1))))
* Apply lambda expression to 4
* Substitute x=4 in (+ (f x 9) (f (* 2 x) (- x 1)))
--> (+ (f 4 9) (f (* 2 4) (- 4 1)))
* Evaluate (+ (f 4 9) (f (* 2 4) (- 4 1)))
* Evaluate (f 4 9)
* Evaluate 4 --> 4
* Evaluate 9 --> 9
* Evaluate f --> (lambda (x y) (* (- x 5) (+ x y)))
* Apply lambda expression to 4, 9
* Substitute x=4, y=9 in (* (- x 5) (+ x y)) --> (* (- 4 5) (+ 4 9))
* Evaluate (* (- 4 5) (+ 4 9))
* Evaluate (- 4 5) --> -1
* Evaluate (+ 4 9) --> 13
* Evaluate * --> *
* Apply * to -1, 13 --> -13
* Evaluate (f (* 2 4) (- 4 1))
* Evaluate (* 2 4) --> 8
* Evaluate (- 4 1) --> 3
* Evaluate f --> (lambda (x y) (* (- x 5) (+ x y)))
* Apply lambda expression to 8, 3
* Substitute x=8, y=3 in (* (- x 5) (+ x y)) --> (* (- 8 5) (+ 8 3))
* Evaluate (* (- 8 5) (+ 8 3))
* Evaluate (- 8 5) --> 3
* Evaluate (+ 8 3) --> 11
* Evaluate * --> *
* Apply * to 3, 11 --> 33
* Evaluate + --> +
* Apply + to -13, 33 --> 20
(define (woot a b)
(if (> a b)
(+ 3 a b)
(aww (+ b 2) a)))
(define (aww a b)
(if (odd? b)
(woot (+ a 3) (- b 5))
(aww (+ 1 a) (- b a))))
(woot 3 7)
;; Hint: Here's a very abbreviated evaluation to keep you on track:
;; (woot 3 7)
;; --> (aww 9 3)
;; --> (woot 12 -2)
;; --> (+ 3 12 -2)
;; --> 13
(define (woot a b) (if (> a b) (+ 3 a b) (aww (+ b 2) a)))
* Desugar to
(define woot (lambda (a b) (if (> a b) (+ 3 a b) (aww (+ b 2) a))))
* define is a special form. Evaluate 2nd operand, bind to 1st operand.
* Evaluate (lambda (a b) (if (> a b) (+ 3 a b) (aww (+ b 2) a))) --> itself
* Bind procedure to name "woot"
(define (aww a b) (if (odd? b) (woot (+ a 3) (- b 5)) (aww (+ 1 a) (- b a))))
* Desugar to
(define aww
(lambda (a b)
(if (odd? b) (woot (+ a 3) (- b 5)) (aww (+ 1 a) (- b a)))))
* define is a special form. Evaluate 2nd operand, bind to 1st operand.
* Evaluate
(lambda (a b) (if (odd? b) (woot (+ a 3) (- b 5)) (aww (+ 1 a) (- b a))))
--> itself
* Bind procedure to name "aww"
(woot 3 7)
* Evaluate 3 --> 3
* Evaluate 7 --> 7
* Evaluate woot --> (lambda (a b) (if (> a b) (+ 3 a b) (aww (+ b 2) a)))
* Apply lambda expression to 3, 7
* Substitute a=3, b=7 into (if (> a b) (+ 3 a b) (aww (+ b 2) a)) -->
(if (> 3 7) (+ 3 3 7) (aww (+ 7 2) 3))
* Evaluate (if (> 3 7) (+ 3 3 7) (aww (+ 7 2) 3))
* if is a special form. Evaluate 1st operand.
* Evaluate (> 3 7) --> #f. Evaluate 3rd operand.
* Evaluate (aww (+ 7 2) 3)
* Evaluate (+ 7 2) --> 9
* Evaluate 3 --> 3
* Evaluate aww -->
(lambda (a b)
(if (odd? b) (woot (+ a 3) (- b 5)) (aww (+ 1 a) (- b a))))
* apply lambda expression to 9, 3
* Substitute a=9, b=3 into
(if (odd? b) (woot (+ a 3) (- b 5)) (aww (+ 1 a) (- b a))) -->
(if (odd? 3) (woot (+ 9 3) (- 3 5)) (aww (+ 1 9) (- 3 9)))
* Evaluate (if (odd? 9) (woot (+ 9 3) (- b 5)) (aww (+ 1 9) (- 3 9)))
* if is a special form. Evaluate 1st operand.
* (odd? 3) --> #t. Evaluate 2nd operand.
* Evaluate (woot (+ 9 3) (- 3 5))
* Evaluate (+ 9 3) --> 12
* Evaluate (- 3 5) --> -2
* Evaluate woot -->
(lambda (a b) (if (> a b) (+ 3 a b) (aww (+ b 2) a)))
* apply lambda expression to 12, -2
* Substitute a=12, b=-2 into
(if (> a b) (+ 3 a b) (aww (+ b 2) a)) -->
(if (> 12 -2) (+ 3 12 -2) (aww (+ -2 2) 12))
* Evaluate (if (> 12 -2) (+ 3 12 -2) (aww (+ -2 2) 12))
* if is a special form. Evaluate 1st operand.
* (> 12 -2) --> #t. Evaluate 2nd operand.
* (+ 3 12 -2) --> 13
(define (make-switch f g pred?)
(lambda (x y)
(if (pred? x y)
(lambda (x) (f x y))
(lambda (x) (g y x)))))
(define sw (make-switch * - <))
((sw 3 8) 4)
;; Hint: Here's a very abbreviated evaluation to keep you on track:
;; ((sw 3 8) 4)
;; --> ((lambda (x) (* x 8)) 4)
;; --> 32
(define (make-switch f g pred?)
(lambda (x y)
(if (pred? x y)
(lambda (x) (f x y))
(lambda (x) (g y x)))))
* Desugar to:
(define make-switch
(lambda (f g pred?)
(lambda (x y)
(if (pred? x y)
(lambda (x) (f x y))
(lambda (x) (g y x))))))
* define is a special form. Evaluate 2nd operand, bind to 1st operand.
* Evaluate (lambda (f g pred?)
(lambda (x y)
(if (pred? x y)
(lambda (x) (f x y))
(lambda (x) (g y x))))) --> itself
* bind lambda expression to name "make-switch"
(define sw (make-switch * - <))
* define is a special form. Evaluate 2nd operand, bind to 1st operand.
* Evaluate (make-switch * - <)
* Evaluate * --> *
* Evaluate - --> -
* Evaluate < --> <
* Evaluate make-switch --> (lambda (f g pred?)
(lambda (x y)
(if (pred? x y)
(lambda (x) (f x y))
(lambda (x) (g y x)))))
* apply lambda expression to *, -, <
* Substitute f=*, g=-, pred?=< into (lambda (x y)
(if (pred? x y)
(lambda (x) (f x y))
(lambda (x) (g y x)))) -->
(lambda (x y)
(if (< x y)
(lambda (x) (* x y))
(lambda (x) (- y x))))
* Evaluate (lambda (x y)
(if (< x y)
(lambda (x) (* x y))
(lambda (x) (- y x)))) --> itself
* bind lambda expression to name "sw"
((sw 3 8) 4)
* Evaluate 4 --> 4
* Evaluate (sw 3 8)
* Evaluate 3 --> 3
* Evaluate 8 --> 8
* Evaluate sw --> (lambda (x y)
(if (< x y)
(lambda (x) (* x y))
(lambda (x) (- y x))))
* apply lambda expression to 3, 8
* Substitute x=3, y=8 into (if (< x y)
(lambda (x) (* x y))
(lambda (x) (- y x))) -->
(if (< 3 8)
(lambda (x) (* x 8)) *** LAMBDA SHIELDING ***
(lambda (x) (- 8 x))) *** LAMBDA SHIELDING ***
* Evaluate (if (< 3 8)
(lambda (x) (* x 8))
(lambda (x) (- 8 x)))
* if is a special form. Evaluate 1st operand.
* (< 3 8) --> #t. Evaluate 2nd operand.
* Evaluate (lambda (x) (* x 8)) --> itself
* apply lambda expression to 4
* Substitute x=4 into (* x 8) --> (* 4 8)
* Evaluate (* 4 8) --> 32
Five functions are listed below. For each function, do the following things:
Deduce its (worst-case) asymptotic time complexity with respect to
one of the function arguments. Use big-O notation, but give the tightest
bound you can (in other words, write the answer using big-O but really give
the big-theta value). Indicate which function argument the complexity
refers to. For instance, a function of two variables x
and y might be O(x) or O(y) (or
something else). Be clear about this (don't just write "linear" or
"exponential" or you'll lose marks). If there are functions with
exponential complexity you should indicate what the base of the exponential
is (but not for functions with logarithmic complexity, as we explained in
class).
Explain the reasoning you used to deduce the asymptotic time complexity. This should be only a couple of sentences, or at most a short paragraph (don't get carried away; just give us the general idea).
(define (triangle n)
(if (= n 0)
0
(+ n (triangle (- n 1)))))
O(n). Computes triangular number n; there are exactly n+1 calls to triangle and each is constant time.
(define (harder n)
(define (harder-iter a b)
(cond ((= b n) 0)
((= a n) (harder-iter 0 (+ b 1)))
(else (+ 1 (harder-iter (+ a 1) b)))))
(harder-iter 0 0))
Computes n^2 by iterating over a two dimensional array and adding one for each element. For each b, a runs from 0 to n so we have O(n) for each b, and b runs from 0 to n, so O(n) b's makes O(n*n). Each call is constant time.
(define (sum-same x)
(if (< x 1)
x
(+ (* x x) (* (sum-same (- x 1)) (sum-same (- x 1))))))
O(2^x). There are x layers of function calls, and each layer has double the previous number of calls. Thus there are 2^x calls in the last layer (and 2^x - 1 calls in all the previous layers) and each call is constant time.
(define (bouncy y)
(define (bouncy-iter h k)
(if (> k y)
h
(bouncy-iter (+ h 1) (* k 2))))
(bouncy-iter 0 1))
O(log y). Computes floor(log_2(y) + 1) via multiplicative iteration. There are log y calls made to the internal procedure, as the controlling term k starts at 1 and doubles with each call until it is greater than y. Each call has a constant number of operations. Note that the size of y is what limits the number of doublings of k, so the overall time complexity is a function of y.
(define (odd-sum j)
(define (odd-internal k)
(if (< k 1)
0
(+ (triangle j) ;; defined in (a) above
(odd-internal (/ k 2)))))
(odd-internal j))
O(j log j). Computes (triangle j)*(log_2 j), by adding triangle j and decreasing j by a factor of 2. Each call has a O(j) operation (triangle j) and there are O( log j) calls, so O( j log j).
An interesting way of representing a real number is as a list of positive
integers using what is known as a "continued fraction". A continued fraction
representation of a real number x looks like this:
with the numbers a1, a2, etc. all integers
greater than zero. The continued fraction representation is usually written
more concisely as just the list of numbers
[a1, a2, a3 ...]. (The figure is taken
from
the Wikipedia
entry on continued fractions; if you like, you can turn your stopwatch off
and go read that article for a few minutes). Any real number has a unique
list of positive integers which are its continued fraction representation,
and conversely any list of positive integers is the continued fraction
representation for a specific real number. If a real number is also a
rational number, the continued fraction representation is finite; for
irrational numbers, it's infinite, so you get an infinite sequence of
positive integers. If you stop the sequence at any point, you get an
approximation for the irrational number; the more terms in the sequence, the
better the approximation.
One interesting aspect of continued fractions is that some irrational
numbers (such as the golden ratio, 1.6180339887) have very simple repeating
continued fraction expansions (golden ratio ==> [1, 1, 1, 1, ...]), whereas
other irrational numbers, like pi, have irregular continued fraction
expansions (pi ==> [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, ...]). Some
irrational numbers like e, the base of natural logarithms (which
is 2.718281828459045...) have non-repeating but highly regular continued
fraction representations (for e, it's [2, 1, 2, 1, 1, 4, 1, 1,
6, 1, 1, 8, ...]).
You can create a continued fraction representation of a real number using the following algorithm:
The first term of the continued fraction is the integer part of the real number i.e. the part to the left of the decimal place. So for pi (3.141592653589...), it would just be 3.
Take the fractional part of the number (in this case, 0.141592653589...) and calculate the reciprocal (here, 1 / 0.141592653589... = 7.0625133059310521...). The integer part of this number is the next term of the continued fraction (here, 7).
Take the fractional part of this new number (here, 0.0625133059310521...), and compute its reciprocal (here, 15.996594406684103). The integer part of this number is the next term of the continued fraction (here, 15).
Continue this way as long as you like. If the original number is a rational number, eventually the continued fraction will end (which means that the fractional part will become zero). Otherwise, it will keep on going forever, though you can stop at any point to get an approximation to the number.
In addition to working with continued fractions, we will also be writing some procedures that deal with prime numbers. The reason for this will become clear in part 4.
In the code that follows, you can use some useful procedures that we will define here:
;; Return the integral part of a real number x. ;; Example: (int 1.5) ==> 1 (define (int x) (inexact->exact (floor x))) ;; Return the fractional part of a real number x. ;; Example: (frac 1.5) ==> 0.5 (define (frac x) (- x (int x))) ;; Does one positive integer m divide another positive integer n? ;; (In other words, is n an exact multiple of m?) ;; Examples: ;; (divides? 2 1024) ==> #t ;; (divides? 3 11) ==> #f (define (divides? m n) (= (remainder n m) 0)) ;; Return #t if an integer is a prime number, otherwise return #f. (define (prime? n) ;; defined in the textbook )
Note: The point value of each problem is given in boldface.
[0.6] Write two procedures which compute the number of times a
particular positive integer m can be divided into another positive integer n.
One of these procedures will implement a recursive process and will be
called count-divisors-rec. The other procedure will implement
an iterative process and will be called count-divisors-iter.
Examples:
(count-divisors-rec 36 3) ==> 2 (3 can divide 36 twice; i.e. 36/3 = 12, 12/3 = 4, and 4 isn't divisible by 3) (count-divisors-rec 1024 2) ==> 10 (2 can divide 1024 ten times; 1024/2 = 512, 512/2 = 256, ... ) (count-divisors-rec 3 2) ==> 0 (2 can't divide 3 at all) ;; count-divisors-iter returns the same answers, of course.
;; recursive:
(define (count-divisors-rec n m)
(if (divides? m n)
(+ 1 (count-divisors-rec (/ n m) m))
0))
;; iterative:
(define (count-divisors-iter n m)
(define (iter n m count)
(if (divides? m n)
(iter (/ n m) m (+ count 1))
count))
(iter n m 0))
[0.3] Write a procedure called next-prime which
takes an integer n and returns the smallest prime number larger
than n. Examples:
(next-prime 1) ==> 2 (next-prime 4) ==> 5 (next-prime 14) ==> 17
;; recursively:
(define (next-prime n)
(let ((next-n (+ n 1)))
(if (prime? next-n)
next-n
(next-prime next-n))))
;; Many people put the (+ n 1) in the code in multiple places,
;; which is poor style since you're computing the same value over and over.
;; iteratively:
(define (next-prime n)
(define (iter i)
(if (prime? i)
i
(iter (+ i 1))))
(iter (+ n 1)))
[0.3] Write a procedure called nth-prime which
takes a positive integer argument and returns the nth prime number, starting
from 0. Examples:
(nth-prime 0) ==> 2 (nth-prime 1) ==> 3 (nth-prime 2) ==> 5 ; etc.
(define (nth-prime n)
(define (iter i current-prime)
(if (= i n)
current-prime
(iter (+ i 1) (next-prime current-prime))))
(if (< n 0)
(error "invalid argument")
(iter 0 2)))
[0.3] Write a procedure called nth-cont-frac-term
which will take two arguments: a real number r and a positive
integer n. The procedure will use the algorithm described above
to return the nth term of the continued fraction expansion of r,
with the zeroth term being the integer component of r.
Examples:
;; Compute the continued fraction for pi. pi = 3.141592653589793 and is ;; predefined in Scheme. (nth-cont-frac-term pi 0) ==> 3 (nth-cont-frac-term pi 1) ==> 7 (nth-cont-frac-term pi 2) ==> 15 (nth-cont-frac-term pi 3) ==> 1 (nth-cont-frac-term pi 4) ==> 292 ;; etc. ;; Compute the continued fraction for 101/329. Note that rational numbers ;; like 101/329 can be used directly in Scheme. (nth-cont-frac-term 101/329 0) ==> 0 (nth-cont-frac-term 101/329 1) ==> 3 (nth-cont-frac-term 101/329 2) ==> 3 (nth-cont-frac-term 101/329 3) ==> 1 (nth-cont-frac-term 101/329 4) ==> 7 (nth-cont-frac-term 101/329 5) ==> 1 (nth-cont-frac-term 101/329 6) ==> 2 (nth-cont-frac-term 101/329 7) ==> 0 (nth-cont-frac-term 101/329 8) ==> 0 (nth-cont-frac-term 101/329 9) ==> 0 ;; All higher terms are also 0.
If n is less than zero, use the error procedure
to signal an error.
(define (nth-cont-frac-term r n)
(define (iter i f n)
(cond ((= n 0) i)
((= f 0) 0)
(else
(let ((next (/ 1 f))) ; can also write this as just (/ r)
(iter (int next) (frac next) (- n 1))))))
(if (< n 0)
(error "invalid range!")
(iter (int r) (frac r) n)))
;; The biggest problem people had was not checking for a division by zero.
;; That works OK for an infinite continued fraction (for irrational numbers)
;; but not for finite continued fractions.
Since we are not going to be using Scheme's list procedures in this exam,
we will represent continued fractions in a different way, as functions from
integers to integers. So the continued fraction representation for pi would
be represented by a function f, where:
f(0) = 3 f(1) = 7 f(2) = 15 f(3) = 1 f(4) = 292 etc.
Write a procedure real->cont-frac-f which takes a real
number and converts it into a function from non-negative integers
(i.e. zero and positive integers) to the corresponding continued
fraction coefficients up to some maximum value. Beyond that maximum value,
the function will return 0. Example:
(define pi_cf (real->cont-frac-f pi 4)) (pi_cf 0) ==> 3 (pi_cf 1) ==> 7 (pi_cf 2) ==> 15 (pi_cf 3) ==> 1 (pi_cf 4) ==> 292 (pi_cf 5) ==> 0 ;; (pi_cf n) = 0 for all n > 4. ;; This defines the continued fraction [3, 7, 15, 1, 292, 0, 0, 0, ...] ;; which is a pretty good approximation to pi.
Hint: This may sound difficult, but it's actually very easy. All
you need to do is wrap a lambda expression around
the nth-cont-frac-term function you defined in part 3, along
with some special handling for inputs that are too small or are beyond the
maximum value. Remember also that lambda expressions are
allowed to access variable names that exist outside of themselves but inside
the function where they were defined.
(define (real->cont-frac-f r nmax)
(lambda (n)
(cond ((< n 0) (error "invalid range!"))
((> n nmax) 0)
(else
(nth-cont-frac-term r n)))))
;; Note that checking for n<0 is unnecessary if nth-cont-frac-term also
;; checks it (as it should). We didn't take marks off in that case.
Write a procedure called eval-cont-frac-f which will take
a function from integers to integers which represents a continued
fraction (in other words, the kind of function returned
from real->cont-frac-f), and convert it back into a real
number. Example:
(define pi_cf (real->cont-frac-f pi 4)) (eval-cont-frac-f pi_cf) ==> 3.1415926530119025 ;; Note that 4 terms of the continued fraction give an approximation to pi ;; which is accurate to 9 decimal places.
Hint: This is a bit tricky, although all you're really doing is
evaluating the equation in the figure, with the function which represents the
continued fraction supplying
the a0, a1, a2, a3
values. One way to do it is to use a helper function which executes a
recursive process (not an iterative one). This helper function will evaluate
the continued fraction function at successive integer values (0, 1, 2, etc.)
and combine them to create the final value. The base case will be when the
continued fraction function returns 0. In that case, return a very large
number, which will become a very small number when its reciprocal is taken.
(Our solution is 7 lines long.)
;; Here's our original recursive solution:
(define (eval-cont-frac-f f)
(define (rec f n)
(let ((fn (f n)))
(if (= fn 0)
+inf.0 ; or 1.0e10 or any large number
(+ fn (/ 1.0 (rec f (+ n 1)))))))
(rec f 0))
;; Here's a more concise variant, which is also correct.
;; Here the f in rec refers to the f in the enclosing function.
;; Also note that (/ r) is just 1/r.
(define (eval-cont-frac-f f)
(define (rec n)
(let ((fn (f n)))
(if (= fn 0)
+inf.0 ; or 1.0e10 or any large number
(+ fn (/ (rec (+ n 1)))))))
(rec 0))
;; Here's a student solution which has the nice property that you
;; don't have to return a large number at any point.
(define (eval-cont-frac-f f)
(define (helper f n)
(if (= (f n) 0)
0
(/ 1 (+ (f n) (helper f (+ n 1))))))
(+ (f 0) (helper f 1)))
;; Here's another student solution we liked. Notice the use of an if expression
;; inside the addition. In this solution you also don't have to return a
;; large number.
(define (eval-cont-frac-f cont-frac-fun)
(define (eval-cf-helper cf-index)
(+ (cont-frac-fun cf-index) ;; grab the integer part of the current index
(if (= 0 (cont-frac-fun (+ 1 cf-index)))
0 ;; if next term is nonzero, invert it and add it to current int.
(/ 1 (eval-cf-helper (+ 1 cf-index))))))
(eval-cf-helper 0))
Having a list of continued fraction terms in the form of a function is kind of cool, but there is another way to encode an entire list of positive integers as a single really big number. That's to take the (infinitely long) set of prime numbers (2, 3, 5, 7, 11, etc.) and raise each prime number to the power of successive numbers in the list we are trying to encode. For instance, the list [1, 2, 3, 4, 5] would become 2^1 * 3^2 * 5^3 * 7^4 * 11^5 = 870037764750 (we're using the ^ character here to mean raising a number to a power). We'll call this "prime encoding" of a list of numbers. (Note that this is also an encoding of the list [1, 2, 3, 4, 5, 0, 0, 0, ...] because any number raised to the power of zero is just 1. Thus, we could use this method to encode lists of continued fraction terms as long as there aren't an infinite number of nonzero terms.)
What's interesting about this way to encode lists of numbers is that
there is a simple algorithm that makes it possible to retrieve the
individual elements of the list. To get the nth element in the list, you
take the nth prime number (which we already know how to compute from part
3), and compute how many times this prime number divides the
prime-encoded list (which we can figure out using
our count-divisors procedure from part 3). In the case we
just described, the first prime number is 2, and 2 divides 870037764750
only once, so the first element in the list is 1. The second prime
number is 3, and 3 divides 870037764750 twice, so the second element in
the list is 2. And so on. For the more math-minded of you, this works
because there is only one way to encode a number as a product of prime
numbers, which is called the "fundamental theorem of arithmetic".
Since we've been working with lists of numbers in the form of functions so far, we'll keep doing that.
Problem: Write a procedure called prime-decode
which will take a prime-encoded number and return a function from
integers to integers which will represent a list of numbers.
Example:
(define f (prime-decode 870037764750)) (f 0) ==> 1 ; our "lists" start at index 0 (f 1) ==> 2 (f 2) ==> 3 (f 3) ==> 4 (f 4) ==> 5 (f 5) ==> 0 ; and (f 6), (f 7) etc. are all 0
Hint: If you use the count-divisors
and nth-prime procedures defined in part 3, this problem is
trivially easy (our solution is two lines long).
(define (prime-decode n) (lambda (m) (count-divisors-iter n (nth-prime m)))) ;; The instructions were slightly incorrect in that there was no ;; count-divisors procedure as such defined in part 3. We accepted ;; any of count-divisors, count-divisors-rec, or count-divisors-iter.
Now that we can decode prime-encoded lists of numbers, we would like
to be able to encode them (create them) as well. Write a procedure
called prime-encode which takes a function from non-negative
integers to positive integers, along with a maximum value (which
represents the last location in the list that doesn't contain a zero),
and returns a prime-encoded integer. Example:
(define (f n) ; the same function we used above
(cond ((= n 0) 1) ; our list locations start with n = 0
((= n 1) 2)
((= n 2) 3)
((= n 3) 4)
((= n 4) 5) ; n.b. for this function, nmax = 4
(else 0)))
(define encoded-f (prime-encode f 4))
encoded-f ==> 870037764750 ; = 2^1 * 3^2 * 5^3 * 7^4 * 11^5
Hint: Either an iterative or a recursive process will work fine
here. Either way you'll probably want to have a helper function.
The next-prime procedure you defined in part 3 will be very
useful to you here.
;; recursive
(define (prime-encode-rec f nmax)
(define (rec n current-prime)
(if (> n nmax)
1
(* (expt current-prime (f n))
(rec (+ n 1) (next-prime current-prime)))))
(rec 0 2))
;; iterative
(define (prime-encode-iter f nmax)
(define (iter n current-prime result)
(if (> n nmax)
result
(iter (+ n 1) (next-prime current-prime)
(* result (expt current-prime (f n))))))
(iter 0 2 1))
And finally, to tie everything together, define a procedure
called encode-real that will convert a real number into a
big integer. This procedure takes two arguments, which are a real
number r to encode and the index nmax of the
last term in the continued fraction expansion of the real number to use.
It will do this by first converting the real number into a continued
fraction (represented as a function as described above and stopping after
the nmax term) and then converting that function into a
single big integer as described above.
In addition, define a procedure called decode-real. This
procedure takes one argument, which is a real number encoded as a big
integer by encode-real, and returns the original real
number. It will do this by first converting the integer into a continued
fraction function and then converting that to a real number.
Example:
(define pi-encoded (encode-real pi 4)) ; only use 4 terms of the continued fraction pi-encoded ==> 45630049645548359221889989680784193951228135357410387073563069824526456053666827 96721662108127711504564872475436156170660465309114594265594144374421919395978742 11182442885879757227603484774542941938476963568564806794800921911469197602839581 44763287363407394866277167714623420994659738685593734004752661378171142578125000 ;; Yikes, that's a big number! ;; This shows that pi-encoded really does represent a continued fraction ;; expansion of pi: (define pi-decoded-f (prime-decode pi-encoded)) (pi-decoded-f 0) ==> 3 (pi-decoded-f 1) ==> 7 (pi-decoded-f 2) ==> 15 (pi-decoded-f 3) ==> 1 (pi-decoded-f 4) ==> 292 (pi-decoded-f 5) ==> 0 ; all higher terms are also zero. ;; Now decode the encoded number to get an approximation of pi, which is ;; the same as what you would get from the first four terms of the ;; continued fraction for pi. (decode-real pi-encoded) ==> 3.1415926530119025
The moral of the story is that if your programming language supports arbitrarily large integers, you can encode real numbers of arbitrary precision using single integers. It may not be the most efficient way to encode real numbers, but it can be done.
Hint: Again, if you use
the prime-encode, prime-decode, real->cont-frac-f,
and eval-cont-frac-f procedures you defined above, both
procedures are very easy to define (our versions are two lines long
apiece).
(define (encode-real r nmax) (prime-encode (real->cont-frac-f r nmax) nmax)) (define (decode-real encoded-r) (eval-cont-frac-f (prime-decode encoded-r)))
[end midterm]