- What are the values of the following expressions?
> 10
> (+ 5 3 4)
> (- 9 1)
> (/ 6 2)
> (+ ( * 2 4) (- 4 6))
> (let ((a 1) (b 2)) (+ a b (* a b)))
> a
> (define a 3)
> a
> (define b (+ a 1))
> (+ a b (* a b))
> (= a b)
> (if (and (> b a) (< b (* a b)))
b
a)
> (cond ((= a 4) 6)
((= b 4) (+ 6 7 a))
(else 25))
- Please define functions (new.< x y), (new.> x y), (new.= x y),
(new.<= x y), (new.>= x y) oraz (new.<> x y).
No built-in functions are allowed, except for < and boolean functions.
- Please define functions (nwd a b) and (nww a b)
whose values are the greatest common divisor and the least common multiple of (natural numbers) a and b.
- Please define a function (same-values? p1 p2 x y) whose value is #t, if p1(x,y) i p2(x,y) have the same value
and #f otherwise.
Examples: > (same-values? = new.= 3 1)
#t
> (same-values? < > 2 3)
#f
> (same-values? + * 2 2)
#t
- Please define functions (odd? n) and (even? n) checking whether a natural number n is odd or even, resp.
No built-in functions are allowed, except for #t, #f, zero? and a
function "-1" calculating n-1.
-
a) Please define a function (factorial n) whose value is n! using recursion.
b) The factorial function can also be defined the following way:
(define (factorial_help n i acc)
(if (< n i)
acc
(factorial_help n (+ i 1) (* i acc))))
(define (factorial n)
(factorial_help n 1 1))
Please show how the expression (factorial 4) is evaluated,
once for the recursive version a) and again for version b).
Note: The argument acc is called accumulator and one says that this version defines
the faculty function using accumulation or iteratively.
- a) Please define functions (fibonacci n) whose value is the n-th element of the
Fibonacci sequence, one using recursion and again using accumulation.
b) For both versions please show how the expression (fibonacci 4) is evaluated.
- a) The exponentiation b^e (for natural numbers b and e) can be quickly executed using b^e = (b^(e/2))^2.
Using this property please define functions (exp b e) whose value is b^e, one recursive function and
one using accumulation.
b) For both versions please show how the expression (exp 2 6) is evaluated.
- Please define a function (root f a b) approximating a root of f
between a and b using the half-interval-method.
- Why the expression if cannot be defined the following way?
(define (new-if condition consequence alternative)
(cond (condition consequence)
(else alternative)))
- Please define a function (product term next a b) analogous to function sum.
Please show, how function product can be used to define both function
silnia and for the approximation of p using the formula
p/4 = 2 · 4 · 4 · 6 · 6 · 8 ··· / 3
· 3 · 5 · 5 · 7 · 7 ··· .
- Please define a function (accumulate combiner null-value term a next b)generalizing functions sum i product:
The arguments term, next, a, and b are the same as in the definitions of
sum i prod.
combiner is a two-argument function describing, how (term a) is tied together
with the recursive result.
null-value is the initial value used in the basic step of recursion.
Please also show, how sum i product can be defined using
accumulate.
- Even function accumulate can be generalized:
Please define a function filter-accumulate with an additional argument pred.
pred is a one-argument predicate and filter-accumulate ties (term a) to the result only if
a fulfills pred.
Using filter-accumulate please compute the sum of squares of the prime numbers
in the interval [a,b]
and the product of the natural numbers i smaller than n for which gcd(i,n) = 1.
- Suppose the following definition of function f is given.
(define f g) (g 2))
Please show how the following expressions are evaluated.
a) (f square)
b) (f (lambda (z) (+ z (* 3 z)))
c) (f f)
- Suppose the following function definitions com, square, and double are given.
(define (comb f g)
(lambda (x) (f (g x))))
(define (square n) (* n n))
(define (double n) (+ n n))
Please show how the expression ((comb square double) 5) is evaluated.
- Please define a function (iter f n), whose value is the function fn.
- Please define the following functions for lists.
a) (append l m), whose value is the concatenation of the lists l i m.
b) (last l), whose value is the last element of the list l.
c) (reverse l), whose value is the list l in reversed order.
d) (delete x l), whose value is the list l without the element x.
e) (pairing l1 l2), that builds a list of pairs out of the lists l1 and l2. Example:
> (pairing '(1 2 3) '(a b c))
'((1.a) (2.b) (3.c))
f) (split x l), that splits l into two lists l1 and l2.
l1 contains the element of l smaller than
x and l2 the elements greater than x.
- Please define a function (member-all? x l) checking whether element x appears
at any level in list x. Examples:
> (member-all? 'a '(b (c a) b))
#t
> (member-all? '(a) '(b (c (a) d) e))
#t
> (member-all? '(a) '(b c a))
#f
- a) Please define a function (square-list l), whose value is the list of squares of all elements of l.
b) Please define a function (map f l), whose value is the list of values f(e) for all elements
e of l (in the same order).
c) Please define a function (filter pred l), whose value is the list of all elements of l
(in the same order) fulfilling pedicate pred.
- Using lists to represent binary trees (as in the lecture notes) please define functions
(memberTree? element tree), (sumTree tree),
(inorder tree), and (mapTree f tree).
-
a) Please complete the definition of function diff as presented in the lecture.
b) Please modify functions make-sum and make-product so that function diff
returns normalized terms - this means for example y instead of (* y 1).
c) Please extend the definition of function diff, so that it can handle terms u^n
for natural number n - using the rule
d(u^n) / dx = n * u^(n-1) * du / dx .
- Please define rational number's artihmetic based on integers' arithmetic.
- Please define a function (eval expression values) which evaluates boolean expressions.
expression is a list whose first element gives the "type" of the boolean expression,
the remaining elements are the subexpressions -
for example '(and x (not y)) represents the expression x∧¬y.
values is a list of variables together with their corresponding boolean value.
Examples: > (define values '((x . #f) (y . #t) (z . #f)))
values
> (eval '(and y (not x)) values)
#t
> (eval '(and y (and (not x) z))) values)
#f
> (eval '(and y #t) values)
#t
- Using function fold please define the following functions for lists.
a) (prod l)
b) (length l)
c) (delete x l)
d) (reverse l)
e) (map f l)
f) (filter pred l)
g) (forall pred l).
- Please complete the arithmetics of complex numbers as presented in the lecture
a) using manifest types.
b) using message passing.
c) Suppose the following definitions are given.
(define z1 (make-rectangular -1 3))
(define z2 (make-polar 2 -2))
Please explain how the expression (angle (+c z1 z2)) is evaluated.
- In Scheme one can define functions with an arbitrary number of arguments:
(define (f x y z . l) (...))
means, that function f has at least three arguments (x,y and z).
If f is called with more than three arguments the remaining ones are collected in list l .
a) Please define a function plus, which sums up any number of numbers.
b) Please define a function par for an arbitrary number of (one-argumented) functions fi.
Function par returns a (one-argumented) function,
which for an argument x returns a list of all fi(x).
Example:
> ((par id square cube) 3)
(3 9 27)
> ((par double double) 5)
(10 10)
- Please - again - define a function (fibonacci n) whose value is the n-th element of the
Fibonacci sequence - this time by computing the n-th power of the matrix