OOP in C++
Dr Robert Nu ̈rnberg
Driving Test 2019
Wednesday, 20 March 2pm – 4pm
Using the exam account details given on the separate instruction sheet, attempt all 4 tasks. Throughout you should work on the H:\ drive and save your work regularly. Write one C++ file per task. Make sure to fill in the answers to each question on the Answer Sheet. Also make sure that the codes you submit will produce all the answers from your answer sheet when compiled and run. Once you have finished, save the 4 files taskN.cpp, N=1. . .4, to the directory H:\Submit and contact the invigilator. Do not log off! Hand in your answer sheet and present your files. You may then click the Submit icon on your desktop, which will automatically submit your files and log you off. You are then free to leave.
1. Sums of squares [20 marks]
Write a program that, given a positive integer n, finds all the unique ways in which to write the number as the sum of three positive square numbers, if that is possible. E.g. for n = 11, the only way is 11 = 12 + 12 + 32.
2. Pseudo random numbers [30 marks] Given x0, a, c, m ∈ N, we define the sequence
xn+1 = (a xn + c) mod m ,
which will produce pseudo random numbers between 0 and m − 1.
Write a program that, given the above defined sequence x0,x1,…,xN, for N ∈ N, can compute the following quantities.
• EN = 1 N xi. N i=1
•VN=1 N (xi−EN)2. N i=1
• AN,k = #{i : xi = k,i = 1,…,N}, for k = 0,…,m−1. (Here # denotes the cardinality of a set, i.e. AN,k is the number of times the value k occured.)
Given a function f : (0, 1) → R, you should also implement 1N 1+xi
0
[Hint: You could test your program with f(x) = 1, f(x) = x and f(x) = x2, for example.]
• IN(f)=N
as an approximation to 1 f dx.
i=1
f m
OOP in C++ Dr Robert Nu ̈rnberg
3. Classical Gram–Schmidt [30 marks]
Write a program that, for vectors a,b ∈ Rm, can compute the inner product ⟨a,b⟩ = m 1
i=1 ai bi , the norm ∥a∥ = (⟨a, a⟩) 2 and the scalar multiplication α a for α ∈ R. As- suming that all the operations are always well-defined, implement the following algorithm, given n vectors a1, a2,…,an ∈ Rm.
v1 = a1
q1= 1 v1
∥v1∥
for i = 2 to n
i−1
vi =ai −⟨ai,qj⟩qj j=1
qi= 1 vi ∥vi∥
end
4. Polynomials
Write a class polynomial that implements polynomials of the form p(x) = nk=0 ak xk, whereak ∈R,k=0,…,n,andn∈N0. Forpolynomialsp,q,andα∈R,m∈N0,the following operations should be defined: p+q, αp, p·q, pm. You should also be able to return the value of the coefficient ak of xk in p, as well as p(x) for some x ∈ R.
[Hint: In order to correctly define p·q, it makes sense to first implement xk ·q(x), for k ∈ N0.]
[20 marks]
OOP in C++
Wednesday, 20 March 2pm – 4pm
Exam Account
Name
CID
Answer Sheet A
1. State the unique sum of three squares representations for the following numbers, of they
exist:
2. Letx0 =200,a=9,c=7,m=2017. Letf(x)= lnx. ( = log(x) / (1 + x)) 1+x
State the values of the following expressions.
3. Let a1 = (1,2,3,4,5,6)T, a2 = (2,3,4,5,6,7)T, a3 = (3,4,5,6,7,8)T, a4 = (4,5,6,7,8,9)T. State the following output from your program.
4. Let{xi}5i=1 ={−7,−1,0,2,7}anddefinep(x)=4 x−xi andq(x)=2(x−x5). Finally, i=1 x5 − xi
let r(x) = [p(x)]3 q(x). State the following values to five decimal digits.
n
sum of squares
2020
2015
1117
E10, E100, E1000
V10, V100, V1000
AN,k for N = 106 and k = 0,1000,2000
I10(f), I100(f), I1000(f)
q3
q4
value
coefficient a3 of x3 in p
coefficient a7 of x7 in r
r(−2)
coefficient a100 of x100 in p50
[Hint: Note that p(xi) = 0 for i = 1,…,4 and p(x5) = 1.]