Preparation for 600 Final Jozo Dujmović
© Jozo Dujmović Preparation for final 1
• Closed notes.
• Use pencil and eraser.
Rules
• Make your answers as readable as possible.
• Adjust the size of your text so that it fits in the available space. Use left page if you need additional space.
• The use of machines with memory is not permitted.
© Jozo Dujmović Preparation for final 2
The structure of exam
• Theoretical questions: Scheme
• Short programming assignments: Scheme • Theoretical questions: Ruby
• Short programming assignments: Ruby
• General programming language questions • Number of questions: 4 – 6
© Jozo Dujmović Preparation for final 3
(a) Explain the concept of first-class objects. What are the first-class objects in Scheme?
(b) Show an example of Scheme procedure that is a first-class object and returns a procedure.
ANSWER (a)
An object (data object, or a function) is first-class if it can be used in programs without restrictions:
May be expressed as an anonymous literal value (constant) May be stored in variables
May be stored in data structures
May be comparable to other objects for equality
May be passed as parameter to procedures/functions May be returned as result from procedures/functions May be constructed at run time
Is readable and printable
It has intrinsic identity (independent of given name) May be stored outside running processes
May be transmitted among processes
In Scheme all objects (including functions) are first-class. Elimination of restrictions
contributes to the expressive power of languages.
© Jozo Dujmović Preparation for final 4
(b) Show an example of Scheme procedure that is a first-class object and returns a procedure.
ANSWER (b)
[22] (define add2 (lambda (n) (+ n 2)))
ADD2
[23] (map add2 ‘(1 2 3 4))
(3 4 5 6)
[24] (define compose ; compose is the function of two arguments (lambda (f g) ; both arguments are functions
(lambda (x) ; function f(g(x))
(f ( g x))))) ; (compose f g) returns the function f(g(x))
COMPOSE
[25] (define add4 (compose add2 add2)) ; add4(x)=add2(add2(x))=x+2+2 ADD4
[26] (add4 5)
9
define f (cadr (list car (lambda(n)(* n n)))))
(map f ‘(1 2 3 4))
(1 4 9 16)
© Jozo Dujmović Preparation for final
; f = n * n
5
© Jozo Dujmović Preparation for final 6
Write a Scheme function (count e lst) that counts the number of times the element e occurs in the list lst. For example:
> (count 1 ‘(1 2 1 2 3 2 1))
3
ANSWER: We will use the tail recursion. If the list is empty we return 0. If it is not empty, then we check the head. If the head is the desired element, we add 1 to the count of the tail. Otherwise, we return the count of the tail.
(define count
(lambda (e lst)
( cond
((null? lst) 0)
((equal? e (car lst)) (add1 (count e (cdr lst)))) (else (count e (cdr lst))))))
[75] (count 1 ‘(1 2 1 2 3 2 1)) 3
[76] (count ‘a ‘(a b b a))
2
© Jozo Dujmović Preparation for final 7
(a) Show a flow chart and explain the work of the do loop in Scheme.
(b) Write in Scheme a recursive function sr, and non-recursive (based on do-loop) function si, that take as their argument the number of components n, and compute the following sum:
1+1/22 +1/32 +…+1/n2 , n>0.
(a) Do loop with multiple initializations/updates has the following syntax:
(do((I1(U1))… (Ik(Uk)));Initializationandupdate
(( TT ) ( V1 ) … ( Vm )) ; Termination test & sequence
( B1 ) ( B2 ) … ( Bn ) ) ; Loop body
© Jozo Dujmović
Preparation for final
8
I1 Ik TTTV1V2 Vm
II
F
Unspecified order
Uk
B1
B2 U2
Sequential execution
U1
Bn
Returne
d value
Write in Scheme a recursive function sr, and non-recursive (based on do-loop) function si, that take as their argument the number of components n, and compute the following sum:
ANSWER
1+1/22 +1/32 +…+1/n2 , n>0.
S(n) = S(n-1) + 1/n2; S(0) = 0
(define (sr n)
(cond
((<= n 0) 0)
(else (+ (/ 1 (* n n)) (sr (sub1 n))))))
(define (si n)
(do ((i 1 (add1 i)) (sum 0))
((> i n) sum)
(set! sum (+ sum (/1 (* i i))))))
© Jozo Dujmović Preparation for final 9
Explain the concept of functions with arbitrary number of arguments in Scheme. Show the syntax of functions with mandatory and optional arguments. Write a program that computes the mean value of any number of arguments in the case where the minimum number of arguments is 2.
ANSWER
A function f can process an arbitrary number of arguments if it is defined in one of the following ways:
( define (f . x)
( define f (lambda x
The function call is
(f arg1 arg2 … argn)
In this case the list x is bound to (arg1 arg2 … argn) and then processed by f. If the minimum number of arguments is 2, then f is defined as follows:
( define (f x y . z)
( define f (lambda (x y . z)
x and y are mandatory arguments and z is an optional list; dot separates mandatory and optional arguments.
© Jozo Dujmović Preparation for final 10
Example:
(define (sumlist lst)
(if (null? lst) 0 (+ (car lst) (sumlist (cdr lst)))))
(define (sum . x) (sumlist x)) ; arbitrary number of arguments (define mean (lambda (x y . z)
(/ (sum x y (sumlist z)) (+ 2 (length z)))))
————————————————————-
Simplest solution:
(define (mean x y . z) (/ (+ x y (apply + z))(+ 2 (length z))))
(apply + ‘(1 2 3)) ; equivalent to (+ 1 2 3) 6
© Jozo Dujmović Preparation for final 11
(a) Write a recursive Scheme procedure line that prints n asterisks in a line as follows: > (line 5)
*****
(b) Write a recursive Scheme procedure histogram that uses the procedure line, and prints a histogram for a list of integers:
> (histogram ’(1 2 3 3 2 1))
*
** *** *** ** *
(c) Write a nonrecursive procedure hist, that uses for-each operator and works in the same way as the procedure histogram.
(d) Write a procedure vhist that is equivalent to histogram, but instead of list uses a vector of integers.
(e) Write a histogram presentation procedure (lvhist x) where x can be either a vector
of a list.
© Jozo Dujmović Preparation for final 12
(a) Show the syntax, explain the function, and show examples of use of Ruby iterators collect, select, and reject.
(b) Explain the concept of self variable. Expand the Ruby class Array with the method saw(m) that can fill any array with the repeating sequence 1,2,…,m, 1,2,…,m, 1,2,…,m,…. (assume that m>1). The method saw(m) must return the filled array. Then, show an example of the use of saw(7) to an array of 30 components.
(c) Explain the concept of default values of method arguments. Show an example of program that uses this concept.
© Jozo Dujmović Preparation for final 13
Collect: (same as map) executes the associated block for each element of the enumerable object, and collects the return values into an array
Select: creates an array by selecting components of an enumerable object
Reject: creates an array by selecting components of an enumerable object
Reject is the opposite of select
© Jozo Dujmović Preparation for final 14
© Jozo Dujmović Preparation for final 15
SELF:
self is a reserved pseudovariable used to access current object invoked by a method. Self contains a set of instance variables that are components of an object.
© Jozo Dujmović Preparation for final 16
Default values of method arguments
Ruby permits the use of default values of method arguments
Default values are used if the user does not provide the values of arguments The list of arguments can have variable length
© Jozo Dujmović Preparation for final 17
Create a Ruby class Sphere. Each sphere is characterized by the instance variable radius. For this class create the initializer and the following methods:
area – a method that returns the area of the sphere volume – a method that returns the volume of the sphere
Create the class Ball that inherits properties from the class Sphere and adds a new instance variable color. Then create the class MyBall that inherits properties from the class Ball and adds a new instance variable owner. Write the method show that displays the instance variables of the class MyBall.
Show sample applications of the class MyBall.
© Jozo Dujmović Preparation for final 18
© Jozo Dujmović Preparation for final 19
Explain and exemplify the concept of tail recursion. Compare tail-recursive and iterative solutions of the same problem.
ANSWER
Many programming problems have iterative structure, where the same operations are performed with a sequence of objects. Two basic approaches to such problems are:
• Iterative: Create a counter/pointer variable, and a loop that changes the counter/pointer variable in the range from the first to the last object. Use the counter/pointer to sequentially access each object in the sequence and perform necessary operation(s) with each of the selected objects.
• Tail-recursive: Interpret a sequence of objects as a list.
Process the head of list. Then, apply the same procedure to the
tail. Stop if the tail is empty.
© Jozo Dujmović Preparation for final 20
Example: Count the number of times the element e occurs in the list lst
Iterative approach: O(n)
count = 0;
for(int i=0; i