算法代写 | COSC 2123/1285 Assignment 2: Algorithm Design & Complexity Analysis

本次澳洲代写主要为算法结构相关的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 definitions 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 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!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 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(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
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?

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


blank

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

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


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

blank

发表评论