本次澳洲代写主要为算法结构相关的assignment

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 deﬁnitions of the big-O,

big-Omega, and big-Theta notations. For instance, to prove that f (n) 2 O(g(n)) or f (n) Ý

O(g(n)), using the deﬁnitions of big-O, we need to demonstrate the existence of a constant

c and a sufﬁcient 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!1 f (n)/g(n) Ç1

for f (n) 2 O(g(n)), or showing that limn!1 f (n)/g(n) Æ 1 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 2£(n).

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

c) [1 mark] loge(n2) 2(

pn).

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) Æ nlogn,

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 ﬁnd 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 ﬁnd 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 ﬁeld “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 inefﬁcient 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?

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 ﬁrst 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 Æ 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).

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** itcsdx@outlook.com **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。