Date: Thu, 28 Mar 2024 05:53:42 -0500 (CDT) Message-ID: <2077849621.930.1711623222184@wiki-n2.rice.edu> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_929_284475768.1711623222183" ------=_Part_929_284475768.1711623222183 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html
Submit your .ss
file via OWL-Space. You will need to use th=
e "Intermediate Student" language to do Problem 18.1.15. If you want to use=
explicit lambda
notation (anywhere the right hand side of a <=
code>define statement), you will need to use the "Intermediate Stude=
nt with lambda" language. You may use either intermediate level language fo=
r the entire assignment if you choose.
Required problems:
du=
-dir
. The final sentence should read "storing a file or a directory in a dir structure costs 1 storage unit." In other words, =
given a dir structure, each directory entry (a file or a directory) contain=
ed therein costs 1 unit of storage for the bookkeeping data. For a file, th=
is bookkeeping overhead is in addition to the size of its data.merge
, should be recursive (call itself directly or indirectl=
y) and it may need to deviate slightly from the structural recursion templa=
te. The top level merge
function is not recursive.= ; expression ; An expression is one of: ; - a number ; - a symbol ; - (make-mul e1 e2) where e1 and e2 are expressions ; - (make-add e1 e2) where e1 and e2 are expressions
(* (f (= + 15 x)) (g x))
Optional problem for extra credit: [50 pts]
The fibonacci function fib is defined by the following rules (in Scheme no=
tation):
(fib 0)= =3D 0 ;; formerly (fib 0) =3D 1; revised to match the prevailing mathem= atical conventions for defining fib (fib 1) =3D 1 (fib (+ n 1)) =3D (+ (fib n) (fib (- n 1)))
A naive program for computing fib (lifted directly from the definition) =
runs in exponential time, i.e. the running time for (fib n)
is=
proportional to K*b**n
for some constants K
and =
b
). It is easy to write a program that computes (fib n)<=
/code> in time proportional to
using only n
. Your challenge is to write a=
program that computes (fib n)
in log time assuming t=
hat all multiplications and additions take constant time, which is unrealis=
tic for large n
. More precisely, your program should compute <=
code>(fib n)O(log n)
addition and =
multiplication operations (less than K * log n
operat=
ions for some constant K
).
Hints: assume <=
code>n =3D 2**m. Derive a recurrence for fib 2**(m + 1)
=
in terms of fib 2**m
and fib 2**m - 1
. Initially=
write a program that works when n
is a power of 2. Then refin=
e it to a program that works for all n
.