Suppose you've got a huge graph - millions of nodes. And you know that it's not connected - so the graph actually consists of some number of pieces (called the connected components of the graph). And there are constantly...
Read on »
Posted on September 6, 2007 11:40 AM • 12 Comments •
There are a lot of very cool problems in computer science that can be solved by using an appropriate data structure; and the data structures are often easiest to describe in terms of graphs. And of those data structures,...
Read on »
Posted on September 3, 2007 8:53 PM • 13 Comments •
For the basics, I wrote a bunch of stuff about sorting. It seems worth taking a moment to talk about something related: binary search. Binary search is one of the most important and fundamental algorithms, and it shows up...
Read on »
Posted on April 7, 2007 12:08 PM • 14 Comments •
Multiple people have written to me, after seeing yesterday's algorithms basics post, asking me to say more about sorting algorithms. I have to say that it's not my favorite topic - sorting is one of those old bugaboos that...
Read on »
Posted on February 28, 2007 3:30 PM • 51 Comments •
What started me on this whole complexity theory series was a question in the comments about the difference between quantum computers and classical computers. Taking the broadest possible view, in theory, a quantum computer is a kind of non-deterministic...
Read on »
Posted on January 16, 2007 11:08 AM • 19 Comments •
As I've mentioned in the past, complexity theory isn't really one of my favorite topics. As a professional computer scientist, knowing and loving complexity up to the level of NP-completeness is practically a requirement. But once you start to...
Read on »
Posted on January 9, 2007 4:16 PM • 31 Comments •
Now that we've gone through a very basic introduction to computational complexity, we're ready to take a high-level glimpse at some of the more interesting things that arise from it. The one that you'll hear about most often is...
Read on »
Posted on January 8, 2007 3:45 PM • 30 Comments •
