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]
b) [1 mark] n100 2O(en).
c) [1 mark] loge(n2) 2(
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)
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
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
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).
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: firstname.lastname@example.org 微信:itcsdx