← All topics
Quiz: Recurrence Relations: questions with answers
10 questions, each with the answer and a short explanation.
Take the timed quiz + get a certificate →- Q1. What is the recurrence for the minimum number of Tower of Hanoi moves?
- Q2. How many binary strings of length 5 have no two consecutive 1s (from the demo)?
- Q3. What is the closed form of a(n) = 5a(n−1) − 6a(n−2) with a(0) = 1, a(1) = 4?
- Q4. By the Master Theorem, what is T(n) = 2T(n/2) + Θ(n)?
- Q5. What is T(n) = 8T(n/2) + Θ(n²)?
- Q6. The characteristic equation of aₙ = 4aₙ₋₁ − 4aₙ₋₂ has a repeated root 2. What is the general solution?
- Q7. Using Tₙ = Tₙ₋₁ + Tₙ₋₂ with T₁ = 1 and T₂ = 2, in how many ways can a 2×4 board be tiled with dominoes?
- Q8. What does this print? (code)
- Q9. Which recurrence describes binary search?
- Q10. By the Master Theorem, what is T(n) = 4T(n/2) + Θ(n)?