![[topimage]](IMADA_en.png)
Exercises
- CLRS Exercise 32.3-2. However, use the pattern given in Exercise 32.4-1.
- CLRS Exercise 32.4-1. Compare with what you got in Exercise 32.3-2.
- CLRS Exercise 32.4-3.
- CLRS Exercise 32.4-5. Think of the whole while-loop as an operation, update_q. Prove that operation update_q is amortized constant time.
- CLRS Exercise 32.4-6.
- CLRS Exercise 32.4-7.
- CLRS Exercise 32.4-8. The hint follows from our discussions at the lecture, where we proved that \( \delta(q,a) \) could be computed by following the chain defined by the \( \pi \) function. And the hint just says that we end up the same place if we take just one step along the chain and then continues recursively from there. Thus, just assume that the hint is true and now solve the exercise.