View Single Post
  #1 (permalink)  
Old June 5th, 2014, 10:14 AM
Rod Stephens's Avatar
Rod Stephens Rod Stephens is offline
Wrox Author
Points: 3,187, Level: 23
Points: 3,187, Level: 23 Points: 3,187, Level: 23 Points: 3,187, Level: 23
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
Join Date: Jan 2006
Location: , , .
Posts: 646
Thanks: 2
Thanked 96 Times in 95 Posts
Default Correction on page 32

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!
Attached Images
File Type: png Equation.png (1.5 KB, 2 views)

Rod Stephens, Microsoft MVP

Essential Algorithms: A Practical Approach to Computer Algorithms

(Please post reviews at Amazon or wherever you shop!)
Reply With Quote