jeffgerickson / algorithms

Bug-tracking for Jeff's algorithms book, notes, etc.
7.92k stars 1.02k forks source link

[Oops.] Lecture Notes, Director's Cut, Adversary Argument #270

Open shestakov-sa opened 1 year ago

shestakov-sa commented 1 year ago

Chapter number or note title: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/13-adversary.pdf

Page number: Pages 6-7, Exercise 1

Error description: Part c) bit pattern 11 is evasive iff n mod 3 = 1 -- it is incorrect, n=1 is not evasive, n=2 is evasive, n=3 is evasive, n=4 is not.

Suggested fix (if any): bit pattern 11 is not evasive iff n mod 3 = 1

Page number: Pages 2-3

Error description: Indices are messy -- r-l-1 is an even number, not r-l

Suggested fix (if any): Invariant is r-l-1