COSC 2123/1285 算法分析

Algorithms and Analysis
COSC 2123/1285
Assignment 2: Algorithm Design & Complexity Analysis
Assessment Type Individual Assignment. Submit online via Canvas → Assignments
→ Assignment 2. Clarifications/updates/FAQ can be
found in Canvas Announcements and Discussion → Assignment
2 General Discussion.
Due Date Week 13, 11:59pm, 4th of June, 2021
Marks 40
• If you are asked to develop/design an algorithm, you need to describe it in
plain English first, say a paragraph, and then provide an unambiguous pseudo
code. The description must include enough details to understand how the algorithm
runs and what the complexity is roughly. All algorithm descriptions and
pseudo codes required in this assignment are at most half a page in length.
• Standard array operations such as sorting, linear search, binary search, sum,
max/min elements, as well as algorithms discussed in the pre-recorded lectures
can be used straight away (but make sure to include the input and output if you
are using them as a library). However, if some modification is needed, you have to
provide a full description. If you are not clear whether certain algorithms/operations
are standard or not, post it to Canvas Discussion Forum or drop us an email
• Marks are given based on correctness, conciseness (with page limits), and clarity
of your answers. If the marker thinks that the answer is completely not understandable,
a zero mark might be given. If correct, ambiguous solutions may still
receive a deduction of 0.5 mark for the lack of clarity.
• Page limits are applied to ALL problems in this assignment. Over-length answers
may attract mark deduction (0.5 per question). We do this to (1) make sure
you develop a concise solution and (2) to keep the reading/marking time under control.
Please do NOT include the problem statements in your submission,
because this may increase Turnitin’s similarity scores significantly.
• In the submission (your PDF file), you will be required to certify that the submitted
solution represents your own work only by agreeing to the following statement:
I certify that this is all my own original work. If I took any parts from
elsewhere, then they were non-essential parts of the assignment, and they
are clearly attributed in my submission. I will show that I agree to this
honour code by typing “Yes":
Problem 1 (3 marks - at most 1/2 page). Determine if the following statements are true
or false AND provide a formal proof using either limits or the definitions of the big-O,
big-Omega, and big-Theta notations. For instance, to prove that f (n) ∈ O(g(n)) or f (n) ∉
O(g(n)), using the definitions of big-O, we need to demonstrate the existence of a constant
c and a sufficient large n0 such that f (n) ≤ c g(n) for all n ≥ n0, or showing that there are
no such values. Using limits, for instance, we need to show that limn→∞ f (n)/g(n) < ∞
for f (n) ∈ O(g(n)), or showing that limn→∞ f (n)/g(n) = ∞ for f (n) ∉ O(g(n)). Note that
there will be no marks if only true/false answer is given.
a) [1 mark] p
2 +2n ∈ Θ(n).
b) [1 mark] n
100 ∈ O(e
c) [1 mark] loge
) ∈ Ω(
Problem 2 (3 marks - at most 2 sentences). Arrange the following functions in an increasing
order of their growth rates.
f1(n) = 1000n,
f2(n) = (logn)
f3(n) = n!,
f4(n) = nlogn,
f5(n) = 2
Problem 3 (4 marks - at most 1 page). In the following questions we assume that m
grows more slowly than logn.
a) [2 marks] Design an in-place algorithm (description + pseudo code + complexity
analysis) to find m smallest elements (possibly repeated) in an array of real numbers
of size n with time complexity O(nm). Note that no extra data structures
are allowed.
a) [2 marks] Design another algorithm (description + pseudo code complexity analysis)
to find m smallest elements (possibly repeated) in an array of real numbers of size
n with time complexity O(nlogm). Extra data structures are allowed.
Problem 4 (2 marks - at most 1/2 page). Design a non-recursive algorithm (algorithm
description + pseudo code) that takes as input the root of a binary search tree and
return the maximum key stored in the tree.
Problem 5 (5 marks - at most 1.5 pages). Let A be an array of size n contains a list of
records in which the field "gender" has value either M or F. Suppose that n is even for
a) [2 marks] Design an in-place recursive decrease-and-conquer algorithm (description

  • pseudo code) of complexity O(n
    ) that swaps the elements of the array so that
    their genders alternate between M and F as much as possible. If there are more
    M than F, then all the uncoupled M are grouped at the end of the array. Similarly,
    if there are more F than M, then all the uncoupled F are grouped at the end of the
    array. For example, if the list is
    then the output could be
    Note that inefficient algorithm, in particular, algorithms with complexity Ω(n
    will attract a zero mark.
    a) [2 marks] Determine the recurrence relation for the number of comparisons C(n)
    required by your algorithm and solve it using the backward substitution method.
    What is the complexity class of C(n) in big-O notation?
    b) [1 marks] Determine the recurrence relation for the number of swaps S(n) required
    by your algorithm and solve it using the backward substitution method. What is
    the complexity class of S(n) in big-Theta notation?
    Problem 6 (9 marks - at most 2 pages). Two years after graduation, you are hired by
    RMIT’s School of Computing Technologies as a software engineer. Your first task is to
    develop a Course Management software that can answer common students’ questions
    automatically. One of the common questions, frequently asked by students who don’t
    want to complete the whole program but are only interested in a few courses, is about
    the number of minimum credits one needs to accumulate before taking a certain course.
    The input is a curriculum which consists of n courses, indexed by integers from 0 to
    n − 1. Each course i has ci credit points and also a list Pi of prerequisites (PRQs). Let
    m be the number of pairs (i, j), 0 ≤ i 6= j ≤ n −1, where i is a PRQ of j. Your task is to
    design two algorithms (description + pseudo code + complexity analysis) that
    return the total number of credits Ti a student has to accumulate before each course
    i = 0,1,...,n −1, can be taken, under two different scenarios in Part a) and Part b). Your
    algorithm must output the minimum number of credits required as PRQs for every
    course (see Fig. 1).
    i 0 1 ··· n−1
    Ti ? ? ··· ?
    Figure 1: This is the table of the accumulated credits Ti required before taking each
    course i, 0 ≤ i ≤ n−1, output by your algorithms.
    a) [3 marks] Scenario 1: the PRQs are nonequivalent, that is, each course can be taken
    only if ALL PRQs have been completed. Apply your algorithm to the toy example
    in Fig. 2 and complete the output table (see Fig. 2).
    b) [6 marks] Scenario 2: the PRQs are equivalent, that is, if Pi 6= ∅, then the course
    i can be taken as long as ONE of the PRQs in Pi has been completed. Design a
    dynamic programming algorithm to achieve your task. Apply your algorithm
    to the toy example in Fig. 2 and complete the output table (see Fig. 2). Note that
    you should also explain explicitly the recurrence formula and the backtrace
    (given i, list the sequence of courses that a student needs to take before enrolling
    in course i with minimum sum of credits).
    Note that to achieve full marks, the algorithms should have complexity O(nm +
    ) in Part a) and O(n + m) in part b) or better. Inefficient algorithms, e.g. with
    complexity exponential in n or m, will attract a zero mark.
    Figure 2: A toy example for Problem 6 is given with input and required output. An arrow
    i → j implies that Course i is a PRQ of Course j. The number next to each course is its
    number of credits. For instance, Algorithms & Analysis has 12 credits and has Further
    Programming and Advanced Programming Techniques as prerequisites.
    Problem 7 (7 marks - at most 2 pages including the drawing of the tree). The year is
    2040, and you are now on a voyage to a newly discovered Earth-like planet, named DST,
    which is the habitat to many mysterious and previously unknown species. After years
    of digging and researching, your biologist and palaeontologist colleagues have collected
    a large number of DNA sequences from all living or dead animals they encountered, and
    now ask for your help in building an evolutionary tree, which represents the ancestral
    relationships among all animals.
    The root of the evolutionary tree is the predicted ancestor of all species. Each node in
    the tree represents the DNA sequence (or rather, a DNA strand consisting of six bases A,
    C, G, T, H, J) of one species. The distance between any two strands Su and Sv is d(Su,Sv)
    defined as the minimum number of base deletions, insertions, and substitutions required
    to turn Su into Sv. The tree must satisfy the following two evolution rules (see Fig. 3).
  • (Rule 1) Each species evolves away from the ancestors: if u is an ancestor of v, then
    d(Su,Sv) ≥ d(Sx,Sy) for every pair of parent and child (x, y) along the path of the
    tree from u down to v (including u and v).
  • (Rule 2) Sibling species evolve away from each other: if v and w are not parent and
    child and their closest common ancestor is u, then d(Sv,Sw) ≥ d(Sx,Sy) for every
    pair of parent and child (x, y) along the paths of the tree from u downto v and from
    u down to w (including u, v, and w themselves).
    Figure 3: This is a toy example that illustrates the rules in the evolutionary tree.
    a) [3 marks] Given a root r, develop an efficient algorithm that builds an evolutionary
    tree rooted at r and satisfying Rule 1 and Rule 2. Include an algorithm description
    and an unambiguous pseudo code. Provide a complexity analysis of your algorithm
    with respect to the input size n and , where is the maximum length of each DNA
    sequence. Note that incorrect or inefficient algorithms will not receive a full mark,
    in particular, exponential-time complexity algorithms may attract a zero mark.
    b) [1 marks] Prove that your algorithm produces an evolutionary tree satisfying Rule
  • and Rule 2. Hint: if you are on the right track, the proof should take a short
    paragraph only.
    c) [3 marks] Implement your algorithm and run it on the dataset provided in Fig. 4
    (see also Fig. 5). Suppose that beefalo is the predicted ancestor of all other
    species. Submit the code together with a drawing of the (rooted) evolutionary tree
    for this example (with nodes labelled by names or images of the creatures).
    Species DNA sequence
    Beefalo AACTHJJTGG
    Bearger TTHJJGTAT
    Bunnyman AACTHJJGG
    Buzzard CAAHGHTG
    Deerclops HJCTHJJGT
    Elder Mandrake CATHJHTJGT
    Eyeplant CTHJJGT
    Grass Gekko CTJHJT
    Moleworm AACTHJJ
    Pengull AHCTHJJTGG
    Tallbird CJHHJJHGA
    Tentacle JJHHGH
    Terrorbeak AHATHHJJTAC
    Volt Goat AHCTHJJTG
    Figure 4: A dataset that contains the names/DNAs of 20 species encountered on DST.
    Figure 5: Newly discovered species, illustrated by Klei Entertainment.
    Problem 8 (7 marks - at most 3 pages). Research a problem of your own interest in any
    field (science, engineering, technology) that can be solved by a computer algorithm.
    a) [5 marks] Write a 1- to 2-page report on an existing algorithm that is among
    the most efficient ones solving that particular problem and include in your report:
    (1) the problem statement, (2) why is the problem important/interesting, (3) the
    algorithm description, (4) a pseudo code, and (5) a complexity analysis. Note that
    the problem/algorithm should NOT be among those already discussed in the prerecorded
    lectures. You should include a few (1-5) references that you used when
    researching the problem/algorithm, but the writing should be your own. A similarity
    score of 25% and above between your report and any existing source may
    indicate plagiarism. Marks will be decided based on the correctness, clarity,
    and the sophistication of the problem/algorithm discussed. If the report is not
    well written or the problem/algorithm is trivial or straightforward, you may not
    receive a full mark.
    b) [2 marks] Propose your own improvement of that algorithm, either in space or
    time complexity. It should be your own idea and not from any existing source.
    You should state clearly at first what the improvement is, and then explain how
    you do it. You may receive from 0 to 2 marks depending on the significance of the
  • Submission
    The final submission (via Canvas) will consist of:
    • Your solutions to all questions in a PDF file of font size 12pt and your agreement
    to the honour code (see the first page). You may also submit the code in Problem 7.
    Late Submission Penalty: Late submissions will incur a 10% penalty on the total
    marks of the corresponding assessment task per day or part of day late, i.e, 4 marks per
    day. Submissions that are late by 5 days or more are not accepted and will be awarded
    zero, unless Special Consideration has been granted. Granted Special Considerations
    with new due date set after the results have been released (typically 2 weeks after the
    deadline) will automatically result in an equivalent assessment in the form of a
    practical test, assessing the same knowledge and skills of the assignment (location and
    time to be arranged by the coordinator). Please ensure your submission is correct and
    up-to-date, re-submissions after the due date and time will be considered as late submissions.
    The core teaching servers and Canvas can be slow, so please do double check
    ensure you have your assignments done and submitted a little before the submission
    deadline to avoid submitting late.
    Assessment declaration: By submitting this assessment, you agree to the assessment
    declaration - assessment-andexams/assessment/assessment-declaration
  • Plagiarism Policy
    University Policy on Academic Honesty and Plagiarism: You are reminded that all submitted
    work in this subject is to be the work of you alone. It should not be shared with
    other students. Multiple automated similarity checking software will be used to compare
    submissions. It is University policy that cheating by students in any form is not permitted,
    and that work submitted for assessment purposes must be the independent work of
    the student(s) concerned. Plagiarism of any form will result in zero marks being given
    for this assessment, and can result in disciplinary action.
    For more details,
  • Getting Help
    There are multiple venues to get help. We will hold separate Q&A sessions exclusively
    for Assignment 2. We encourage you to check and participate in the discussion forum on
    Canvas, on which we have a pinned discussion thread for this assignment. Although we
    encourage participation in the forums, please refrain from posting solutions or suggestions
    leading to solutions.