Mark Chu-Carroll is a Computer Scientist working as a researcher in a corporate lab. My professional interests run towards how to build programming languages and tools that allow groups of people to work together to build large software systems.
goodmath
Posts by this author
September 6, 2007
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 new vertices and edges being added to the graph, but nothing is ever removed…
September 3, 2007
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, one thing that often comes up is amortized algorithmic complexity. Amortized…
September 2, 2007
I've now uploaded nearly all of the Yellowstone pictures. There are two additional
photo albums on Picasa: one for the Mammoth Hot Springs area, and one for the Yellowstone canyon. Here are the links:
Yellowstone Vacation, Mammoth Hot Springs area
Yellowstone Vacation, Canyon Area
September 1, 2007
I'm back from vacation! There was no network access in Yellowstone, and virtually no cellphone service.
Anyway, a bunch of people asked me to post photos. I've got three sets of photographs, for the three main areas of the park that I visited: the Geyser area, the Terrace area, and the Canyon…
August 24, 2007
Bright and early tomorrow morning, I'm leaving on vacation. I'll be spending the week in
Yellowstone National Park. I'm not sure what the network situation is there, but I'm not expecting much. Unfortunately, this year I didn't have time to prepare some reruns of old posts before I left.
If I…
August 24, 2007
The next interesting variant on graphs is directed graphs, or digraphs for
short. A digraph is a graph where each edge distinguished between its source and its target - so an edge is from one node, and to another node. Unlike a simple graph, where if A is adjacent to B, then you can follow the…
August 22, 2007
Aside from the Mandelbrot set, the most famous fractals are the Julia sets. You've almost definitely seen images of the Julias (like the ones scattered through this post), but what you might not have realized is just how closely related the Julia sets are to the Mandelbrot set.
Remember what the…
August 21, 2007
A bunch of readers, and one commenter in another thread, have all hit me with a pathetic
monstrosity of a purported proof of God. Several have even been misled by the URL where the
dreadful thing is posted, thinking that ScienceBlogs have picked up a creationist. Rest assured, this bozo and his…
August 19, 2007
This weekend, Seed Media, our benevolent and beloved corporate overlords, sponsored a Scibling gathering: ScienceBloggers from all over the country (and outside) all gathered in New York, ate, drank, and partied.
It made for quite an interesting weekend. I didn't end up being able to hang around…
August 17, 2007
Sonic Youth, "Or": Very smooth for SY. But great. They're an amazing band.
The Flower Kings, "Blue Planet": A typical track from one of my favorite neo-progressive
rock bands. For the Flower Kings, this is a short one at only 10 minutes.
The Clogs, "Lantern": once again, one of my favorite…
August 16, 2007
My friend and blog-father Orac sent me a truly delectable piece of bad math today. It's just
astonishing: a supposed mathematical model for why homeopathic dilution works, and for why the
standard dilutions are correct. It's called "The octave potencies convention: a mathematical model of dilution…
August 16, 2007
This post is quite thoroughly off-topic for this blog. But as someone who is openly religious and who
has written a number of posts that criticize Christian institutions, I get a fair bit of mail from cretins
who make demands that I speak up to defend their pathetic insistence that all religious…
August 15, 2007
One of the reasons that I like about graph theory so much is because of
how it ties into computer science. Graphs are fundamental to many problems in
computer science, and a lot of the work in graph theory has direct implications for
algorithm design. It also has a lot of resonance for me, because…
August 13, 2007
One amusing thing in graph theory is graph traversal. Many of the interesting algorithms on graph
are ultimately based on the idea of iterating through the nodes of the graph in some order that is
related to the structure of the graph.
There are two fundamental orders of graph traversal, known as…
August 12, 2007
Despite having written about it before, I still get a lot of questions about William Dembski's "No Free Lunch"
(NFL) theorems. One message recently contained the question in a particularly interesting form, so I thought I'd take
the opportunity to answer it with a post.
Here's the question I…
August 10, 2007
Another really fun and fundamental weighted graph problem is the shortest path problem. The
question in: given a connected weighted graph G, what is the shortest path between two vertices
v and w in G?
To be precise, the weight of a path is just the sum of the weight of the edges that make up
the…
August 8, 2007
Once upon a time, I wrote about a jackass who was criticizing his college math instructor, because the instructor couldn't explain what made the calculus class christian, or why it was different from what would be taught in a math class at a secular college.
That kind of thinking is quite strong…
August 8, 2007
One of the most fundamental properties of fractals that we've mostly avoided so far is the idea of dimension. I mentioned that one of the basic properties of fractals is that their Hausdorff dimension is
larger than their simple topological dimension. But so far, I haven't explained how to figure…
August 7, 2007
I got started on this series about graph theory by writing a post debunking something foolish that George Gilder said about network theory. Today I'm going to talk about one of the classic problems in graph theory, which happens to be a network problem. It's called the maximum flow problem.
The…
August 6, 2007
So, in my last post, I promised to explain how the chaos game is is an attractor for the Sierpinski triangle. It's actually pretty simple. First, though, we'll introduce the idea of an affine transformation. Affine transformations aren't strictly necessary for understanding the Chaos game, but…
August 6, 2007
There's one piece of bad math that I've encountered relatively frequently in conversations. It's
incredibly frustrating to me, because it's just so crazy - but the way we teach math and physics, far to many people just don't have enough of a clue to see how foolish it really is.
This comes up…
August 3, 2007
Most of the fractals that I've written about so far - including all of the L-system fractals - are
examples of something called iterated function systems. Speaking informally, an iterated function
system is one where you have a transformation function which you apply repeatedly. Most iterated…
August 1, 2007
As I alluded to yesterday, there's an analogue of L-systems for things more complicated than curves. In fact, there are a variety of them. I'm going to show you one simple example, called a geometric L-system, which is useful for generating a certain kind of iterated function fractal; other…
August 1, 2007
Moving on from simple graphs, one of the things you can do to make things more interesting
is to associate numeric values with the edges, called the weights of those edges. This variation
of a graph is called a weighted graph.
Weighted graphs are extremely useful buggers: many real-world…
July 30, 2007
In the post about Koch curves, I talked about how a grammar-rewrite system could be used
to describe fractals. There's a bit more to the grammar idea that I originally suggested. There's something called an L-system (short for Lindenmayer system, after Aristid Lindenmayer, who invented it for…
July 27, 2007
While reading Mandelbrot's text on fractals, I found something that surprised me: a relationship
between Shannon's information theory and fractals. Thinking about it a bit, it's not really that suprising;
in fact, it's more surprising that I've managed to read so much about information theory…
July 25, 2007
One of the strangest things in fractals, at least to me, is the idea of space filling curves. A space filling curve is a curve constructed using a Koch-like replacement method, but instead of being
self-avoiding, it eventually contacts itself at every point.
What's so strange about these things…
July 23, 2007
Often, we use graphs as a structured representation of some kind of information. Many interesting problems involving the things we're representing can then by described in terms of operations over
graphs. Today, I'm going to talk about some of the basic operations that we can do on graphs, and in…
July 21, 2007
After seeing PZs comments on Stuart Pivar's new version of his book, titled "Lifecode: From egg to embryo by self-organization", I thought I would try taking a look. I've long thought that much of the stuff that I've read in biology is missing something when it comes to math. Looking at things, it…
July 20, 2007
I got hit by a mutant meme; I don't remember who tagged me. I'm not terribly into these
meme things, but I don't pass up excuses to post recipes. So below the fold are four recipes that I've created: seared duck breast with ancho chile sauce; saffron fish stew; smoked salmon hash; and
spicy…