CS计算机代考程序代写 scheme algorithm data structure Preparation for

Preparation for
the CSc 600 Final Exam [online]
Jozo Dujmović
© Jozo Dujmović Preparation for final 1

Rules and notes
• Open books/notes/computers
• Individual work only
• All your answers must be verbally explained to the extent that proves that the solutions are your intellectual property
• Solutions without convincing explanation are not acceptable
• The search and use of Internet resources during the exam is not permitted.
© Jozo Dujmović Preparation for final 2

Important:
• Exam time is limited to 2 hours from the moment you start to work. Control what is your remaining exam time.
• Exam is available in the interval that is 2 hours and 10 min but the exam time is limited to 2 hours of effective work.
• Students who finish work earlier are advised to use the available time to recheck, correct, expand, and comment their solutions
© Jozo Dujmović Preparation for final 3

Note:
• Questions and problems presented in the following slides are taken from standard in-class exams and some of them reflect closed-notes conditions
• Online exams must reflect the specific conditions of open-notes environment and must be slightly different, while covering the same topics as the closed-notes exams
• The primary difference is that in online exams there are no purely theoretical questions. We left such questions in this material because they have significant educational value. Problem solving
questions are the same in online and F2F version.
© Jozo Dujmović Preparation for final 4

Question #1: HONOR PLEDGE
The prerequisite for passing this exam is that in the answer area for this question you provide the following honor pledge:
I, , declare that the answers to all questions in this exam are the result of my own work, obtained without help of other people, and without access to the Internet. I understand that all questions are copyrighted and confidential, and I pledge that I will not copy and distribute the questions.
© Jozo Dujmović Preparation for final 5

What are other questions? (1)
• Each programming paradigm has fundamental properties (key facts, points and ideas) that are both the purpose and the takeaway of the study. These properties are always included in all exams
• Functional programming: first class objects, list as a fundamental programming mechanism, all language constructs must return a value, dynamic typing, the use of symbol table, anonymous functions, collections of heterogeneous objects, functions with mandatory and optional arguments, composing functions, scope, recursive thinking and problem solving
© Jozo Dujmović Preparation for final 6

What are other questions? (2)
• Multiparadigm and OO programming:
– Ruby support for procedural programming: dynamic typing, data types and formats, procedural operations, assignments, control structures, arrays and array operations, functions: number and passing of arguments, I/O operations, libraries
– Ruby support for functional programming: language constructs return a value, collections of heterogeneous objects, functions with mandatory and optional arguments
– Ruby support for OO programming: inheritance from Object, the meaning of 100% object-oriented, creating and expanding classes, using and expanding system classes, local, global, instance and class variables. constructors/ initializers, getters and setters, methods, anonymous
objects, inheritance, method libraries
© Jozo Dujmović Preparation for final 7

The structure of exam
• [Theoretical questions: Scheme] F2F
• Short programming assignments: Scheme
• [Theoretical questions: Ruby] F2F
• Short programming assignments: Ruby
• Typical number of questions: 4
• Time = two hours (4 * 30min)
• [General programming language questions: sometimes used if there is more time]
© Jozo Dujmović Preparation for final 8

Scheme
© Jozo Dujmović Preparation for final 9

Sample Scheme theoretical questions
(F2F)
© Jozo Dujmović Preparation for final 10

(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 Dujmović Preparation for final 11

(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 Dujmović Preparation for final
; f = n * n
12

(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 )) ) ; Initialization and update
(( TT ) ( V1 ) … ( Vm )) ( B1 ) ( B2 ) … ( Bn ) )
II
; Termination test & sequence
I1
Ik
TT
;Loopbody
Returne d value
T
F
V1
V2
Vm
Unspecified order
Uk
B1
B2
Sequential execution
U2
U1
Bn
© Jozo Dujmović
Preparation for final
14

(b) Write in Scheme a recursive function sr, and non-recursive (iterative, based on do- loop) function si, that take as their argument the number of components n, and compute the following sum:
ANSWER
© Jozo Dujmović
Preparation for final 15
1 + 1/22 + 1/32 + … + 1/n2 ,
n>0.
S(n) = S(n-1) + 1/n2;
(define (sr n) (cond
S(0) = 0
((<= 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))))))

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 Dujmović Preparation for final 16

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 Dujmović Preparation for final 17

Sample Scheme programming
assignments
© Jozo Dujmović Preparation for final 18

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 Dujmović Preparation for final 19

(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 Dujmović Preparation for final 20

Note: the map function is not convenient for this problem because it returns the list:
(define (line1 n)
(cond
((<= n 0) (newline) (display "")) (else (display "*")(line1 (- n 1))))) (define (histogram lst)(map line1 lst)) > (histogram ‘(1 2 3 4 3 2 1)) *
**
***
****
***
**
*
‘(# # # # # # #) >
© Jozo Dujmović Preparation for final 22

ANSWER (b):
© Jozo Dujmović Preparation for final 24
There are four cases:
(define sumall
(lambda (lst)

First element is an empty list  2.   
‘( ( ) [CDR] )
‘( ( pair ) [CDR]
‘( number [CDR]
Listisempty  1. ‘( )

List is not empty First element is a pair (i.e. a list)  3.  
) )
  First element is a number   4.  
(cond
((null? lst) 0)
((null? (car lst)) (sumall (cdr lst)))
((pair? (car lst)) (+ (sumall (car lst)) (sumall (cdr lst)))) (else (+ (car lst) (sumall (cdr lst)))) )))

[1] (load “sumall.s”)
# =
(LAMBDA (LST)
(COND ((NULL? LST) 0)
((NULL? (CAR LST)) (SUMALL (CDR LST))) ((PAIR? (CAR LST))
(+ (SUMALL (CAR LST)) (SUMALL (CDR LST)))) (ELSE (+ (CAR LST) (SUMALL (CDR LST))))))
OK
[2] (sumall ‘(1 2 3))
6
[3] (sumall ‘((1 2) 3))
6
[4] (sumall ‘(1 (2 3) (1 3)))
10
[5] (sumall ‘((1) (2) (3)))
6
[6] (sumall ‘())
0
[7] (sumall ‘(((1 2) (3 4) 5) 6)) 21
[8]
© Jozo Dujmović Preparation for final 25

Ruby
© Jozo Dujmović Preparation for final 26

Sample Ruby theoretical questions
(F2F)
© Jozo Dujmović Preparation for final 27

(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 Dujmović Preparation for final 28

(a)
Collect: (same as map) executes the associated block for each element of the enumerable object, and collects the return values into an array
= .collect {|| function()} contains functions of components
Select: creates an array by selecting components of an enumerable object
= .select {|| }
contains those components where condition returns a value other than false or nil
Reject: creates an array by selecting components of an enumerable object
= .reject {|| }
contains those components where condition returns either false or nil (rejects components that satisfy the condition)
Reject is the opposite of select
© Jozo Dujmović Preparation for final 29

(b) 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 Dujmović Preparation for final 31

(c) 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 Dujmović Preparation for final 32

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 Dujmović Preparation for final 34

Make a class Set and the following methods:
show that displays sets as {1,2,3}
found that returns true if x is a member of the set)
hasMember that prints the message “3 is a member of {1,2,3} “ or “4 is not a member of {1,2,3}”
and
isSet? (recognizer that all set elements are different)
© Jozo Dujmović
Ruby 36

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 Dujmović Preparation for final 39

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

Related Posts