ADS_midterm
2-1
分数 5
作者 Yuchen Mao
单位 浙江大学

Consider an ordinary binary min-heap that supports INSERTION and DELETEMIN only. For each key xx in the heap, denote its depth by d(x)d(x). We assume that the depth of the root is 11. We define a potential function

Φ(D)=cxDd(x)\Phi(D) = c\cdot \sum_{x \in D}d(x),

where cc 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.


2-2
分数 5
作者 Yuchen Mao
单位 浙江大学

Delete the minimum number from the binomial queue given in the following figure. Which one of the following statements must be FALSE?

binomial_heap.png


2-3
分数 5
作者 Yuchen Mao
单位 浙江大学

Gvien the following table, what are the precision and the recall?

Relevant Irrelevant
Retrieved 1000 3000
Not Retrieved 7000 21000

2-4
分数 5
作者 Yuchen Mao
单位 浙江大学

Consider the following game tree. If node dd is pruned by α\alpha-β\beta pruning algorithm, which of the following statements about the value of node aa or node bb must be correct?

a-b剪枝(2)-1.jpg


2-5
分数 5
作者 Yuchen Mao
单位 浙江大学

Consider the following symbol frequencies for a five-symbol alphabet:

Symbol Frequency
A 0.32
B 0.25
C 0.20
D 0.18
E 0.05

What is the average encoding length of an optimal prefix code?


2-6
分数 5
作者 Yuchen Mao
单位 浙江大学

Consider the following pseudo-code.

strange(a1,,ana_1, \ldots, a_n):
1.1.\,\,if n2022n \leq 2022 then return
2.2.\,\,strange(an/4+1,,a3n/8a_{\lfloor n/4 + 1 \rfloor}, \ldots, a_{\lfloor 3n/8 \rfloor})
3.3.\,\,for i=1i = 1 to nn:
4.4.\quadprint(aia_i)
5.5.\,\,strange(a3n/4+1,,ana_{\lfloor 3n/4 + 1 \rfloor}, \ldots, a_n)

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 nn is a power of 2.)