UNIVERSITY OF CHESTER - Postgraduate Programmes Assignment Specification Faculty of Science and Engineering Department of Computer Science Module No CO7312 Module Title Algorithmics Academic Year 2016-17 Assessment No 1 Submission Date 19th January 2017 Feedback due by 16th February 2017 Assignment Title Learning Objectives Assessed 1. Analyse the performance of algorithms with regard to processor and memory usage 2. Design and critically justify a range of algorithms for novel problems 3. Discuss the complexity of problems both in relation to algorithmic efficiency and membership of established complexity classes. 4. Apply trade-offs between time consumption and accuracy for complex problems Submission Information Submit all required files in a zipped folder via Moodle Extensions and Plagiarism Extensions Extensions can only be granted by Dr Linda Rayner, Head of Department at least 48 hours in advance of the deadline (by appointment through the Departmental Administrator), and written evidence will be required. Late work is penalised at the rate of 10% per day. Plagiarism The material you submit must be your own work. The penalties for plagiarism are severe. The minimum penalty is usually zero for that piece of work. Further information is available at Portal > Support Departments > Academic Quality Support Services > Academic Malpractice   Assignment Brief You are required research and solve a basic form of the multiprocessor scheduling problem, as follows: • Each instance is defined by a number of processors k and a set J of times for some processes to be executed. You may assume that all processors have the same speed. • Each process in J must be assigned to exactly one of the processors • Only one job can execute on a single processor at a time • You must minimise the time taken to execute all processes So for example, if we have two processors and J = [3,7,4,6] the optimum solution would be to have the first two jobs on one processor and the second two on the other. 1. Write a short report (no more than 1000 words) on this problem, discussing its complexity and any known algorithms or heuristics which can be used to tackle it. You should refer to published research on the topic throughout. 2. You should produce a Mixed Integer Programming formulation of this problem and use it to solve a small instance to optimality using OpenSolver. This instance will be provided for each of you by the module leader. 3. Additionally, you should produce a heuristic algorithm for faster, inexact solution of larger problems. This should include a discussion of the algorithm’s complexity with regard to both time and space. The algorithm should be coded and tested using a programming language of your choosing. A hint for this section is to start with a simple solution and build on it. Remember even powerful meta-heuristics are essentially adaptations of simpler methods.   Assessment Criteria Report Model Heuristic 70% and above Report demonstrates a genuine grasp of the logical nature of the problem. Complexity is established through discussion of relationship with other known problems in its class. Model solves the provided instance correctly, is economical in its use of variables and contraints, Heuristic is powerful and demonstrated to estimate solution to a range of problems in testing, perhaps using randomly generated instances. A meta-heuristic is employed successfully. Complexity analysis is present and correct throughout. 60-70% As above but may be a little more vague in places Model solves instance correctly but may be a little overcomplicated in places. An effective heuristic is developed but perhaps not tested very thoroughly. Small oversights in complexity analysis may be present. 50-60% Some small misconceptions may be present in discussion, perhaps regarding nature of problem or its complexity. May stray on to the subject of similarly named but logically unrelated problems. Model demonstrates some understanding but perhaps some constraints are not quite implemented correctly. As above but perhaps with simpler techniques adopted and/or limited testing 40-50% Similar to the above but with larger flaws and misconceptions whilst still conveying a reasonable grasp of the problem under discussion. As above but with less understanding demonstrated and greater error in formulation. A reasonable attempt made at solving the problem but perhaps a little basic or with oversights in checking for feasibility. Below 40% Either a failure to properly engage with the topic or serious gaps in understanding are present. Model incomplete or lacking in general coherence. Difficult to see relationship between model and problem. Little or no coherent attempt to solve the problem