代写COMP202、代写Java语言程序

日期：2022-04-17 02:31

COMP202 Programming Assignment

Complexity of Algorithms 01 April 2022

Title: Longest Range of Peaks Problem

Go to COMP202 and to Assignment:

COMP202: CA2 – PROGRAMMING ASSIGNMENT 2022

Notes:

1. This assessment is worth 15% 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. To introduce formal concepts of measures of complexity and algorithms

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

Suppose that we are given an array A[1, 2, . . . , n] containing n ≥ 3 positive,

not necessary distinct, integers. We do not assume that the input array

is sorted. We first define a notion of a peak. Any three consecutive indices

i, i+1, i+2 such that 1 ≤ i ≤ n?2 and A[i] < A[i+1] and A[i+1] > A[i+2],

is called a peak; note that the inequalities are strict.

A range is a collection of disjoint peaks. Formally, a range that consists

of k ≥ 1 peaks is the following collection of indices in array A: {i1, i2, . . . , ik}

such that:

(1) 1 ≤ i1 < i2 < · · · < ik ≤ n ? 2 (indices are distinct increasing integers

from {1, 2, . . . , n}),

(2) i1+2 < i2, i2+2 < i3, · · · , ik?1+2 < ik (peaks are disjoint, i.e., indices

are separated from one another by at least 2 positions in array A),

(3) Each three consecutive indices ij , ij + 1, ij + 2 (for j = 1, 2, . . . , k) form

a peak, that is, A[ij ] < A[ij + 1] and A[ij + 1] > A[ij + 2] for each

j = 1, 2, . . . , k (we have k disjoint peaks)

(4) For every two consecutive peaks ij , ij+1, ij+2 and ij+1, ij+1+1, ij+1+

2, (for j = 1, 2, . . . , k ? 1), we have the following additional condition:

A[ij + 1] ≥ A[ij+1] and A[ij + 2] ≤ A[ij+1] (note weak inequalities

here). This condition intuitively means that the east slope of the peak

ij , ij + 1, ij + 2 contains the base (first element ij+1) of the west slope

of the very next peak ij+1, ij+1 + 1, ij+1 + 2.

If a range consists of k ≥ 1 peaks, then its length is k. The Longest

Range of Peaks Problem is to find the length of the longest range of peaks

in the input array A, or output 0 if there is no peak in array A.

Examples:

Let us consider input A[1, 6, 2, 11, 2, 10, 5, 7, 3] with n = 9. Here A[1], A[2], A[3];

A[3], A[4], A[5]; A[5], A[6], A[7]; A[7], A[8], A[9] are four peaks in A. These

are all peaks in array A. We also have the following range of length 2:

A[1], A[2], A[3]; A[5], A[6], A[7]. Another range of length 2 is: A[3], A[4], A[5];

A[7], A[8], A[9]. And another range of length 2 is: A[1], A[2], A[3]; A[7], A[8], A[9].

Here, any of these 3 ranges is the the longest range in this instance of the

problem and so the output of the Longest Range of Peaks Problem is 2.

Let us consider now input A[1, 6, 2, 2, 2, 10, 5, 7, 8, 3] with n = 10. Here,

the longest range has length 3 and it is: A[1], A[2], A[3]; A[5], A[6], A[7];

A[8], A[9], A[10], so the output of the Longest Range of Peaks Problem is 3.

Observe, for instance, that A[1], A[2], A[3]; A[8], A[9], A[10] is not a range

because the condition (4) above is false, namely, A[8] = 7 is not between

A[3] = 2 and A[2] = 6.

If the input array is sorted in non-decreasing order, for instance A[1, 6, 8, 8, 10, 13],

then there is no peak, and so the output of the Longest Range of Peaks Problem

is 0. Similarly, if the array is sorted in non-increasing order, for instance

A[15, 11, 4, 4, 3, 3], then there is no peak, and so the output of the problem

is 0.

Some further examples of inputs.

Suppose, for instance, that n = 13 and that the input sequence is:

1 3 2 1 7 5 7 10 1 1 1 3 2,

that is, A[1] = 1, A[2] = 3, A[3] = 2, A[4] = 1, A[5] = 7, A[6] = 5, A[7] =

7, A[8] = 10, A[9] = 1, A[10] = 1, A[11] = 1, A[12] = 3, A[13] = 2. Then, the

longest range of peaks is: A[4], A[5], A[6]; A[7], A[8], A[9]; A[11], A[12], A[13]

and has length 3. The output to the problem is 3.

Suppose, for instance, that n = 11 and that the input sequence is:

1 5 2 2 2 7 4 4 4 5 4,

