Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CMT304
Programming Paradigms
If you have been granted an extension for extenuating circumstances, then the sub-
mission deadline and return date will be 1 week later than that stated above (same
time).
If you have been granted a deferral for Extenuating Circumstances, then you will be
assessed during the next period the module is run (assuming all other constraints
are met).
This assignment is worth 100% of the total marks available for this module.
If coursework is submitted late (and where there are no extenuating circumstances):
1. If the assessment is submitted no later than 24 hours after the deadline, the mark for
the assessment will be capped at the minimum pass mark;
2. If the assessment is submitted more than 24 hours after the deadline, a mark of 0 will
be given for the assessment.
Extensions to the coursework submission date can only be requested using the Extenuating
Circumstances procedure. Only students with approved extenuating circumstances may
use the extenuating circumstances submission deadline. Any coursework submitted after
the initial submission deadline without approved extenuating circumstances will be treated
as late.
By submitting this assignment you are accepting the terms of the following declaration:
I hereby declare that my submission (or my contribution to it in the case of group
submissions) is all my own work, that it has not previously been submitted for as-
sessment and that I have not knowingly allowed it to be copied by another student.
I understand that deceiving or attempting to deceive examiners by passing off the
work of another writer, as one’s own is plagiarism. I also understand that plagiarising
another’s work or knowingly allowing another student to plagiarise from my work is
against the University regulations and that doing so will result in loss of marks and
possible disciplinary proceedings1.
1
Assignment
Task 1
Consider the following situation:
The public works division in a region has the responsibility to subcontract
work to private companies. There are several types of tasks. Each task is carried
out by a team, but each team is capable of carrying out all different types of tasks.
The region is divided into districts, and the amount of tasks to be done in each
district is known. In particular, the following information is available:
• The region is divided into n districts.
• There are m private companies such that 1 . . . k are experienced and
k + 1 . . .m are non-experienced.
• Each company i has ti teams available, for all 1 ≤ i ≤ m.
• Each district j requires aj many teams, for all 1 ≤ j ≤ n.
• The yearly cost of allocating a team from a company i to a district j is (the
integer) ci,j , for all 1 ≤ i ≤ m, 1 ≤ j ≤ n.
The goal is to write a logic program for helping the public works division with this process.
Using the information above, the program should determine the number of teams from each
company to allocate to each district such that the following constraints are satisfied.
• At least one experienced company must be allocated to each district (as precaution in
case some difficult task arises in that district).
• Enough teams must be allocated to meet the demand in each district.
• No company can be asked to provide more teams than it still has available.
• The cost must be minimised.
Task 1.1:
1. Write a logic program in ASP (problem encoding.lp) which finds all solutions to the
problem, given n, m, k, ti, aj , ci,j for all 1 ≤ i ≤ m, 1 ≤ j ≤ n. Document your code
so the following is clear.
(a) How it should be used.
(b) What the approach to solving the problem is. In particular, you need to explain
what each rule achieves and how the rule achieves it.
Include your name and student id in the comments.
2. Write three problem instances (problem instancei.lp, for all i ∈ {1, 2, 3}) to test your
program. Document your code so it is clear what the instance is modeling.
Task 1.2: Write a short report on logic programming related to the problem:
1. Provide, in up to 300 words, an analysis of the design and functioning of your program
in terms of the Guess-and-Test modeling methodology.
The word limits are an upper limit, not a target length. Text longer than the word limit for
each point will be ignored. Clearly mark each argument in your answer and indicate if it is
2
for and against. Only provide two arguments for and against; additional arguments will be
ignored.
Task 2
Quadratic unconstrained binary optimization (QUBO) is an optimisation problem commonly
arising in many applications such as scheduling, computer vision, computer-aided design,
financial analysis, molecular conformation. QUBO is an NP-hard problem, but small prob-
lems are feasible to solve on standard computers. For this task a simple brute force ap-
proach is sufficient, and can achieve full marks if implemented efficiently and clearly, and is
concisely documented.
QUBO is the problem of maximising a quadratic polynomial
E(x1, x2, . . . , xN ) =
N∑
l=1
N∑
k=1
Hl,kxlxk = x
THx
where xl ∈ {0, 1} for l = 1, . . . , N and Hl,k ∈ R for l, k = 1, . . . , N , and N is a positive
integer. Note that the xl values can only be either 0 or 1, so this is a search over a discrete
space.
Task 2.1: Write a Haskell program that can solve this problem by reporting a list of x1, . . . , xN
values that maximises the above functional E for small N . You may try to solve the problem
exactly or approximately (find a vector x for which E is close to the maximum). In the com-
ments, make sure you clearly document your approach, how to call your program with the
input matrix H of size N , and how the output vector x is reported.
Task 2.2: Describe one feature of the functional programming paradigm. Discuss whether
this feature makes it simpler or harder to solve the problem and compare this to another
paradigm of your choice that does not have this feature. Your answer should not be longer
than 400 words (this is not a target, but an upper limit).
Task 3
The attached measurements.csv is a csv file where the first column contains the time t and
the second column a voltage measurement x in the circuit (1, 000 datapoints from time 0 to
2π).
Write a python program using differentiable programming techniques covered in the module
to approximate the measurement data in measurements.csv with a parameterised function
fp : R 7→ R, t → x. You may use pytorch, tensorflow or jax for this (or maybe a combi-
nation of these packages; using numpy and matplotlib for supporting functionality is fine;
other packages should not be needed). You are free to choose any function type (some
analytical function, a neural network, etc). Make sure your code is suitably documented
in the comments and in particular you provide a short justification for your choice of the
representation of fp.
Your code can produce the results in any suitable format, on the terminal, via plots or in files
(do not submit these; your code will be run). Assume measurements.csv is in the directory
your python code is executed in.
3
Task 4
Consider the following quantum circuit:
consisting of several multi-target CNOT and controlled swap gates. It has two two-qubit
input quantum registers |A⟩ and |B⟩ and two two-qubit output quantum registers |A′⟩ and
|B′⟩.
Analyse the operation of the circuit. In particular, derive the full operator of the circuit and
describe the mapping from |A⟩|B⟩ to |A′⟩|B′⟩. You may use code in any language to com-
pute the circuit operator, or compute it manually. There is no need to list all intermediate
numerical results/matrices, but you need to describe and justify how you derived the opera-
tor. Based on the operator, what operation does the circuit implement?
Learning Outcomes Assessed
• Explain the conceptual foundations, evaluate and apply various programming paradigms,
such as logic, functional, scripting, filter-based programming, pattern matching and
quantum computing, to solve practical problems.
• Discuss and contrast the issues, features, design and concepts of a range of program-
ming paradigms and languages to be able to select a suitable programming paradigm
to solve a problem.
Criteria for assessment
Task 1.1: maximum 15 marks, assessed according to the following scale
Fail 0 No code has been submitted.
1− 3 Code does not run or does not produce valid output for any valid input; little
to no relevant documentation.
4− 6 Code is valid without syntax errors and creates a valid output for every
valid input (or produces a suitable error message for valid cases it cannot
process). Even if the output is not a solution, a suitable attempt to solve the
problem is visible. An attempt to document the code has been made.
Pass 7− 8 Code is valid without syntax errors and creates a valid output for every
valid input (or produces a suitable error message for valid cases it cannot
process). A suitable attempt to solve the problem has been made, that
will often find at least one solution (if there is any). The attempt has been
reasonably documented, but no consideration has been given to optimise
the program’s performance.
4
Merit 9− 10 Code is valid without syntax errors and creates a valid output for every
valid input (or produces a suitable error message for valid cases it cannot
process). A suitable attempt to solve the problem has been made, that will
find all solutions (if there are any). The attempt has been well documented.
Distinction 11− 15 Code is valid without syntax errors and creates a valid output for every valid
input. A suitable attempt to solve the problem has been made, that will find
all solutions (if there are any) for all problems, with excellent performance.
The attempt has been well documented and clearly shows an effort to op-
timise the program’s performance, e.g. by using efficient algorithms and
data representations and also some heuristics.
Task 1.2: maximum 10 marks, assessed according to the following scale
Fail 0 No document has been submitted.
1− 3 At most an incomplete attempt to analyse the design and functioning of the
program has been made.
4− 5 An attempt has been made to analyse the design and functioning of the
program.
Pass 5 A suitable attempt has been made to analyse the design and functioning of
the program.
Merit 6 The analysis of the design and functioning of the program is well-developed,
showing a clear understanding of the Guess-and-Test methodology.
Distinction 7− 10 The analysis of the design and functioning of the program shows a clear
understanding of the Guess-and-Test methodology and shows an under-
standing of related performance issues.
Task 2.1: maximum 15 marks, assessed according to the following scale:
Fail 0 No code has been submitted.
1− 3 Code does not run or does not produce valid output for any valid input; little
to no relevant documentation.
4− 6 Code is valid without syntax errors and creates a valid output for every
valid input (or produces a suitable error message for valid cases it cannot
process). Even if the output is not a solution, a suitable attempt to solve the
problem is visible. An attempt to document the code has been made.
Pass 7− 8 Code is valid without syntax errors and creates a valid output for every
valid input (or produces a suitable error message for valid cases it cannot
process). A suitable attempt to solve the problem has been made, that
will often find a solution (if there is at least one). The attempt has been
reasonably documented, but no consideration has been given to optimise
the program’s performance.
Merit 9− 10 Code is valid without syntax errors and creates a valid output for every valid
input (or produces a suitable error message for valid cases it cannot pro-
cess). A suitable attempt to solve the problem has been made, that will
always find a solution (if there is any). The attempt has been well docu-
mented, stating the idea to solve the problem and how it has been imple-
mented.
5
Distinction 11− 15 Code is valid without syntax errors and creates a valid output for every valid
input. A suitable attempt to solve the problem has been made, that will
find a solution (if there is any) for all problems, with excellent performance.
The attempt has been well documented, clearly stating the idea to solve
the problem and how it has been implemented. It clearly shows an effort to
optimise the program’s performance, e.g. by using efficient algorithms and
data representations and also some heuristics.
Task 2.2: maximum 10 marks, assessed according to the following scale:
Fail 0 No document has been submitted.
1− 3 The feature discussed is not related to functional programming paradigm.
4− 5 The feature discussed shows some understanding of the functional pro-
gramming paradigm, but is incomplete / comparison with another paradigm
is not present.
Pass 5 The feature discussed is generally valid for the functional programming
paradigm, but does not consider the specific problem or contains mistakes
in the details. An attempt to compare it to another paradigm has been made
and some understanding of this paradigm is present.
Merit 6 The feature discussed shows a clear understanding of the functional pro-
gramming paradigm, and it relates to the problem. The comparison with
another paradigm is well-developed, showing a clear understanding of both
paradigms and their differences.
Distinction 7− 10 The feature discussed shows a clear understanding of the functional pro-
gramming paradigm and the underlying theoretical concepts and how these
relate to the problem. The comparison with another paradigm is well-
developed, showing a deep understanding of practical and theoretical is-
sues involved, and clearly discusses concrete differences to the other cho-
sen paradigm.
Task 3: maximum 25 marks, assessed according to the following scale:
Fail 0 No code has been submitted.
1− 6 Code does not run.
7− 12 Code is valid without syntax errors and represents a suitable attempt to ap-
proximate the measurements using differentiable programming, but it does
not work for the measurement data provided.
Pass 13− 14 Code is valid without syntax errors and represents a suitable attempt to ap-
proximate the measurements using differentiable programming. It provides
a reasonable approximation of the measurement data. There are some
comments explaining the code.
Merit 15− 17 Code is valid without syntax errors and represents a suitable attempt to
approximate the measurements using differentiable programming. It pro-
vides a good approximation of the measurement data. Comments provide
insights into the operation of the code and the choice of target functional to
match the data.
Distinction 18− 25 Code is valid without syntax errors and represents a suitable attempt to
approximate the measurements using differentiable programming. It pro-
vides a good approximation of the measurement data. Comments provide
insights into the operation of the code and the choice of target functional to
match the data is clearly motivated and provides insights into the data.