Algorithms and Data Structures
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP20003 Algorithms and Data Structures
Time Limit: 45 Minutes
This paper has three questions. Answer all questions on the test paper on the printed side
only. You may use the facing page for your own notes if you wish, but it will not be marked
unless you clearly indicate this as your wish.
There are extra blank pages at the end of the paper.
Marks are shown out of 10, and this paper counts for 10% of your final grade. You are
permitted to use pencil.
This exam contains 14 pages (including this cover page) and 8 questions.
Please do not open this test until instructed to do so.
Grade Table (for teacher use only)
Question Points Score
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 3
Total: 10
COMP20003 Algorithms and Data Structures Midterm - Page 2 of 14
Computational Complexity (2 marks)
1. (1 point) Given the following functions f(n) and g(n), is f in O(g(n)) or is f in Θ(g(n)),
or both? If true, specify a constant c and point n0, if false, briefly specify why.
(a) (1/3 points) f(n) = 2n, g(n) = 22n.
(b) (1/3 points) f(n) = n!, g(n) = 2n.
(c) (1/3 points) f(n) =
∑n
i=1 i
k, g(n) = nk.
2. (1 point) Consider f(n) = 1 + c+ c2 + . . .+ cn where c is a positive real number, and a
function g(n) which satisfies f(n) ∈ Θ(g(n)):
(a) (1/3 points) if c < 1, then g(n) =?.
(b) (1/3 points) if c = 1, then g(n) =?.
COMP20003 Algorithms and Data Structures Midterm - Page 3 of 14
(c) (1/3 points) if c > 1, then g(n) =?.
COMP20003 Algorithms and Data Structures Midterm - Page 4 of 14
Searching and Sorting (5 marks)
Briefly and clearly answer each of the following questions.