COMP 3170 Department of Computer Science
Analysis of Algorithms and Data Structures University of Manitoba
Let’s Read A Paper – Extended Versions
Source. Pˇatra¸scu, Thorup. Time-Space Trade-Offs for Prdecessor Search. STOC’06, pp. 232-240.
2006.
In-Class Questions
1. Abstract. What is the main result in this paper?
2. Section 1.1. What is the cell probe model? Why does a lower bound in the cell probe model
imply a lower bound in the word RAM model?
3. Section 1.2.
(a) What are n, ℓ, and b?
(b) Why assume that lg(n) ≤ ℓ ≤ b?
(cid:110) lg(n)(cid:111) (cid:112)
(c) Show that min lg(ℓ), ≤ lg(n)
lg(ℓ)
4. Section 1.3
(a) For what values of x is lg(x) defined?
(b) What is a? What is the smallest possible value of a? What is S in terms of a and n?
(c) What is a polynomial universe? A superpolynomial universe?
(d) What is the difference between the third and fourth branches of expression (1)? Which
one is larger under what conditions?
(e) Why do branches three and four of expression (1) provide better lower bounds than
branch two when ℓ ∈ ω(lg(n))?
(f) Confirm the paper’s claim that with space n1+ϵ, the optimal complexity for a polynomial
universe is constant. Can you see how a constant time complexity could be achieved?
5. Section 2.
(a) Can you give high-level, qualitative descriptions of how Lemmas 1, 2, 3 and 4 are used
to prove Theorem 6?
(b) What does Theorem 6 imply about a data structure whose space is linear in n?
1
