Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP202 Programming Assignment
Complexity of Algorithms
Title: Longest Range of Peaks Problem
Submissions should be made via CANVAS:
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 posi-
tive, 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 inputA[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 Prob-
lem 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 com-
mented 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.