Why Sorting is O(N log N)


Tags: , and

Any decent algorithms textbook will explain how fast sorting algorithms like quicksort and heapsort are, but it doesn’t take crazy maths to prove that they’re as asymptotically fast as you can possibly get.

Counting Sudoku Solution Grids using Monte Carlo


Tags: and

How many ways can you fill a 9x9 grid, obeying all the rules of the sudoku puzzle? The answer is too big to just calculate directly on a computer, so an exact answer takes careful analysis. But if an absolutely exact answer isn’t required, we can get a good statistical approximation using a Monte Carlo algorithm. As a bonus, the algorithm doesn’t need any application-specific analysis and works on many other problems, too. It’s a handy “stupid things that work” approach to solving problems.