that is, A[1] = 1, A[2] = 5, A[3] = 2, A[4] = 2, A[5] = 2, A[6] = 7, A[7] =

4, A[8] = 4, A[9] = 4, A[10] = 5, A[11] = 4. Then, the longest range of peaks

is: A[1], A[2], A[3]; A[5], A[6], A[7]; A[9], A[10], A[11] and has length 3. The

output to the problem is 3.

For further examples of inputs together with answers, see the text file

dataTwo.txt that I provide (see explanation of the data format below). The

file dataTwo.txt contains also solutions.

The task: You should design a dynamic programming algorithm and write

a procedure to implement the sequential implementation of your dynamic

programming algorithm, that for any given input sequence of n positive

integers (multiple identical numbers allowed) finds the length of the longest

range of peaks (or 0 if there is no peak in the sequence). Your procedure

should only output the value of the longest range of peaks or 0.

Additionally, you should include a brief idea of your solution in the commented

text in your code, describing how you derive your recursive dynamic

programming solution first and ideas of its sequential implementation. You

should also include a short analysis and justification of the running time of

your procedure in terms of n. These descriptions are part of the assessment

of your solution.

Hints

You are supposed to solve the Longest Range of Peaks problem by dynamic

programming. Some exercises from the exercise list on dynamic programming

could inspire your solution here. In your solution (described as part

of the assessment) you should first define an appropriate dynamic programming

table and then come up with a recurrence solution to the problem first,

which then you should translate into a sequential solution that fills in a dynamic

programming table in an appropriate way in your implementation.

Programming Language

You will be using Java as the programming language.

Program framework description

IMPORTANT: Before submitting, you must rename your file Main123456789.java

where 123456789 is replaced with all digits of your Student ID. You also

must rename the main public class Main123456789{ } in your file 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 Longest Range of Peaks problem. Note

that you may add additional procedures outside of the procedure LongestRange

if needed.

To use this template, after you write your code inside of procedure called

LongestRange, 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 LongestRange.

To compile your program in command line (under Linux/Unix) use something

like this (this may differ 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 dataOne.txt as input file and will output

answers (that is the values of the longest range or 0) 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 Main123456789 -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 correctly solved

instances. If all instances 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 values of the longest

ranges or 0, 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; note the number 0 is the part of the

input format, but not part of the input sequences):

0

In general file dataOne.txt can have an arbitrary number of distinct inputs of

arbitrary, varying lengths. File dataOne.txt contains 50 different instances

of the problem. The first 6 instances are the same as the examples above.

Observe that n is not explicitly given as part of the instance. Also 0 which

starts each instance does not have any particular purpose; it is just format

of the input data to mark beginning of an instance.

Input data text file dataTwo.txt has the following format (this example

has again 2 inputs, each input ends with A):

There ans1 (ans2, respectively) is the value of the longest range for the first

(second, respectively) instance or 0 if there is no peak in those instances.

File dataTwo.txt contains the same 50 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 distinct

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 length of the longest range in the given sequence for

the given instance, or 0 in case if this instance contains no peaks. Note, that

your program does not need to output this longest range of peaks.

Program submission

You must submit a single Java source code in a single file that must

be called Main123456789.java (not the byte code), where 123456789 is

replaced with all digits of your Student ID, via CANVAS:

https://https://liverpool.instructure.com/

Go to COMP202 and to Assignment: COMP202: CA2 – PROGRAMMING

ASSIGNMENT 2022

IMPORTANT: Before submitting, you must rename your file Main123456789.java

where 123456789 is replaced with all digits of your Student ID. You also

must rename the main public class Main123456789{ } in your file by also

replacing 123456789 by all digits of your Student ID.

Your source file Main123456789.java must have the (unaltered) text of

the template provided by me, containing the text of your procedure inside

the LongestRange method. You are allowed to include additional procedures

outside the LongestRange method if needed. In addition, within commented

parts of method LongestRange, you should describe your recursive solution

and how you implement it sequentially. Moreover, you should also describe

a short running time analysis of your sequential implementation in terms of

n and big-O notation.

You are responsible that your source code program Main123456789.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

installation 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?): 60%

? Clarity of solution (Is your program easy to follow? Is it commented

to help me see your solution method?): 10%

? Correctness of time complexity (in big-O notation of the problem size

n) description of your procedure and description of your solution.

(Have you provided an analysis of the (asymptotic) running time of

your method, and is that analysis correct? Is the description of your

solution (recursion and sequential implementation) correct and clearly

written?: 20%

? Optimality of solution (Do you have the ”best”, i.e., quickest, solution

possible in terms of the asymptotic runtime?): 10%