Algorithms and Analysis

COSC 2123/1285

Assignment 2: Algorithm Design & Complexity Analysis

Assessment Type Individual Assignment. Submit online via Canvas → Assign-

ments → Assignment 2. Clarifications/updates/FAQ can be

found in Canvas Announcements and Discussion → Assign-

ment 2 General Discussion.

Due Date Week 13, 11:59pm, 4th of June, 2021

Marks 40

IMPORTANT NOTES

• 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 algo-

rithm 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/opera-

tions are standard or not, post it to Canvas Discussion Forum or drop us an email

at [email protected]

• Marks are given based on correctness, conciseness (with page limits), and clar-

ity of your answers. If the marker thinks that the answer is completely not under-

standable, 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 an-

swers 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 con-

trol. 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":

2

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)≤ cg(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

4n2+2n ∈Θ(n).

b) [1 mark] n100 ∈O(en).

c) [1 mark] loge(n2) ∈Ω(

p

n).

Problem 2 (3 marks - at most 2 sentences). Arrange the following functions in an in-

creasing order of their growth rates.

f1(n)= 1000n,

f2(n)= (logn)2,

f3(n)= n!,

f4(n)= n logn,

f5(n)= 2n.

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 num-

bers 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(n logm). 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.

3

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

simplicity.

a) [2 marks] Design an in-place recursive decrease-and-conquer algorithm (description

+ pseudo code) of complexity O(n2) 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

(ID1,F), (ID2,F), (ID3,M), (ID4,F), (ID5,M), (ID6,M), (ID7,F), (ID8,F),

then the output could be

(ID5,M), (ID7,F), (ID3,M), (ID8,F), (ID6,M), (ID1,F), (ID2,F), (ID4,F).

Note that inefficient algorithm, in particular, algorithms with complexity Ω(n3)

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?

4

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+

n2) 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.

5

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).

1. (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).

2. (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).

6

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

1 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).

7

Species DNA sequence

Beefalo AACTHJJTGG

Bearger TTHJJGTAT

Bunnyman AACTHJJGG

Buzzard CAAHGHTG

Catcoon AHCTHHJJTGG

Deerclops HJCTHJJGT

Dragonfly AHCTHHJGJTGGC

Elder Mandrake CATHJHTJGT

Eyeplant CTHJJGT

Grass Gekko CTJHJT

Hound JJHHJJTGH

Lavae AHHJGJTGGC

MacTusk HCTHJJTGGJH

Merm JHTHHJJTGA

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.

8

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 pre-

recorded 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 simi-

larity 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

improvement.

9

1 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 sub-

missions. 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 assess-

ment declaration - https://www.rmit.edu.au/students/student-essentials/ assessment-and-

exams/assessment/assessment-declaration

2 Plagiarism Policy

University Policy on Academic Honesty and Plagiarism: You are reminded that all sub-

mitted 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 permit-

ted, 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, please see the policy at

https://www.rmit.edu.au/students/student-essentials/assessment-and-results/

academic-integrity.

3 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 sugges-

tions leading to solutions.

10

欢迎咨询51作业君