COMP202 Programming Assignment Complexity of Algorithms 28 March 2019
Title: Grouping Monotone Sequence
Submission deadline: 30 April 2019 (Tuesday, 2pm)
Submissions should be made via the Departmental Submission Server:
https://sam.csc.liv.ac.uk/COMP/Submissions.pl
Notes:
1. This assessment is worth 10% of your overall course grade.
2. Standard late penalties apply, as per university policy.
3. Learning outcomes covered by this CA task will also be covered within resit exam: this prevents the need for explicit reassessment of this component. The resit exam will replace the CA component in case this is failed.
Learning outcomes
The purpose of this exercise is for you to demonstrate the following learning outcomes and for me to assess your achievement of them.
1. To demonstrate how the study of algorithmics has been applied in a number of different domains.
2. Tointroduceformalconceptsofmeasuresofcomplexityandalgorithms analysis.
3. To introduce fundamental methods in data structures and algorithms design.
Note: You will be provided with a collection of sample inputs together with correct answers to these inputs. You should aim at submitting your final program only if it produces correct answers to all these inputs.
Academic integrity
The work that you submit should be the product of yourself (alone), and not that with any other student or outside help. Obviously I am providing a source code framework within which you will provide your own method for solving this problem, but the code that you write within this framework should be your own code, not that obtained in collaboration with other students or other outside assistance or sources.
Problem Description
I introduce here a problem of a paritioning type, which I will call Grouping Monotone Sequence. You are given as input a sequence of n positive inte- gers a1, a2, . . . , an and a positive integer k ≤ n. We assume that the input sequence is sorted in a non-decresing order, that is, a1 ≤ a2 ≤ ··· ≤ an. Given a group of consecutive numbers ai, ai+1, . . . , aj for a starting index i and end index j, with i ≤ j, we call
j
cij =(al−aveij)2,
l=i
the cost of group ai,ai+1,…,aj, where
1 j
aveij = j − i + 1 · (
is the average of group ai,ai+1,…,aj; note that j−i+1 is the size of group ai,ai+1,…,aj. Your task is to group these numbers a1,a2,…,an into k groups of consecutive numbers, that is, as they appear in the input order a1, a2, . . . , an, so that total sum of costs of all k groups is minimised.
More formally, you have to decide the k − 1 cutting positions 1 ≤ i1 < i2 <···
You should write a procedure that for any given input sequence of n sorted positive integers (multiple indentical numbers allowed) and any given k ≤ n, finds a grouping with minimum value of the objective function value. Your procedure should only output the value of the objective of this optimal solution (grouping) that only is the integral part of this value. That is, it should compute the grouping with minimum possible value of the objective function among all possible groupings, and then output the objective value (its integral part) of this optimal grouping.
Additionally, you should include a brief idea of your solution in the commented text in your code and you should also include a short analysis and justification of the running time of your procedure. These descriptions are part of the assessment of your solution.
Hints
You are supposed to solve the Grouping Monotone Sequence problem by dynamic programming. Observe that in this problem we have two kinds of objects to maintain: the numbers a1, . . . , an and groups G1, . . . , Gk, which suggests that the dynamic programming solution should involve two kinds of indices. Let C(j,l) denote the minimum objective function value of the grouping of a1, a2, . . . , aj into l groups. Try to express C(j, l) by using values C(j′,l′) for some values j′ < j,l′ < l. These hints should lead to an appropriate recurrence solution to the problem which then you should translate into a sequential solution that fills in this dynamic programming table in an appropriate way.
Programming Language
You will be using Java as the programming language.
Program framework description
I provide a template program called Main.java that you will use (without altering anything but the place to put your code) to include the code of your procedure to solve the Grouping Monotone Sequence problem.
To use this template, after you write your code inside of method called GroupingMonotoneSequence, you must include in the current directory the input text files dataOne.txt and dataTwo.txt. Note, however, that if you need any additional procedures, you may include them outside of the text of the procedure GroupingMonotoneSequence.
To compile your program in command line (under Linux/Unix) use some- thing like this (this may differ within your system):
javac Main.java
Then, you can run your program from command line like this
java Main -opt1
which will run the program with dataOne.txt as input file and will out- put answers (that is the optimal objective function values (their integral part)) to all instances in order they appear in dataOne.txt. You may use your own dataOne.txt in the format (see below) to experiment with your program. Input file dataOne.txt may contain any number of correct input sequences.
Now, if you run the program with
java Main -opt2
this will run the program with dataTwo.txt as input file. In this case, the output will be the indices of inputs from dataTwo.txt that were solved incorrectly by your program together with percentage of correcly solved in- stances. If all instancea are solved correctly, the output should be 100%. File dataTwo.txt contains the same instances as dataOne.txt, but, in addition dataTwo.txt also contains the correct, that is optimal objective function values (their integral part), answers to these instances. You may use dataTwo.txt to test the correctness of your program.
Description of the input data format:
Input data text file dataOne.txt has the following format (this example
has 2 inputs, each input ends with A):
k a1
a2 ... ... an A k a1 a2 ... ... an A
In general file dataOne.txt can have an arbitrary number of distinct inputs of arbitrary, varying lengths. File dataOne.txt contains 31 different instances of the problem. Observe that n is not explicitly given as part of the instance.
Input data text file dataTwo.txt has the following format (this example has again 2 inputs, each input ends with A):
k ans1 a1 a2 ... ... an A k ans2 a1 a2 ... ... an A
There ans1 (ans2, respectively) is the correct value of the optimal (mini- mum) value (its integral part) of the objective function in the optimal solution to the first (second, respectively) instance. File dataTwo.txt con- tains the same 31 instances of the problem as in file dataOne.txt but in addition has the answers. This data can be used to test the correctness of your procedure.
Again, in general file dataTwo.txt can have an arbitrary number of dis- tinct input sequences of arbitrary, varying lengths. It is provided by me with correct answers to these instances.
The solutions shown in dataTwo.txt are (at least) the claimed solutions for each sample input, computed by my program. Recall that your solution should print out the objective function value of the grouping in the given sequence that is the grouping with the smallest possible objective function value for the given instance. Note, that your program does not need to out- put the grouping itself (that is, the cutting positions), but only the objective function value (its integral part) of the optimal grouping.
Program submission
You must submit a single Java source code in the file that must be called Main.java (not the byte code) to the Departmental Submission Server:
https://sam.csc.liv.ac.uk/COMP/Submissions.pl?strModule=COMP202
Your source file Main.java must have the (unaltered) text of the tem- plate provided by me, containig the text of your procedure inside the Group- ingMonotoneSequence method. You are allowed to include additional pro- cedures outside the GroupingMonotoneSequence method if needed.
You are responsible that your source code program Main.java can be compiled correctly with Java compiler and executed on (any) one of the computers in the Computer Science Department’s that runs Java installa- tion under Linux, where I will test your programs. You may also remotely connect to any Linux computer in the Department to compile/test your program. Programs that will not correctly compile on Departmental Linux Java installation will automatically receive mark 0 for the correctness part.
Assessment
Marking on this assessment will be performed on the following basis:
• Accuracy of solution (e.g., does it give correct answers for all of the test cases, and is it a general solution method for instances of this problem?): 50%
• Clarity of solution (Is your program easy to follow? Is it commented to help me see your solution method?): 10%
• Correctness of time complexity description of your procedure and de- scription of your solution. (Have you provided an analysis of the (aymptotic) running time of your method, and is that analysis cor- rect? Is the description of your solution (recursion and sequential implementation) correct and clrearly written?: 20%
• Optimality of solution (Do you have the ”best”, i.e. quickest, solution possible in terms of the asymptotic runtime?): 20%