Graph Theory37 sections · 1633 units
Open in Course

Quiz: Binary Lifting Recurrence

Knowledge check

Check Your Understanding

The recurrence up[v][k] = up[up[v][k-1]][k-1] computes the 2k2^k-th ancestor. Why is this correct?

  1. A.It adds 2k12^{k-1} twice, which equals 2k2^k
  2. B.It multiplies the jump distance by 22 each level
  3. C.It jumps 2k12^{k-1} steps from vv, then another 2k12^{k-1} from where you land
  4. D.It looks up the kk-th entry in the parent's row
Start the roadmap to answer the quizzes and solve the challenges