Consider an ordinary binary min-heap that supports INSERTION and DELETEMIN only. For each key xxx in the heap, denote its depth by d(x)d(x)d(x). We assume that the depth of the root is 111. We define a potential function
Φ(D)=c⋅∑x∈Dd(x)\Phi(D) = c\cdot \sum_{x \in D}d(x)Φ(D)=c⋅∑x∈Dd(x),
where ccc is a constant that is sufficiently large. That is, the potential of a heap is proportional to the sum of the depths of the keys stored in it. Using this potential function Φ\PhiΦ, what are the amortized costs of INSERTION and DELETEMIN? Your bounds should be as tight as possible.
O(logn)O(\log n)O(logn) for INSERTION and O(logn)O(\log n)O(logn) for DELETEMIN
O(1)O(1)O(1) for INSERTION and O(logn)O(\log n)O(logn) for DELETEMIN
O(logn)O(\log n)O(logn) for INSERTION and O(1)O(1)O(1) for DELETEMIN
O(n)O(n)O(n) for INSERTION and O(n)O(n)O(n) for DELETEMIN
Delete the minimum number from the binomial queue given in the following figure. Which one of the following statements must be FALSE?
there are two binomial trees after deletion, which are B2B_2B2 and B3B_3B3
23 and 14 are both the roots of some binomial trees
21 is the child of 13
23 and 24 are siblings
Gvien the following table, what are the precision and the recall?
precision = 25% and recall = 12.5%
precision = 12.5% and recall = 25%
precision = 33.3% and recall = 14.3%
precision = 14.3% and recall = 33.3%
Consider the following game tree. If node ddd is pruned by α\alphaα-β\betaβ pruning algorithm, which of the following statements about the value of node aaa or node bbb must be correct?
both are greater than or equal to 68
both are less than or equal to 68
exactly one of them is greater than 68
exactly one of them is less than 68
Consider the following symbol frequencies for a five-symbol alphabet:
What is the average encoding length of an optimal prefix code?
2.23
2.31
2.49
2.50
Consider the following pseudo-code.
strange(a1,…,ana_1, \ldots, a_na1,…,an):1. 1.\,\,1.if n≤2022n \leq 2022n≤2022 then return2. 2.\,\,2.strange(a⌊n/4+1⌋,…,a⌊3n/8⌋a_{\lfloor n/4 + 1 \rfloor}, \ldots, a_{\lfloor 3n/8 \rfloor}a⌊n/4+1⌋,…,a⌊3n/8⌋)3. 3.\,\,3.for i=1i = 1i=1 to nnn:4.4.\quad4.print(aia_iai)5. 5.\,\,5.strange(a⌊3n/4+1⌋,…,ana_{\lfloor 3n/4 + 1 \rfloor}, \ldots, a_na⌊3n/4+1⌋,…,an)
What is the running time of this pseudo-code? Your answer should be as tight as possible. (Hint: give a recurrence for this pseudocode and solve the recurrence with the method of your choice. You may assume nnn is a power of 2.)
O(1)O(1)O(1)
O(logn)O(\log n)O(logn)
O(n)O(n)O(n)
O(nlogn)O(n \log n)O(nlogn)