# math代写|算法代写|algorithm代写 – CSCB63 Assignment 1

math代写|算法代写|algorithm代写:这是一个有一定难度的cs方面的算法设计代写题目
1. (a) [5 marks] Let f and g be functions such that f(n) ≥ 1 and lg(g(n)) ≥ 1 for all natural n.
Prove: If f(n) ∈ O(g(n)), then lg(f(n)) ∈ O(lg(g(n))).
(b) [5 marks] Give an example of functions f and g such that f(n) > 0 and g(n) > 0 for all natural
n, and f(n) ∈ O(g(n)), but lg(f(n)) ∈ O/ (lg(g(n))).
Prove that your example satisfies the claims.
2. (a) [4 marks] Create two AVL trees. Insert keys
25, 10, 11, 20, 28, 9
in that order to construct T1 and
14, 31, 22, 18, 13, 16
in that order to construct T2. You will be graded on whether your tree matches the solution tree.
(b) [4 marks] Trace through the union algorithm given in class to construct the tree T = T1 ∪ T2
or union(T1, T2). You should show your steps to show how you construct T clearly indicating
where you are performing a split and on which value, a recursive union call or a
merge/join call.
3. [10 marks] An arena has a number of rows with seats that can be sold for an event. Each row has a
row number r and a number of remaining available seats s. Design a data structure that stores the
rows for an event as a pair (r, s) and supports efficient implementation of the four operations:
INSERT(r, s): A new row with row number r and seats available s is available for this event.
Insert the row into the data structure.
DELETE(r, s): Delete the row with row number r and seats available s.
BESTAVAILABLE(s): Find a row that has at least s seats available such that the row number r is
the minimum over all rows with at least s seats available. More formally, return the row ri from
the pair (ri