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:
- This assessment is worth 15% of your overall course grade.
- Standard late penalties apply, as per university policy.
- 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. - To demonstrate how the study of algorithmics has been applied in a
number of different domains. - To introduce formal concepts of measures of complexity and algorithms
analysis. - 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: - 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: - 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.ins…
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