CARDIFF UNIVERSITY EXAMINATION PAPER
Academic Year: Examination Period: Examination Paper Number: Examination Paper Title: Duration:
2018/2019
Spring
CMT304
Programming Paradigms 2 hours
Do not turn this page over until instructed to do so by the Senior Invigilator.
Structure of Examination Paper:
There are 4 pages.
There are 3 questions in total. There are no appendices.
The maximum mark for the examination paper is 60 and the mark obtainable for a question or part of a question is shown in brackets alongside the question.
Students to be provided with:
The following items of stationery are to be provided: ONE answer book.
Instructions to Students: Answer all three questions.
Students are permitted to introduce to this examination any textbook, any printed or hand- written notes, and other similar materials. These may be annotated, highlighted and book- marked as desired.
The use of translation dictionaries between English or Welsh and a foreign language is per- mitted in this examination.
The use of electronic devices is not permitted.
1 PLEASE TURN OVER
CMT304
Q1. (a) (b)
1 2 3 4 5 6 7 8
Describe the characteristics of a problem for which Answer Set Programming is the best paradigm to use for addressing it. [4]
Consider the following Answer Set Program:
c(1..n).
r(1..n).
{q(I,J) :- r(I), c(J)}.
:- not n {q(I,J)} n. :-q(I,J),q(II,JJ),(I,J)!=(II,JJ),I-J==II-JJ. :- q(I, J), q(I, JJ), J != JJ. :-q(I,J),q(II,JJ),(I,J)!=(II,JJ),I+J==II+JJ. :- q(I, J), q(II, J), I != II.
Explain each line. [8]
If this is used in a large program (i.e. with a large n), it can be inefficient. Explain why. [4]
Describe in plain text and in code a change to this program to increase its effi- ciency. [4]
Explain the difference between the Functor, Applicative and Monad type- class in Haskell. Provide an instance definition for some data structure for each
Q2. (a) (b)
(c)
typeclass as example.
Consider the following quantum circuit:
[9]
•
H
H
H
Show that this circuit can be simplified to a single (standard) gate and explain the operation of this gate. [7]
Is quantum computing part of the functional programming paradigm? Provide in total two arguments, where either argument can be either for or against the
proposition.
[4]
2
H
Q3. (a) For each of the following regular expressions (Perl syntax), describe the language matched by the regular expression in words and give an example for a string matched by the expression:
(i) :-[()]
(ii) [$%@]\w[\w\d]+
(iii) [A-Z]\w+.
(b) For each of the following problems, state whether it is best solved by script pro- gramming, genetic algorithms, or machine programming. Provide a reason for each answer.
(i) Allocate 30000 students to 2000 personal tutors, taking into account staff availability, staff language requirements, and student preferences.
(ii) Compute a cryptographic hash on a very low-powered embedded device.
(iii) Compute statistical measures for file access times on a Unix server.
(iv) Find the optimal strategy for malware to hide itself from detection.
[4]
(c) Assume you have a processor with 5 registers, referred to as R1, R2, R3, R4, and R5, and the following instruction set:
ADD Rx, Ry: Add the contents of the registers Rx and Ry and store the result in Rx.
SUB Rx, Ry:SubtractthecontentofRyfromRxandstoretheresultinRx. DEC Rx:DecreasethevalueinregisterRxby1.
INC Rx:IncreasethevalueinregisterRxby1.
LOAD Rx, Z:DirectloadintoregisterRxusingaddressZ.
LOAD Rx, @Ry:RegisterindirectloadintoRxusingregisterRy
LOAD Rx, #Z:ImmediateloadofZintoregisterRx.
JMP @LABEL:UnconditionaljumptotheaddressofLABEL.
JZ @LABEL:JumptotheaddressofLABELifthelastoperationhasresultedin a value of zero.
QUESTION CONTINUES ON NEXT PAGE
3 PLEASE TURN OVER
CMT304
[6]
CMT304
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
You are given the following program:
LOAD R1, #0 LOAD R2, 1 LOAD R5, #1 LOAD R3, 2 JZ@E
@L:
LOAD R4, @R2
LOAD R5, R5
JZ @D1
JMP @D2
@D1:
SUB R1, R4
INC R5
JMP @D3
@D2:
ADD R1, R4
DEC R5
@D3:
INC R2
DEC R3
JZ @E
JMP @L
@E:
Assume the memory contains the following values (starting from address 1):
361234567
(i) Identify two high-level control-flow constructs in this program. Indicate the type and start and end line for each.
(ii) Which function does the program compute in R1? Describe the general function of the program (you may give a mathematical formula).
(iii) Give the value in R1 after the program terminates for the given memory contents.
[5]
(iv) Replace all occurrences of the character ‘a’ in the string named ‘s’ with the character ‘b’.
(v) Assign the string “a” to the key ‘b’ in a hash named ‘test’.
[5]
(d) Provide minimal valid example Perl code for the following tasks:
(i) Assign the numerical value 3 to a scalar variable named ‘x’.
(ii) Assign the number of elements in the array ‘a’ to the scalar variable ‘x’.
(iii) Split a string named ‘s’ into individual characters.
4X END OF EXAMINATION