程序代写代做代考 game C database go Université d’Ottawa Faculté de génie

Université d’Ottawa Faculté de génie
School of Electrical Engineering and Computer Science
University of Ottawa Faculty of Engineering
École de science informatique et de génie électrique
Length of Examination: 3 hrs
Professor: Jochen Lang
April 26, 2018, 9:30-12:30 Page 1 of 19
CSI2120 Programming Paradigms
Family Name: _________________________________________________ Given Names: _________________________________________________ Student Number: ___________
Signature ____________________________
You are allowed one hand-written double-sided letter-sized sheet of notes.
At the end of the exam, when time is up: Stop working and close your exam booklet. Remain silent.
FINAL EXAM
Question
Marks
Out of
1
6
2
5
3
3
4
5
5
4
6
5
7
5
8
5
Total
38

CSI 2120, Winter 2018 page 2 of 19 _________________________________________________________________________________________________
Question 1 Database [6 marks]
Consider the following Prolog database:
% name, game, score
score( ‘Emma’, ‘FIFA18’, 3 ).
score( ‘Benjamin’, ‘Minecraft’, 387 ).
score( ‘Liam’, ‘The Legend of Zelda’, 2200 ).
score( ‘Ethan’, ‘Super Mario Odyssey’, 15100 ).
score( ‘Ava’, ‘Minecraft’, 410 ).
score( ‘Liam’, ‘Minecraft’, 222 ).
score( ‘Ava’, ‘The Legend of Zelda’, 1900 ).
a) Use setof/3 to find a sorted list of all highscores in the game Minecraft
?- ______________________________________________________________________
______________________________________________________________________ . L = [222, 387, 410].
b) Use findall/3 to find a list of all games played by Liam
?- ______________________________________________________________________
______________________________________________________________________ . L = [‘The Legend of Zelda’, ‘Minecraft’].

CSI 2120, Winter 2018 page 3 of 19 _________________________________________________________________________________________________
c) Complete the predicate countGames to determine the number of the occurrence of a game in a list of games.
?- countGames( [‘FIFA18’, ‘Minecraft’, ‘The Legend of Zelda’,
‘Super Mario Odyssey’, ‘Minecraft’, ‘Minecraft’,
‘The Legend of Zelda’], ‘Minecraft’, N).
N = 3.
countGames( [], _, 0 ) :-______________________________________________ .
countGames( [O|T], G, C ) :- _________________________________________ _________________________________________________________________________ ______________________________________________________________________ .
countGames( [G|T], G, C ):- _________________________________________ _________________________________________________________________________ ______________________________________________________________________ .

CSI 2120, Winter 2018 page 4 of 19 _________________________________________________________________________________________________
d) Consider the following predicates?
popular( P ) :- findall( G, highscore(_,G,_),L),
setof( G, N^S^highscore(N,G,S),LL),
findMax( L, LL, P, _ ).
max( MG, MC, _, CC, MG, MC ) :- MC>CC, !.
max( _, _, G, C, G, C ) :- !.
findMax( _, [], ‘None’, 0 ) :- !.
findMax( L, [G|OG], M, C ) :- findMax( L, OG, MG, MC ),
countGames( L, G, CC ),
max( MG, MC, G, CC, M, C ).
What does the following query produce?
?- popular(P). _________________________________________________________________________
______________________________________________________________________ .

