math代写|算法代写|algorithm代写 : 典型的一个算法代写题目
1. [15 marks] Consider the following algorithm that computes the number of 1’s in a one-dimensional
array A that contains some number of 1’s (possibly none) followed by some number of 0’s (possibly
none).
The idea of the algorithm is to break up A into approximately √
n sections, each one of length approximately
√
n (where n = length(A)), and to perform the search in two phases: first look at the
last element in each section to determine the last section that contains 1’s, then look at each element
in that section to determine the position of the last 1 in A.
NUMOFONES(A) :
m ←
lp
length(A)
m
p ← m − 1
while p < length(A) and A[p] = 1 :
p ← p + m
p ← p − m + 1
while p < length(A) and A[p] = 1 :
p ← p + 1
return p
For each part of this question, measure complexity by counting the number of array accesses. To
simplify your analysis, assume that the length of A is a perfect square i.e., length(A) = m2
for some
m ∈ N.
(a) [5 marks] Perform a worst-case analysis of the NUMOFONES algorithm. Make sure you give a
tight bound not just an upper bound.
(b) [10 marks] Perform an average-case analysis of the NUMOFONES algorithm. Assume that A is
equally likely to contain any number of 1’s (anywhere from 0 to n = length(A)).
(HINT: Use indicator random variables. You do not have to simplify your final answer.)
2. [15 marks] Give an algorithm for the following problem. The input is a sequence of n numbers
{x1, x2, . . . , xn}, another sequence of n numbers {y1, y2, . . . , yn}, and a number z. Your algorithm
should determine whether or not z ∈ {xi + yj | 1 ≤ i, j ≤ n}. You should use universal hashing
families, and your algorithm should run in expected time O(n).
Provide justification that your algorithm is correct and runs in the required time. Be very clear about
which theorems from class and/or the text you are using, and how.
3. [15 marks] The following questions are for a B-tree with t = 2, ie, (2, 4) - trees.
(a) [5 marks] Suppose we want to insert the keys 1,2,...,n into a (2, 4) - tree. Would we get the same
tree no matter what order we do the insertions in? If not, what is the smallest value of n for
which the order of insertions makes a difference. Justify your answer.
1
(b) [10 marks] Suppose the keys 1,2,...,63 are stored in a “full” (2, 4) - tree of height 3. This means
that all internal nodes are 4-nodes and there are 21 of them.
i. What is the maximum number, M, of deletions you can perform while maintaining the
height of the tree at 3? Justify your answer by explaining how M deletions can be performed
and no more than M deletions can be performed.
ii. What is the minimum number, m, of deletions required to decrease the height of the original
tree to 2? Justify your answer by explaining how m deletions are sufficient and no less than
m deletions are enough.
2