乐趣区

关于算法:COMP202算法复杂度分析

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.
  4. To demonstrate how the study of algorithmics has been applied in a
    number of different domains.
  5. To introduce formal concepts of measures of complexity and algorithms
    analysis.
  6. 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:
  7. 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:
  8. 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
退出移动版