- 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 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.
- 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
-
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.
- 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.
- 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 the 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 nwd(i,n) = 1.
- Suppose the following definition of function f.
(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)
- Please define a function (root f a b) approximating a root of f
between a and b using the half-interval-method.
- Suppose the following function definitions 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 following 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.
- 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 (mapf f l), whose value is the list of values f(e) for all elements e of l.
c) Please define a function (filter pred l), whose value is the list of all elements of l
fulfilling pedicate pred.
- Using lists to represent binary trees (see lecture notes) please define functions
(memberTree? element tree), (sumTree tree), (inorder tree) and (mapTree f tree).
-
a) Please complete the definition of function deriv as presented in the lecture.
b) Please modify functions make-sum and make-product so that function deriv
returns normalized terms - this means for example y instead of (* y 1).
c) Please complete the definition of function deriv tak, 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 a function (eval expression values) which evaluates boolean expressions.
expression is a list whose first element gives the "typ" 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 collecte 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
- Suppose the following definitions are given.
(define m 1) (define n 1)
(define (p m) (define (q n)
(pp 5)) (define (qq x)
(define (pp x) (+ x n))
(+ x m)) (qq 5))
What are the values of the expressions (p 11) and (q 11)?
Justify Your answers using the environment model.
- Suppose the following definitions are given.
(define a 2)
(define (p a)
(define (pp b)
(set! a (+ b 1))
(* a b))
(pp 2))
What is the value of the expression (p 5)? What is the value of a after evaluating (p 5)?
Justify Your answers using the environment model.
- a) Please define a function (make-konto balance) generating an account
with balance dollars.
The following operations should be possible:
withdraw money, deposit money and checking balance.
b) Suppose now the following definition.
(define k1 (make-konto 100))
Using the environment model please show, how the following expressions are evaluated.
> ((k1 'withdraw) 40)
> (k1 'balance)
> ((k1 'deposit) 10)
> (k1 'balance)
c) Please modify function make-konto, so that an account with a password is generated -
that is operations are only carried out, if the correct password is given.
Example:
(define k2 (make-konto 100 'password))
k2
> ((k2 'passowrd 'withdraw) 40)
60
> ((k2 'wrong-password 'withdraw) 20)
incorrect password
- Please define a function (counting-version f), where f is a one-argument function.
Its value is a one-argument function, which - computes f and - counts how often f is called.
Example:
> (define sq (counting-version square))
sq
> (sq 5)
25
> (sq 7)
49
> (sq 'how-often)
2
> (sq 'reset)
0
> (sq 'how-often)
0
- a) Assume that the following expessions have been evaluated.
> (define x (mcons 'a (mcons 'b '())))
> (define z1 (mcons x x))
> (define z2 (mcons (mcons 'a (mcons 'b '()))
(mcons (mcons 'a (mcons 'b '())) '())))
> (set-mcar! (mcar z1) 'g)
> (set-mcar! (mcar z2) 'g)
What are the values of z1 and z2?
b) Please define a function (mlist l), która transforming list l
into a destructive list.
- Please define a destructive version append! of append.
What are the values of the following expressions?
> (define x '(a b))
> (define y '(c d))
> (append x y)
> (cdr x)
> (append! x y)
> (mcdr x)
- Please implement stacks analogous to queues.