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

Algorithm

28 October

0x5f400000: Understanding Fast Inverse Sqrt the Easy(ish) Way!

In this post, we attempt to unravel the mysteries of the “magic” constant found in the fast inverse sqrt method in an intuitive fashion.

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.

15 October

Infinity Norm of the Inverse of Lower Bidiagonal Matrices

We consider the problem of efficiently computing the infinity norm of the inverse of a lower bidiagonal matrix L in linear time.

12 August
Posted in Algorithm, Article, Lua

Interval Scheduling Problem

Let’s consider the Interval Scheduling Problem, in which we have a set of n requests \{1,2,\cdots,n\}; the i^{th} request corresponds to an interval of time starting at s_i and finishing at f_i, or request $i$ spans interval $ [s_i,f_i]$. Suppose that a subset of the requests is compatible if no two of them overlap in time; find the largest compatible subset of any set of requests in a reasonable number of steps.