Cardiff School of Computer Science and Informatics Coursework Assessment Pro-forma
Module Code: CMT304
Module Title: Programming Paradigms
Lecturer: V´ıctor Gutie´rrez-Basulto, Frank C. Langbein and Philipp Reinecke
Assessment Title: Resit Assessment
Date Set: 19/07/21
Submission date and Time: 09/08/21 09:30 am
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.
Your submission must include the official Coursework Submission Cover sheet, which can be found here:
https://docs.cs.cf.ac.uk/downloads/coursework/Coversheet.pdf
Submission Instructions
All submissions must be via Learning Central. Upload the following files in a single zip file,
[student number].zip:
Description | Type | Name |
Cover Sheet | Compulsory | One PDF (.pdf) file | [student number].pdf |
Task 1.1 | Compulsory | Three source files | patent.lp, instance1.lp instance2.lp |
Task 1.2 | Compulsory | One PDF (.pdf) file | task1.pdf |
Task 2.1 | Compulsory | One source file | qubo.hs |
Task 2.2 | Compulsory | One PDF (.pdf) file | task2.pdf |
Task 3 | Compulsory | One Perl (.pl) file | task3.pl |
Task 4 | Compulsory | One PDF (.pdf) file | task4.pdf |
Any deviation from the submission instructions above (including the number and types of files submitted) will result in a mark of zero for the assessment or question part.
Staff reserve the right to invite students to a meeting to discuss coursework submissions.
Assignment
is worth 25 marks, summing up to 100 of the total marks available for this module. This assignment is a coursework that consists of four tasks. Each of the four tasks below
|
|  |
Task 1.1
Consider the following situation:
Patent requests are submitted to the patent office and are reviewed by the technical board. Each patent request is verified and discussed by a group of technical board members chosen by the head of the board. To find a good match between patent request and referees, every member of the technical board sub- mits a bid that classifies all requests that need to be reviewed into four categories depending on their expertise:
EXPERT, KNOWLEDGEABLE, FAMILIAR or INEXPERT
The goal is to write a program to automated this process to help the head of the board. Using a list of bids, indicating the level of expertise for each patent request and board member, it should assign each submitted patent request to a specific number of n members of the technical board such that
the workloads of the technical board members are approximately equal, that is, do not differ by more than m;
no member of the technical board is required to review a submission that is placed in the INEXPERT category;
no member of the technical board is required to review more than k submissions from the FAMILIAR category;
the total number of cases when a submission is assigned to a member who placed it in the EXPERT category is as large as possible.
The parameters n, m and k are arguments set when calling the program.
Write a logic program in ASP which finds all solutions to the problem, given n, m, k and the list of bids in a suitable format. Document your code so the following is clear.
1. How it should be used.
2. 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.
Write also two problem instances (problem instancei.lp, for all i 1, 2 ) to test your program. Document your code so it is clear what the instance is modeling.
Task 1.2:
Write a short report as described below:
1. Provide, in up to 300 words, two arguments for and two arguments against using logic programming to solve the problem.
2. Discuss, in up to 300 words, whether the logic programming paradigm is suitable for this problem or whether another paradigm of your choice is more appropriate, based on your previous arguments.
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 of the first point and indicate whether it is for or against. Only provide two arguments for and against; additional arguments will be ignored.
Criteria for assessment of Task 1
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 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. |
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 at least one) for all problems, with excellent perfor- mance. 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 algo- rithms 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 | An insufficient number of arguments has been submitted and/or they hardly apply to the functional programming paradigm. At most an incomplete at- tempt to discuss the suitability of the functional paradigm has been made. |
4 − 5 | An insufficient number of arguments has been submitted, but they show some understanding of the functional programming paradigm. An attempt has been made to discuss the suitability of the functional paradigm, but it hardly relates to the paradigm. |
Pass | 5 | The required number of valid arguments has been submitted. They are generally valid for the functional programming paradigm, but they repeat similar issues, do not consider the specific problem or contain mistakes in the details. A attempt has been made to discuss the suitability of the functional paradigm and some understanding of this paradigm is present. |
Merit | 6 | The required number of valid arguments has been submitted. They show a clear understanding of the functional programming paradigm and it relates to the problem. The discussion of the suitability of the functional paradigm is well-developed, showing a clear understanding of the issues involved, and indicates the differences to the other chosen paradigm. |
Distinction | 7 − 10 | The required number of valid arguments has been submitted. They show a clear understanding of the functional programming paradigm and the under- lying theoretical concepts and/or realisations on programmable machines and how these relate to the problem. The discussion of the suitability of the functional paradigm is well-developed, showing a deep understanding of practical and theoretical issues involved, and clearly discusses concrete differences to the other chosen paradigm. |
|
|  |
Task 2.1
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. Some QUBO problems can be efficiently
solved with quantum annealing. For this task a simple brute force approach 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
N N
E(x1, x2, . . . , xN ) = Hl,kxlxk = xT Hx
l=1 k=1
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.
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). Make sure you clearly document your approach in the comments. Also clearly document how to call your program with the input matrix H of size N , and how the output vector x is reported.
Task 2.2
Write a short report as described below:
1. Provide, in up to 300 words, two arguments for and two arguments against using functional programming to solve the problem.
2. Discuss, in up to 300 words, whether the functional programming paradigm is suitable for this problem or whether another paradigm of your choice is more appropriate, based on your previous arguments.
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 of the first point and indicate whether it is for or against. Only provide two arguments for and against; additional arguments will be ignored.
Criteria for assessment of Task 2
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. |
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 at least one) for all problems, with excellent perfor- mance. 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 algo- rithms 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 | An insufficient number of arguments has been submitted and/or they hardly apply to the functional programming paradigm. At most an incomplete at- tempt to discuss the suitability of the functional paradigm has been made. |
4 − 5 | An insufficient number of arguments has been submitted, but they show some understanding of the functional programming paradigm. An attempt has been made to discuss the suitability of the functional paradigm, but it hardly relates to the paradigm. |
Pass | 5 | The required number of valid arguments has been submitted. They are generally valid for the functional programming paradigm, but they repeat similar issues, do not consider the specific problem or contain mistakes in the details. A attempt has been made to discuss the suitability of the functional paradigm and some understanding of this paradigm is present. |
Merit | 6 | The required number of valid arguments has been submitted. They show a clear understanding of the functional programming paradigm and it relates to the problem. The discussion of the suitability of the functional paradigm is well-developed, showing a clear understanding of the issues involved, and indicates the differences to the other chosen paradigm. |
Distinction | 7 − 10 | The required number of valid arguments has been submitted. They show a clear understanding of the functional programming paradigm and the under- lying theoretical concepts and/or realisations on programmable machines and how these relate to the problem. The discussion of the suitability of the functional paradigm is well-developed, showing a deep understanding of practical and theoretical issues involved, and clearly discusses concrete differences to the other chosen paradigm. |
|
|  |
Task 3
Task 1.1: Consider the following situation:
A set of image files (GIF, PNG, and JPG) have been accidentally renamed wrongly: The file endings have been removed. For instance, a file whose original name was test.gif is now called test. The files may be mixed with files whose
file endings are intact and with files that are not of type GIF, PNG, or JPG, and they may be spread across subdirectories. You cannot install software on the machine you are using.
Your task is to write a Perl script that restores the original file endings for all such files in a set of directories and their subdirectories. That is, after running the script, each GIF file must have the file ending .gif, each PNG file must have the file ending .png, and each JPG file must have the file ending .jpg. All other files must be left untouched. In particular, image files that already have the correct file ending should be left alone.
It must be possible to run the script from the command line as follows:
task3.pl [directories]
where [directories] is a space-separated list of directories where the file endings need to be restored. The script should print the names of all renamed files on STDOUT in the following format:
original name -> new name
Criteria for assessment of Task 3
Your script must run on lapis.cs.cf.ac.uk. The script will be assessed as follows:
1. The script will be run against the directory images/ in the provided archive example-1.zip.
It will be run in the directory example-1/ as follows:
rm report.txt
task3.pl images/ > report.txt
After execution, the contents of images/ should be exactly like the contents of the directory images-after/ in example.zip, the file report.txt should exist, and it must have the exact same contents (including the format) as the file report.txt in example.zip.
2. Your script will be run against several other directories, using different combinations of parameters that are allowed according to the description, and checked as described above.
3. Your script will be manually inspected for code quality.
Breakdown of marks
Please note: Your script must not depend on any software not present on the specified machine (lapis.cs.cf.ac.uk), and you must not request that any software be installed on that machine. Any such request will be denied. The script will be executed with a Bash shell. If the script does not run exactly as specified, no attempt will be made to make it run, and you will not earn any marks.
Criteria | Detailed criteria | Range marks |
Operation with example case | The script runs | [0,1] |
| GIF files renamed correctly | [0,1] |
| PNG files renamed correctly | [0,1] |
| JPG files renamed correctly | [0,1] |
| All other files untouched | [0,1] |
Report as specified and correct | [0,1] |
Operation with unknown cases | GIF files renamed correctly | [0,2] |
| PNG files renamed correctly | [0,2] |
| JPG files renamed correctly | [0,2] |
| All other files untouched | [0,2] |
| Report as specified and correct | [0,2] |
Error handling | Parameter errors | [0,1] |
| File/directory errors | [0,2] |
| Error messages | [0,2] |
Code quality | Comments present and helpful | [0,1] |
| Clear structure | [0,1] |
| Use of existing tools | [0,2] |
|
|  |
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 |Aj) and
|Bj).
Analyse the operation of the circuit. In particular, derive the full operator of the circuit and describe the mapping from A B to Aj Bj . Based on this mapping, what operation does the circuit implement?
In addition, construct a circuit that inverts this operation, mapping |Aj)|Bj) back to the input
|A)|B) values. Justify that your circuit is correct.
Criteria for assessment of Task 4
Fail | 0 | No document has been submitted. |
1 − 6 | The circuit operation has not been identified correctly and the justification is not correct. There is no discussion of how to invert the circuit. |
7 − 12 | There is a discussion of the circuit operation that shows some insights, but the operation is not correctly identified and the justification is incomplete. The approach of inverting the circuit shows some insights, but is not suit- able. |
Pass | 13 − 14 | The circuit operation has been correctly identified, with some mistakes, and the justification shows some understanding of the involved quantum opera- tions. The approach of how to invert the circuit points in the right direction, but remains incomplete. |
Merit | 15 − 17 | The circuit operation has been correctly identified and the justification is suitable, even if there are minor mistakes or incomplete arguments. The approach to invert the circuit is suitable and well justified, but some minor issues have been missed. |
Distinction | 18 − 25 | The circuit operation has been correctly identified and the justification is complete. The approach to invert the circuit is correct and fully justified. |
Learning Outcomes Assessed
Evaluate and apply the functional and logic programming paradigms to solve a given problem.
Evaluate and apply a suitable programming paradigm and language from a selection of them to solve a given problem.
Discuss and contrast the issues, features, design and concepts of a range of pro- gramming paradigms and languages, such as imperative, functional, declarative, logic, scripting, filter-based programming, pattern matching and quantum computing.
• Explain the conceptual foundations of various programming paradigms.
