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
, si) where si ≥ s ∧ ∀k(sk ≥ s → ri < rk ∨ i = k) if it exists and null otherwise.
SELL(x, r): Sell x seats for the event for row number r with s seats available. This means that
the new number of seats available for row r should be decreased to s − x. You may assume that
s ≥ x.
Each of the above operations must run in O(log n) time. You should explain what your data structure
is and how it is implemented by giving detailed descriptions (or pseudocode) for each of the above
operations.
4. [12 marks] Implement an algorithm for determining whether two AVL trees (storing ordered sets—just
keys) are equal in the set-theory sense—they store the same keys (but may have different tree shapes).
The starter code and the test program are on Blackboard: AVL.java, Node.java, and Run.java. You
will add your code to only AVL.java and submit it. Do not submit any other Java files—they will be
ignored. (To add your own classes, make them inner classes of AVL.)
1
Package declaration Some of you use IDEs that require package names. So let’s all use the same
one. All files declare “package avl;”. Please try not to change it. We are about 200 students altogether,
and it would be impractical to cater for 200 variations.
If you use the command line instead of an IDE (I confess I’m primitive and I still do this), the package
declaration means that you need to put the files under subdirectory avl. Then there are several ways
to compile and run. Here is one: outside avl,
javac avl/*.java
java avl.Run
There are other ways. What works for you is good.
How you can test If compilation is successful, you can use “java avl.Run” or IDE equivalents to run
my test program. This runs all tests sequentially, but aborts at the first failure. Failures are represented
by exceptions with error messages.
You can use “java avl.Run 0” to run just test #0, for example. See also the “main” method and its
comment in the file.
Marking scheme If your code looks like a general algorithm (as opposed to customizing for my
test cases) that takes O(m + n) worst-case time, where m and n are the tree sizes with m ≤ n, you
get 3 marks to start. If your algorithm takes O(m lg( n
m + 1)) worst-case time, you get 3 more marks.
In addition:
• If your code compiles: 1 more mark per test passed. But watch these requirments:
I will compile with these strict options, which mean that any unsafe type cast (which you don’t
need for this task) is considered a hard error:
javac -Xlint:unchecked -Werror avl/AVL.java
I will give each test case 1 second only on the Mathlab server. Timing out is a failure. Each test
case is timed separately. My tests are small, so taking more than 1 second is a clear sign of some
circular problem.
• If your code does not compile in the sense above: 0 more marks.
If your code does not look like a general algorithm that takes O(m +n) worst-case time, 0 to 3 marks
depending on how far off it is. Examples: m lg n /∈ O(m+n); a hash-table approach takes Ω(m×n)
time.
Total: 40 marks
2