Algorithms

Igor Ostrovsky on September 9th, 2009

Not many developers have the insights of Michael Abrash. He is a game developer with decades of experience building commercial games, including a game you may recognize as "Quake". His Graphics Programming Black Book is years old, but much of it is just as interesting as it was at the time of writing. And, the […]

Continue reading about Program like a Quake developer

Igor Ostrovsky on August 30th, 2009

Over the past couple of years, auto-complete has popped up all over the web. Facebook, YouTube, Google, Bing, MSDN, LinkedIn and lots of other websites all try to complete your phrase as soon as you start typing. Auto-complete definitely makes for a nice user experience, but it can be a challenge to implement efficiently. In […]

Continue reading about Efficient auto-complete with a ternary search tree

Igor Ostrovsky on April 1st, 2009

Notice that this post was published on April 1, 2009. For decades, computer science students have been taught that so-called NP-hard problems do not have known efficient solutions. These problems include the infamous Travelling salesman problem, subset sum, 3SAT, and many more. But – as is often the case – where theoretical Computer Science failed, […]

Continue reading about Choose expression: proposal for a revolutionary C# construct

Igor Ostrovsky on August 29th, 2008

This article is the first one in a series titled Data structure zoo. Each article will give you a “working knowledge” of data structures that solve a particular problem. You won’t necessarily know how to implement each one, but you will have a good idea of the main characteristics of each solution and how to […]

Continue reading about Data structure zoo: ordered set

Igor Ostrovsky on July 21st, 2008

Skip lists are a fascinating data structure: very simple, and yet have the same asymptotic efficiency as much more complicated AVL trees and red-black trees. While many standard libraries for various programming languages provide a sorted set data structure, there are numerous problems that require more control over the internal data structure than a sorted […]

Continue reading about Skip lists are fascinating!

Igor Ostrovsky on May 9th, 2008

The folks at Dev 102 posted a programming job interview challenge. It is rather easy, but I figured that it may be a nice change of pace, since my last posting was fairly involved. The challenge is to reverse the bits in each byte, given a large array of bytes. What is the fastest possible […]

Continue reading about Programming job interview challenge

Igor Ostrovsky on May 4th, 2008

What is the time complexity of quicksort? The answer that first pops up in my head is O(N logN). That answer is only partly right: the worst case is in fact O(N2). However, since very few inputs take anywhere that long, a reasonable quicksort implementation will almost never encounter the quadratic case in real life. […]

Continue reading about Quicksort killer