Add Me!Close Menu Navigation

From fighting crime and arresting pirates to blasting away zombies, you can always count on a superhero. Unfortunately, I am definitely not that person.

Add Me!Open Categories Menu

Currently Browsing

December, 2013

29 December

Counting Binary Trees (The Hard Way)

In this post, we prove the closed form of a nonlinear recurrence corresponding to the count of binary trees with n nodes.

28 December

Calculating Modified Fibonacci Numbers, Quickly and Exactly

This is inspired by an article of similar name called Calculating Fibonacci Numbers, Quickly and Exactly. Consider the a modified fibonacci sequence given by the recurrence c_0 = 2, c_1 = 1, c_k = c_{k-1} + c_{k-2}. We shall look at various algebraic and analytic properties of this sequence, find two algorithms that computes c_k in O(\log(k)) time, and finally look at a motivating example where we need to compute this sequence quickly and exactly.