Hey all - I apologize for the (extremely) long period of no updates, I've been prioritizing other things. I've been accepted this Fall to begin my Ph.D. at University of California, Berkeley. Since I won't be at Microsoft any longer, I've started a new...

We're entering an era where CPU clock speeds will soon cease to scale upwards and instead CPU manufacturers are planning to put more and more independent cores on a chip. Intel plans to release an 80-core chip within 5 years . Consequently the research...

Most computer scientists are familiar with the P = NP problem, which asks essentially whether we can verify more problems in polynomial time than we can solve. So fundamentally does complexity theory hinge on this result that the Clay Mathematics Institute...

In most data structure and algorithms classes, the model used for basic analysis is the traditional RAM model: we assume that we have a large, random-access array of memory, and count the number of simple reads/writes needed to perform the algorithm....

I apologize to everyone for the hiatus - I realise a post is more than a little overdue and will try to be more regular in the future. I appreciate the support that I've received for the blog and continuing it. Consider the following problem: you're...

One of the benefits of functional languages is their great flexibility in list manipulation, which enables them to express certain computations concisely that would require one or more verbose loops in procedural languages. Many of the features that functional...

Today I'm going to talk about how the quadratic sieve factoring algorithm works, giving a comprehensive description assuming knowledge of only basic university-level mathematics. The foundation of the most popular public-key cryptography algorithm...

If you've ever done work with Web graphics, I'm sure that at some point you reduced an image with thousands of colors, such as a screenshot or photograph, to an image with only 256 colors, for example to store the image in the GIF format. Remarkably,...

JPEG is an image encoding designed to compress photographs and similar images effectively, often 5 to 15 times over a raw bitmap format. It's a lossy format that exploits properties of human vision to eliminate information that is difficult to distinguish...

This article will discuss effective use of types to catch some common problems at compile time not normally found by the typechecker. The typechecker is the most important tool in the programmer's arsenal. Types enable you to structure code in a more...

Hi everybody. This is a short post, but I just wanted to tell you all about a new wiki I created called LiteratePrograms , based on an extension of the same MediaWiki software used by Wikipedia . Some of you read my earlier post about literate programming...

Happy Valentine's Day, everyone! Today I'm going to talk about the important problem of successfully tracking dependencies in builds in an automatic manner. In short, there are two kinds of build systems: the ones where all dependencies are tracked...

If asked what they do, some developers might say "I write code" or "I program computers". But more fundamentally, what is computing really about? After all, Euclid's algorithm for computing the greatest common denominator of two numbers in polynomial...

Literate programming , invented in 1981 by the same Donald Knuth who wrote The Art of Computer Programming and the document language TeX, is a technique in which a program is written as a human-oriented document interspersing discussion and code. The...

Most people who have studied algorithms remember quicksort, the ubiquitous sorting algorithm available in the standard library of nearly every programming language implementation in existence, including C, C++, Java, and the .NET Framework. Quicksort...

Today I'm going to discuss a few clever algorithms for dividing values by constant values known at compile-time, without the use of the division instruction. In compiler optimization theory, the basic problem we attempt to solve is to create algorithms...

Sorry for the long hiatus, everyone. Today I'm going to talk about succinct data structures, which are informally data structures that use very close to the absolute minimum possible space. This material is largely based on lectures by MIT professor Erik...

When learning to program in a functional language such as Lisp, Ocaml , or Haskell , one of the most difficult aspects of the paradigmic shift is that data in these languages is almost entirely immutable, or read-only. In purely functional programs, there...

Software transactional memory ( STM ) is a scheme for concurrent programming with multiple threads that uses transactions similar to those used in databases. Today I'll discuss what STM is, how it works, some implementations, and why you should care....

If you write programs in C, C++, Java, or C#, you've gotten used to having the null value around. The null value is a special reserved reference (or pointer) value indicating that a reference does not refer to any object. It's useful for constructing...

One of the most difficult problems in cryptographic key management is keeping a secret key safe from both compromise and loss. If you don't make enough backups, the key might be destroyed in a hardware failure or natural disaster. But if any backup...

I'm a fervent fan of using code generator tools wherever possible to make your life easier. Although they come with issues related to effective building, diagnostics, and debugging, the amount of value they add to your application is immense: they can...

Number theory is, roughly speaking, the study of properties of integers. Often a problem which is easy for real numbers, such as factoring or linear programming, seems to be considerably more difficult when restricted to integers (in fact, integer...

Computational geometry is a field that studies efficient solution of geometric problems, which are critical in mapping, manufacturing, and particularly graphics applications. If you find data structures and algorithms interesting, it's likely you'd also...

Today I'll talk about multiple dispatch, a programming language feature that increases flexibility of method calls and eliminates the need for awkward pattern constructions, at the cost of some additional complexity in the dispatch algorithm. The Visitor...