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
CSI2120 Programming Paradigms
MIDTERM EXAM
Length of Examination: 75 minutes March 3, 2020, 16:00
Professor: Jochen Lang
Family Name: _________________________________________________ Other Names: _________________________________________________ Student Number: ___________
Signature ____________________________
You are allowed one single-sided, letter-sized, hand-written sheet of notes.
At the end of the exam, when time is up: Stop working and close your exam booklet. Remain silent.
Page 1 of 10
Question
Marks
Out of
1
8
2
5
3
4
4
5
5
4
Total
26
2019/03/05 Midterm Exam, CSI 2120 page 2 of 10 ______________________________________________________________________________________________________________
Question 1 [8 marks]
Consider the following program in Go with the definitions of the interface Accumulator and the structure Product which implements the interface.
package main
import (
“fmt”
“math” )
type Accumulator interface {
SetInput([]float64)
GetResult() float64
}
// Struct to store product of input values
type Product struct {
input
factor float64
Result float64
}
func (p *Product) GetResult() float64 {
p.Result = p.factor
for _, x := range p.input.inputSlice {
p.Result = p.Result * x
}
return p.Result
}
func main() {
accu := []Accumulator{&Product{input{[]float64{1.0, 2.0, 4.0}},
2.0, 0.0}}
for i, ac := range accu {
fmt.Printf(“%d. Accumulater %f\n”, i+1, ac.GetResult()) }
return }
2019/03/05 Midterm Exam, CSI 2120 page 3 of 10 ______________________________________________________________________________________________________________
a) Define the type input to work with the structure Product and the main program on the previous page. [2 marks]
type ____ input struct ________________________ { ___inputSlice []float64________
____________________________________ }
b) Complete the SetInput method to ensure the structure Product implements the interface Accumulator. Note: Product embeds the structure input. [3 marks]
func (_______in *input______________) SetInput(inSlice []float64) { __in.inputSlice______ =
make([]float64, ____len(inSlice)___________________)) copy(inSlice, ______in.inputSlice________________________)
return }
2019/03/05 Midterm Exam, CSI 2120 page 4 of 10 ______________________________________________________________________________________________________________
c) The following structure Sum implements also the Accumulator interface. Initialize a structure Sum in accu[1] for the input values 3.0, 7.0 with the weighter function GeometricSeries(n int) float64 given below. [3 marks]
// Struct to store weighted sum of input values
type Sum struct {
input
weighter func(int) float64
Result float64
}
func (s *Sum) GetResult() float64 {
s.Result = 0
for n, x := range s.input.inputSlice {
s.Result = s.Result + s.weighter(n+1)*x
}
return s.Result
}
func GeometricSeries(n int) float64 {
ratio := -7.0 / 8.0
res := (1.0 – math.Pow(ratio, float64(n))) / (1.0 – ratio)
return res
}
func main() {
accu :=
[]Accumulator{&Product{input{[]float64{1.0, 2.0, 4.0}},
2.0, 0.0},
___&Sum__{_input{[]float64{3.0, 7.0}__},
____GeometricSeries_____________________________, 0.0 }}
2019/03/05 Midterm Exam, CSI 2120 page 5 of 10 ______________________________________________________________________________________________________________
Question 2 [5 marks]
Consider the following concurrent Go program that sums random integers send over separate channels.
package main
import (
“fmt”
“math/rand”
“time” )
// Initialize random Number generator by time
var rGen *rand.Rand
func worker(maxMS int) (ch chan int) {
ch = make(chan int)
go func() {
defer close(ch)
n := rGen.Intn(maxMS)
time.Sleep(100 * time.Millisecond)
ch <- n
}()
return }
const NChannels = 5
func main() {
rGen = rand.New(rand.NewSource(time.Now().UnixNano())) chs := make([]chan int, NChannels)
for i := 0; i < NChannels; i++ {
chs[i] = worker(1000)
}
sum := accumulate(chs)
fmt.Println("Sum: ", sum)
return
}
2019/03/05 Midterm Exam, CSI 2120 page 6 of 10 ______________________________________________________________________________________________________________
Complete the function accumulate that collects the integers from the channels in the slice chs and adds them up in sum via a channel collector.
func accumulate(chs []chan int) (sum int) { sum = 0
collect := make(chan int)
defer close(collect)
for i, ch := range chs {
// Each go function reads a value from one channel and // re-sends the value on the collect channel
go func(___n int, c chan int_________________________________) {
val := __<-c_________________________________________ fmt.Printf("Receieved on %d: %d\n", n, val)
__collect <- val_____________________________________ }(i,ch)
}
rec := 0 for {
val := <-collect
sum = sum + val
rec++
if ____rec == len(chs)_______________________{
break // exit from loop when all channels have been read
} }
return }
2019/03/05 Midterm Exam, CSI 2120 page 7 of 10 ______________________________________________________________________________________________________________
Question 3 [4 marks]
Given the following Prolog program
canis(wolf).
canis(coyote).
lutra(otter).
taxidea(badger).
panthera(lion).
panthera(tiger).
panthera(jaguar).
carnivora(X) :- felidae(X).
carnivora(X) :- mustelidae(X), !.
carnivora(X) :- canidae(X).
canidae(X) :- canis(X).
mustelidae(X) :- taxidea(X).
mustelidae(X) :- lutra(X).
felidae(X) :- panthera(X).
a) Give all solutions in order that they are found by Prolog by the following query (and using ; after each answer)?
?- carnivora(X).
X = lion ;
X = tiger ;
X = jaguar ;
X = badger.
2019/03/05 Midterm Exam, CSI 2120 page 8 of 10 ______________________________________________________________________________________________________________
b) Consider the following program. (Note the two cuts !)
canis(wolf).
canis(coyote).
lutra(otter).
taxidea(badger).
panthera(lion).
panthera(tiger).
panthera(jaguar).
carnivora(X) :- felidae(X).
carnivora(X) :- mustelidae(X).
carnivora(X) :- canidae(X), !.
canidae(X) :- canis(X).
mustelidae(X) :- !, taxidea(X).
mustelidae(X) :- lutra(X).
felidae(X) :- panthera(X).
Give all solutions in order that they are found by Prolog by the following query (and using ; after each answer)?
?- carnivora(X).
X = lion ;
X = tiger ;
X = jaguar ;
X = badger ;
X = wolf.
2019/03/05 Midterm Exam, CSI 2120 page 9 of 10 ______________________________________________________________________________________________________________
Question 4 [5 marks]
Complete the following Prolog program calculating the value Y of a geometric series of N terms with a ratio R:
The equation of the series is 𝑌 = 1 + ∑ 𝑅 power(_,0,1) :- !.
power(X,N,Y) :- N>0,
N1 is N-1,
power(X,N1,Y1),
Y is Y1 * X.
geometricSeries(_____-________,______0________,_______1_______) :- !. geometricSeries(R,N,______Y_________) :- N > 0,
power(________R_______,________N_______,_______NR________) ,
N1 is N-1, geometricSeries(R,______N1_________,_______Y1________),
Y is ___NR + Y1_________________. ?- geometricSeries(-1/2,0,Y).
Y = 1.
?- geometricSeries(-1/2,1,Y).
Y = 0.5.
?- ?- geometricSeries(-1/2,3,Y).
Y = 0.625.
For example:
2019/03/05 Midterm Exam, CSI 2120 page 10 of 10 ______________________________________________________________________________________________________________
Question 5 [4 marks]
Complete the following Prolog program calculates the individual terms of a geometric series and returns the in a list of length N. It uses the a ratio R:
The equation of the series is 𝑌 = 1 + ∑ 𝑅 power(_,0,1) :- !.
power(X,N,Y) :- N>0,
N1 is N-1,
power(X,N1,Y1),
Y is Y1 * X.
geometricTerms(_______-_______,______0________,______[1]______) :- !. geometricTerms(R,N, ____[H|T]___________) :- N > 0,
power(_____R__________,_______N________,_______H________), N1 is N-1,
geometricTerms(R, ______N1_________,________T_______).
For example:
?- geometricTerms(-1/2,0,L).
L = [1].
?- geometricTerms(-1/2,1,L).
L = [-0.5, 1].
?- geometricTerms(-1/2,3,L).
L = [-0.125, 0.25, -0.5, 1].