编程代写｜COMP202 Programming Assignment Complexity of Algorithms

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.

Note: You will be provided with a collection of sample inputs together with correct answers to these inputs. You should aim at submitting your fifinal 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

The Square Grouping problem is defifined as follows. You are given as input a sequence of n positive integers a1, a2, . . . , an and a positive integer k ≤ n. Your task is to group these numbers into k groups of consecutive numbers, that is, as they appear in the input order a1, a2, . . . , an, so as to minimise the total sum of the squares of sums of these numbers within each group.

More formally, you have to decide the k − 1 cutting positions 1 ≤ i1 < i2 < · · · < ik−1 ≤ n − 1, where (we assume below that i0 = 1):

Gj = {aij−1+1, aij−1+2, · · · , aij }

Then, such feasible solution, that is, grouping into these k groups, has the value of the objective function equal to

k Xj=1Xai∈Gj ai 2.

Your goal is to fifind such grouping into k groups so that this objective function is minimised.

Suppose, for instance, that n = 5 and k = 3 and that input sequence is:

5 7 11 4 21,

that is, a1 = 5, a2 = 7, a3 = 11, a4 = 4, a5 = 21. Then, for example, setting the k − 1 = 2 cutting positions as follows

5 7 | 11 | 4 21,

that is the cutting positions i1 = 2, i2 = 3, defifine the following k = 3 groups G1 = {5, 7}, G2 = {11}, G3 = {4, 21}. The objective function value of this grouping is

(5 + 7)2 + (11)2 + (4 + 21)2 = 144 + 121 + 625 = 890.

Observe that there is a better solution here, with the following grouping

5 7 | 11 4 | 21,

The objective function value of this grouping is

(5 + 7)2 + (11 + 4)2 + (21)2 = 144 + 225 + 441 = 810,and it can be checked that this is the optimal grouping, that is, 810 is the smallest possible value of the objective function among all possible groupings in this instance.

For further examples of inputs together with values of their optimal solutions, see the text fifile data2.txt that I provide (see explanation of the data format below). In fact the example sequence above, 5 7 11 4 21, with k = 3 is the fifirst instance in data1.txt and in data2.txt (data2.txt contains also solutions).

Observe that the input sequence a1, . . . , an need not be sorted and you are not supposed to change the order of these numbers, but only fifind appropriate k − 1 cut points that defifine the k groups (each group must be non-empty, that is, must contain at least one number). The task is, given any sequence of n (strictly) positive integers and k ≤ n, fifind the grouping that has the smallest possible objective function value. Note that the input sequence may contain the same number multiple times.

Also observe that it is possible that k = n in the input to this problem (it is impossible that k > n, though). For instance if the input sequence is as above

5 7 11 4 21,

and k = n = 5, then there exists only one possible feasible grouping into k = 5 groups with the following cut points:

5 | 7 | 11 | 4 | 21,

and the objective value of this grouping is

(5)2 + (7)2 + (11)2 + (4)2 + (21)2 = 25 + 49 + 121 + 16 + 441 = 652,

and this is the (optimal) solution to this instance with k = 5.

You should write a procedure that for any given input sequence of n positive integers and any given k ≤ n, fifinds 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 is, it should compute the grouping with minimum possible value of the objective function among all feasible groupings, and then output the objective value 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 justifification of the running time of your procedure. These descriptions are part of the assessment of your solution.

Hints

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 dynamicprogramming solution should involve two kinds of indices. Similarly to this,when dealing with dynamic programming solution to the {0, 1} Knapsack problem, we also used two kinds of indices, see lecture notes on Fundamental methods – Dynamic Programming. I then suggest you to start your investigations with making some simple observations similar to those we have made in these lecture notes for the {0, 1} Knapsack and Weighted Interval Scheduling problems, respectively, namely that the optimal solutions to these problems either contain the last item (interval, resp.) n or not.

Namely, ask yourself the question: what if you already knew the cutting position of the last group? And, as usual, you should start by defifining appropriate dynamic programming table and come up with the appropriate recurrence solution to the problem. After you have your recursive solution,you should translate it to a sequential solution that fifills in the table in an appropriate way.

Programming Language

You will be using Java as the programming language.

Program framework description

IMPORTANT: Before submitting, you must rename your fifile Main123456789.java where 123456789 is replaced with all digits of your Student ID. You also must rename the main public class Main123456789{ } in your fifile by also replacing 123456789 by all digits of your Student ID.

I provide a template program called Main123456789.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 Square Grouping problem.

To use this template, after you write your code inside of method called SquareGrouping, you must include in the current directory the input text fifiles data1.txt and data2.txt. Note, however, that if you need any additional procedures, you may include them outside of the text of the procedure SquareGrouping.

To compile your program in command line (under Linux/Unix) use something like this (this may diffffer within your system):

javac Main123456789.java

Then, you can run your program from command line like this

java Main123456789 -opt1

which will run the program with data1.txt as input fifile and will output answers to all instances in order they appear in data1.txt. You may use your own data1.txt in the format (see below) to experiment with your program.

Input fifile data1.txt may contain any number of correct input sequences.

Now, if you run the program with

java Main123456789 -opt2

this will run the program with data2.txt as input fifile. In this case, the output will be the indices of inputs from data2.txt that were solved incorrectly by your program together with percentage of correctly solved instances. If all instances are solved correctly, the output should be 100%.

File data2.txt contains the same instances as data2.txt, but, in addition data2.txt also contains the correct answers to these instances. You may use data2.txt to test the correctness of your program.