nice video, you are a talented educator. using an intuitive analogy is obviously helpful. also i like the approach of working backwards through the solution because it makes it immediately obvious why every step is useful towards the big picture. working through the steps forwards would leave the student confused until the end, when they would need to piece together obscure details to make sense of it
I have read some implementation of this method. At first, you have to classify the overfull and underfull buckets into a stack. Then when choosing the underfull and overfull buckets, you just need to take the most recent overfull and underfull buckets. In fact any randomly chosen overfull buckets and underfull buckets are satisfied since you only need to make sure to pour to make the underfull buckets to make it full. But I think that using stacks are convenient.
the algorithm works regardless of how they are selected. pick them however it's the most convenient, probably by iterating in order. if buckets are already pre-sorted, there is an optimization to minimize the number of pours. you can pour from the most full bucket into the least full bucket. being sorted also simplifies the process of identifying which ones are overfull vs underfull. you just move towards the center from the two edges. in general, these optimizations do not justify the cost of sorting, but in practice, it may be justified in some cases.
nice video, you are a talented educator. using an intuitive analogy is obviously helpful. also i like the approach of working backwards through the solution because it makes it immediately obvious why every step is useful towards the big picture. working through the steps forwards would leave the student confused until the end, when they would need to piece together obscure details to make sense of it
Thank you, I finally understand this nice piece of algorithm! :)
so rad. thank you
Very helpful, thank you! Now I just need to generate some numbers :)
Thanks mate
very pedagogical. too bad you did not explain which method to use to choose the underfull bucket and overfull one. thanks.
I think the underfull and overfull buckets are chosen randomly.
I have read some implementation of this method. At first, you have to classify the overfull and underfull buckets into a stack. Then when choosing the underfull and overfull buckets, you just need to take the most recent overfull and underfull buckets. In fact any randomly chosen overfull buckets and underfull buckets are satisfied since you only need to make sure to pour to make the underfull buckets to make it full. But I think that using stacks are convenient.
the algorithm works regardless of how they are selected. pick them however it's the most convenient, probably by iterating in order.
if buckets are already pre-sorted, there is an optimization to minimize the number of pours. you can pour from the most full bucket into the least full bucket. being sorted also simplifies the process of identifying which ones are overfull vs underfull. you just move towards the center from the two edges. in general, these optimizations do not justify the cost of sorting, but in practice, it may be justified in some cases.