CSI 2120, Winter 2018 page 5 of 19 _________________________________________________________________________________________________
Question 2 Scheme List Processing [5 marks]
Consider the following example output:
(contain ‘(a 7 9 10) ‘(5 a c 7 10))  ((a 7 10) (9))
Complete the auxiliary procedure containAux for contain that accept two lists as inputs and produces a list of two lists as outputs. The first input list are elements to be tested if they are contained in the second input list. The first list in the output list is a list of elements that are contained in the second input list while the second list in the output list are the elements that are not contained in the second input list.
(define (contain S L)
(cond
((or (not (list? S)) (not (list? L))) error)
((or (null? S) (null? L) ) (list ‘() ‘()))
(#t (containAux S L ‘() ‘()))))
(define (containAux S L FS FO)
(cond
((null? S) ________________________________________________ ) ((member (car S) L) ________________________________________________ ___________________________________________________________________ __________________________________________________________________)
(#t _________________________________________________________ ____________________________________________________________________ _________________________________________________________________)))

CSI 2120, Winter 2018 page 6 of 19 _________________________________________________________________________________________________
Question 3 Scheme Calculation [3 marks]
The area of a rectangle with the lower-left corner A and the upper right corner B is given by
=(−)(− )
The corners A, B can be represented in Scheme as pairs, e.g., (-2 . 2) (1 . 5) And then the following procedure call will calculate the area.
(area (cons -2 2) (cons 1 5)) 9
Complete the procedure area to calculate the area:
(define (area A B) _________________________________________________________________________ _________________________________________________________________________ _________________________________________________________________________ _________________________________________________________________________ _________________________________________________________________________ _________________________________________________________________________ _________________________________________________________________________ _________________________________________________________________________)

CSI 2120, Winter 2018 page 7 of 19 _________________________________________________________________________________________________
Question 4 Scheme let, let*, letrec, named let [5 points]
Consider the following definition for the function fct
(define (fct x y)
(let ((diff (- x y)))
(let ((diff-squared (* diff diff)))
(let ((diff-cubed (* diff-squared diff)))
diff-cubed))))
a) What will be the result of the following call?
(fct 5 7)
_________________________________________________________________________
b) Rewrite this function by replacing the let calls by a call to the let* function
(define (fct x y) ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ____________________________________________________________________ ___________________________________________________________________ )

CSI 2120, Winter 2018 page 8 of 19 _________________________________________________________________________________________________
Consider the following definition for the function abc (define (abc x y)
(let loop ((i x) (s 0))
(if (< i y) (loop (+ i 1) (+ s i)) s))) c) What will be the result of the following call? (abc 3 7) _________________________________________________________________________ CSI 2120, Winter 2018 page 9 of 19 _________________________________________________________________________________________________ Consider the following definitions for the function len that calculates the length of an input list. (define (len L) (if (list? L) (lengthAux L) 'error )) (define (lengthAux L) (if (null? L) 0 (+ 1 (lengthAux (cdr L))))) d) Rewrite len without an auxiliary function (lengthAux) but using a letrec instead (note that you will have to define the binding lenlet): (define (len L) (if (list? L) (letrec (_______________________________________________________ ______________________________________________________________ ______________________________________________________________ ______________________________________________________________ ______________________________________________________________ ______________________________________________________________) (lenlet L)) 'error)) CSI 2120, Winter 2018 page 10 of 19 _________________________________________________________________________________________________ Question 5 Go Routines [4 marks] Consider the following go main routine which applies the functions fourier in go routines and collects their calculation. package main import "fmt" import "runtime" import "math" import "math/rand" type Series struct { a, b float64 } func main() { runtime.GOMAXPROCS(3) } data := make(chan float64) defer close(data) var c [32]Series TP := 4 for t := 0; t < TP; t++ { for k := 0; k < 32; k++ { c[k].a = rand.Float64()/32.0 c[k].b = rand.Float64()/32.0 } go fourier(c, t, TP, data) } // Below the results from all of the go routines need to be // received and printed to the console. The program is to exit // when all data is received. ______________________________________________________________ ______________________________________________________________ ______________________________________________________________ ______________________________________________________________ ______________________________________________________________ CSI 2120, Winter 2018 page 11 of 19 _________________________________________________________________________________________________ The function fourier currently accepts a fixed size array c of size 32. func fourier(c [32]Series, t, TP int, out chan float64) { res := c[0].a for n := 1; n < 32; n++ { res += c[n].a*math.Sin(2.0*math.Pi*float64(t)/float64(TP)) + c[n].b*math.Cos(2.0*math.Pi*float64(t)/float64(TP)) } out <- res return Change the function to work correctly with an arbitrary-sized slice. func fourier(c ________________________________________________________, t, TP int, out chan float64) { } } res := c[0].a for ______________________________________________________________{ res += c[n].a*math.Sin(2.0*math.Pi*float64(t)/float64(TP)) + c[n].b*math.Cos(2.0*math.Pi*float64(t)/float64(TP)) } out <- res return CSI 2120, Winter 2018 page 12 of 19 _________________________________________________________________________________________________ Question 6 N-ary Tree Prolog [5 marks] Consider the following n-ary tree definition: t(2,-3,[t(5,1,[t(7,2,[])]), t(-3,4,[]), t(2,4,[t(-1,1,[]), t(-2,3,[])])] ) An in-order traversal is defined as follows: traverse(t(X,Y,[])) :- write(X), tab(1), write(Y), nl. traverse(t(X,Y,[H|T])) :- traverse(H), write(X), tab(1), write(Y), nl, traverseTail(T). traverseTail([]) :- !. traverseTail([H|T]) :- traverse(H), traverseTail(T). Please see next page! CSI 2120, Winter 2018 page 13 of 19 _________________________________________________________________________________________________ What does the following traversal print? ?- traverse(t(2,-3, ). [t(5,1,[t(7,2,[])]), t(-3,4,[]), t(2,4,[t(-1,1,[]), t(-2,3,[])])] ______________________________________________________________ ______________________________________________________________ ______________________________________________________________ ______________________________________________________________ _______________________________________________________________ ______________________________________________________________ ______________________________________________________________ ______________________________________________________________ CSI 2120, Winter 2018 page 14 of 19 _________________________________________________________________________________________________ The predicate findPoint is true if a point is in the tree. findPoint(t(U,V,_),U,V) :- !. findPoint(t(_,_,[H|_]),U,V) :- findPoint(H, U, V). findPoint(t(_,_,[_|T]),U,V) :- findPointTail(T,U,V). Complete the auxiliary predicate findPointTail below: findPointTail([H|_],U,V) :- ______________________________________________________________ ______________________________________________________________ . findPointTail([_|T],U,V) :- ______________________________________________________________ ______________________________________________________________ . CSI 2120, Winter 2018 page 15 of 19 _________________________________________________________________________________________________ Question 7 N-ary Tree Scheme [5 marks] Consider the following n-ary tree definition: (define pTree (list (cons 2 -3) (list (list (cons 5 1) (list (list (cons 7 2) '()))) A tree traversal is defined below: (define (traverse T) (cond (list (cons -3 4) '()) (list (cons 2 4) (list (list (cons -1 1) '()) (list (cons -2 3) '())))))) ((null? T) '()) ((null? (cdr T)) (car T)) (#t (cons (car T) (traverseTail (cadr T)))))) (define (traverseTail T) (if (null? T) '() (append (traverse (car T)) (traverseTail (cdr T))))) What does the function traverse evaluate to: (traverse pTree)  ______________________________________________________________ ______________________________________________________________ ______________________________________________________________ ______________________________________________________________ CSI 2120, Winter 2018 page 16 of 19 _________________________________________________________________________________________________ The function findPoint? evaluates to true if a point is in the tree. (define (findPoint? T U V) (cond ((null? T) #f) ((and (equal? (caar T) U) (equal? (cdar T) V)) #t) ((null? (cdr T)) #f) (#t (findPointTail? (cadr T) U V)))) Complete the auxiliary function findPointTail? below: (define (findPointTail? TL U V) (if (null? TL) ______________________________________________________________ ______________________________________________________________ ______________________________________________________________ ______________________________________________________________ ______________________________________________________________)) CSI 2120, Winter 2018 page 17 of 19 _________________________________________________________________________________________________ Question 8 N-ary Tree Go [9 marks] Consider the following main program: package main import "fmt" type nTree struct { x, y int children []nTree } func main() { tree := nTree{2, -3, []nTree{{5, 1, []nTree{{7, 2, nil}}}, {-3, 4, nil}, {2, 4, []nTree{{-1, 1, nil}, {-2, 3, nil}}}}} tree.traverse() u, v := -1, 1 if tree.findPoint(u, v) { } } fmt.Printf("Found: %d %d \n", u, v) CSI 2120, Winter 2018 page 18 of 19 _________________________________________________________________________________________________ Complete the method traverse below such that it prints the points in-order to console. func (t *nTree) traverse() { if t.children == nil || len(t.children) == 0 { fmt.Printf("%d %d \n", t.x, t.y) } else { for _________________________________________________ { ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ } } return } CSI 2120, Winter 2018 page 19 of 19 _________________________________________________________________________________________________ Complete the method findPoint below is to return true if a point is in the tree and false otherwise: func (t *nTree) findPoint(u, v int) bool { if t.x == u && t.y == v { } return true } if t.children == nil { return false } ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ___________________________________________________________