Tutorial of Data Structures and Algorithms on 25/03/2019

Binomial trees and binomial heaps

Binomial trees are used for implementing priority queues, but I've just learned that they are also used for predicting stock prices. It means that there are niches where this topic is extremely relevant, although we don't fully understand how.

Notes from the board:

Someone asked if it was a coincidence that the number of child nodes of the root was equal to the degree of the binomial tree. No, it's not a coincidence. Remember from the slides that there is a property stating the number of nodes in each level of the tree. A good question is how to prove this particular property not only for the level 1 (child nodes of the root) but for every level. Hint: Try a proof by induction.

If you like this topic, you can dig deeper and read about its application into economics for predicting optimal stock prices. Research into this topic looks like this.

Finally, I will try to post weekly some questions on the topics seen in lectures and tutorials - questions that will resemble (not equal, obviously) those which will be in the final exam. So, stay tuned.