wojtask
Incorrect solution for Exercise 5.4-4
Mutual independence is required for exact calculation, because it assumes that the sample space is uniformly distributed (any sequence of k birthdays should be equally likely with probability $\frac 1 {n^k}$). Pairwise independence is enough for the approximate technique using indicator random variables. All of this is nicely explained here (see section 6.5).
Many thanks for reporting this error. I read the material in the book again very carefully, and have figured out where exactly the mututal independence is needed. The authors use slightly different method for calculating the probability than the one from the resource you linked, but the mututal independence requirement obviously stays.
In the current solution I mistakenly considered formula (5.7) on pages 140-141 a part of the main calculation. Formula (5.7) needs only pairwise independence, but its generalized version is used to obtain $\Pr\{A_k \mid B_{k-1}\} = (n-k+1)/n$ on page 141.
Let me fix that right away.
No problem, I am glad if I can contribute to your great work regarding this solutions guide.
FYI: When you decide to tackle Exercise 6.5-5 in the near future, note that it is not valid. I had notified prof. Tom Cormen about this issue and he agreed that line 5 in Max-Heap-Insert is redundant but will not going to change the text.
Thank you for the heads up about 6.5-5. It answers my concerns that I put in https://github.com/wojtask/clrs4e-solutions/issues/245#issuecomment-2692742103. When I will be tackling this exercise soon, I will put a clarification note instead of a solution.
I understand prof. Cormen's choice to not changing the text, because when they make a correction they try to perturb the pagination as little as possible. And this one is not a serious problem, just a redundancy.
I am facing some difficulties in fixing this using the narrative from the book. Let me revisit this error later. It is going to be fixed in time for release 0.3.