In CSC165, we started covering code efficiency (big Oh) and I see that two years ago, CSC148 also covered this by now (by virtue of looking at the midterm from then). So it’s pretty obvious that the efficiency of a data search relies not only on the search algorithm itself, but the data structure as well.

 

By sorting a binary search tree by value (__lt__ node on the left, __gt__ node on the right), we’re able to ignore up to half of the nodes on every single node traversal. Reminds me a bit of the ‘guess a number’ game where an optimal strategy is to eliminate half of the options with each guess. We’ve only used integers in our class examples, but it’s easy to see that this kind of data structure can be used for any type of data that can be subject to equality operators which could also include any abstract data types.

 

I was thinking that using something like this could be instrumental in speeding up the operation of the puzzle functions in our assignment. If I’m doing a peg-solitaire depth-first-search, to see if my extensions have been attempted before, I only need to look at already known positions with one peg less than my current position. So if I implemented an __eq__ method in PegSolitairePuzzle that just looked at number of pegs remaining, a slightly modified binary search tree that allows for “equal” data could be implemented and then the search of known positions could remain quick as the size of that data grows.

 

The __eq__ could be made more complex where we take 10^3 * numbers of pegs, and use the remaining digits to calculate something about the position of the pegs to sort them even better and be able to discard more irrelevant positions even quicker. I’m pretty excited and intimidated to learn about all these sorts of things in a future algorithms class!