Closed justinmeiners closed 2 years ago
@aharrison24 Here is an initial pass which mostly fixes typos and footnotes with your recommendations. I am still working on the larger reorg!
Please bring them up if you think things should be different. I think everything we talked about, but I did remove some details from the Dirichlet proof footnote.
I've gone ahead and read chapter 11 and had a good think about the algorithm. I think I have a reasonable understanding of what's going on now. There are certainly some things I would have appreciated knowing sooner. I've mentioned most of them in my in-line comments.
A couple of minor extra things: In the add_to_counter
algorithm it would be helpful to clarify that carry
is the element to be inserted and op
is a binary operation such as min
or max
that returns one of its two inputs.
I also think it would be very valuable to have a slightly extended example of how the counter works, where multiple elements are inserted. You could do an example where the elements are characters and the binary operator is min
, for instance. 'zero' could be a space character. You could push in 8 letters in an order that causes multiple slots to be occupied at the end. You can use that to show that the counter only needs log2(8) = 3
slots. You can also show that after all the elements have been inserted, the job isn't yet finished. This justifies the need for the reduce_counter
operation, which performs all the remaining comparisons to get to a single 'winner'. I think that's important, because with the text as it is currently, the reduction step is never really justified. It's just presented as something that is necessary.
I also realised that nowhere is it explicitly stated that the counter starts out empty and has elements pushed in to it one at a time.
I just finished the "big" revision and I think I have been able to address most of your comments. I went back to the videos to review this section and found some helpful comments I missed which address many of your concerns.
I have added comments to this code here indicating specific resolutions to concerns. Once again, I really appreciate you working through this with me.
it would be very valuable to have a slightly extended example of how the counter works
I think that's a great idea, and added it to issue #48 .
I have resolved those comments you left. I am going to merge this in for now as it is a significant improvement. Let's start a new PR for additional fixes if needed. (I will review your issue again.)