Thursday, November 30, 2006

Update: Balbir's Blog: Problem 4.2 Page 85, Introduction to Algorithms

I posted an entry about a possible errata in Introduction to Algorithms at
Balbir's Blog: Problem 4.2 Page 85, Introduction to Algorithms

Well, it's a part of the errata of the book now. Check out http://www.cs.dartmouth.edu/~thc/clrs-2e-bugs/bugs.php the errata reads

Page 85, Problem 4-2. Change the second paragraph of the problem to read, ``Show that if the only way to access information in array A is by this single-bit operation, we can still determine the missing integer in O(n) time. Any entire integer outside of A is still accessible in a single operation.''
Reported by Balbir Singh. Posted 29 November 2006.
Severity level: 3
To be corrected in the eighth printing.
Severity level 3 is "A more significant technical or expository error"

I have not yet figured out how the new solution works (with the new constraint), if anybody else thinks of it, please do comment on it here.
Post a Comment