I’ve recently come across an interesting article detailing an existing bug in the binary search implementation presented in Programming Pearls (Addison-Wesley, 1986; Second Edition, 2000). The article can be found here and it presents a bug that can easily be overlooked. Many of us may be very familiar with the problem and many a times we notice it, but easily disregard it because we say that it cannot occur in practice. The nice thing about this bug is that if the program would have been described in pseudocode, the bug would not be there. I really advise you to read the article… it presents how the bug was discovered and what was the impact.
(more…)
Some time ago I wrote a post showing how to implement a generic binary search tree data structure in C#. In today’s post I will provide a way of extending the binary data structure in order to be able to use LINQ in order to query it. In order to be able to use LINQ over a custom data structure, all that we have to extend our data structure such that it implements the IEnumerable<T> interface. This is due to the fact that LINQ provides a set of extension methods that extend the functionality of types inheriting from IEnumerable<T>.
(more…)
It has been a long while since I actually got to implement some tree data structures, and in order not to get rusty, I’ve decided to try to create a simple Binary Search Tree in C#. My main goals for this piece of code was to create a BST in one of the most general ways possible. This being said, I’ve decided to use generic classes to define the
(more…)
A few years ago I came across an interesting problem: Two players play the following game: there are n sticks on a table. The first player begins by removing an arbitrary number of sticks, except that he is not allowed to remove all of them in the first move. Next, every player takes one or more sticks, but not more than twice as many as the preceding player has taken with his last move. The player who removes the last stick wins. The question is which is the best move for the first player, if initially there are 1000 sticks in the game? (more…)