p2p.wrox.com Forums

p2p.wrox.com Forums (http://p2p.wrox.com/index.php)
-   BOOK: Essential Algorithms: A Practical Approach to Computer Algorithms (http://p2p.wrox.com/forumdisplay.php?f=744)
-   -   Correction on page 32 (http://p2p.wrox.com/showthread.php?t=93032)

Rod Stephens June 5th, 2014 10:14 AM

Correction on page 32
1 Attachment(s)
Dipanjan said:


The example is on Page 32 heading is “A Fairly Random Array” , the final equation that comes up is given as : (N-1/N)*(N-2/N-1)* ….(N-(K-1)/N-(k-1)+1)* (N-1/(N-(K-1))

The expression marked in RED seems to be incorrect where it should be [1/N-(K-1)] as an expression for Pk.
This is correct. The final term Pk is the probability of an item ending up in position k given that it was not placed in positions 1, 2, ..., k - 1. After placing items in the first k - 1 positions, there are N - (k - 1) positions remaining, so the probability of the item being placed in any of the remaining positions is 1 over that number or 1/[N - (k - 1)].

See the attachment for a nicely formatted version of the equation.

Thanks for pointing this out Dipanjan!

All times are GMT -4. The time now is 11:02 PM.

Powered by vBulletin®
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
© 2013 John Wiley & Sons, Inc.