As promised, today I'm going to talk about how to compute the strongly connected components
of a directed graph. I'm going to go through one method, called Kosaraju's algorithm, which is
the easiest to understand. It's possible to do better that Kosaraju's by a factor of 2, using
an algorithm called Tarjan's algorithm, but Tarjan's is really just a variation on the theme
Archive for: October, 2007
As promised, today I'm going to talk about how to compute the strongly connected components
This past week, I discovered a new digital music download site, called Bitmunk. It's less expensive
than iTunes or Amazon, and has a fantastic selection of obscure bands. Through Bitmunk, I found
a couple of terrific new neo-progressive bands, which has me on a serious prog kick. So for today, I've
narrowed the domain of the randomization to just the progressive stuff, and I also cheated a bit to make
sure that the two best of the new bands I found are included in the list.
Just to be clear, I've got no connection with Bitmunk, they're not giving me anything to mention them, etc. I found them by way of a comment in the last FRT here. Someone pointed me at the Bayprog website, which I followed to find a link to Metaphor's website; after listening to a sample there, I decided to buy their album, and they linked to Bitmunk for digital purchases.
- The Mars Volta, "Inertiatic ESP". The Mars Volta is a recent discovery for me, but not
via the new site. They're a sort of hyperkinetic neo-progressive group. The best I can do at describing them is to say that they sound like a cross between King Crimson and Dream Theatre, hopped up on too
much caffeine. They're very good - wonderful when I'm in the right mood, but they're not the easiest
listen. There's so much going on, so many fast twists and shifts that it's easy to get lost. This is a very typical one of their tracks. Weird rhythmic shifts, incredible density. Very cool stuff.
- The Flower Kings, "Pioneers of Aviation". I love the Flower Kings. They are, in my opinion,
the very best of the neo-progressive bands. Their music is brilliantly written - deep, complex, but still
melodic, and they've got the chops to really pull it off. This is one of my favorite instrumental tracks
off of their second most recent album. There's just no way I can say enough about how great the FKs
- Elegant Simplicity, "Time to Breath". This is one of the two great bands that I discovered
through Bitmunk. This is the opening track off of their album "The Architect of Light". I think it's
a good introduction to them. The opening is wonderfully strange; a capella voice singing the melody
that will become the main theme, placed over a strange King Crimsonesque background of tape loop
and selected noise - with the vocals in a different key than the background, creating a dissonance
out of what will turn out to be a very smooth melodic theme. They're clearly very influenced by
the Flower Kings - they've got a very FKish sound; but not derivative, just clearly influenced.
Very good stuff, I highly recommend it.
- Marillion, "Ocean Cloud". You can't talk about neo-prog rock without mentioning Marillion. During the dark days of the 80s, they were one of the only bands keeping the progressive flame
alive. This track is an 18 minute opus off of the "Marbles" double-album, and it's a great example
of what I think makes Marillion so great. What they've always been best at, to me, is transitions: the best moments in their music are always in the points of change, where they're shifting between themes or moods. "Ocean Cloud" really shows this off, as it shifts back and forth between gentle, almost lullaby-like delicacy, and roaring intensity.
- King Crimson, "FraKctured". You can't talk about any kind of progressive rock without mentioning King Crimson. In my opinion they're just the best progressive group ever, period. They've
gone through many incarnations over the years, from the days when they started off as "The Cheerful Insanity of Giles, Giles, and Fripp"; to the original King Crimson; to the Red era, to the quartet
with Fripp, Belew, Bruford, and Levin; to the fractalized ProjeCKts; to the current quartet group. Each
era has been different, all have been amazing.
- Spock's Beard, "Sometimes They Stay, Sometimes They Go". One of the first really great
bands in the current wave of neo-progressive. A good track off of their latest album.
- Metaphor, "Wheel of the World". The other of my Bitmunk discoveries. This is from a
great album, "Entertaining Thanatos", which the group describes as "Seven lighthearted songs about death". Metaphor isn't quite up there with "Elegant Simplicity", but they're very good. They've got
some pretty clear influences: there's a strong sense of King Crimson and the Flower Kings about
their style. But there's also some very distinctive and unique stuff. Very good, definitely worth
- King Crimson, "Requiem". More King Crimson. You can never go wrong with more Crimson!
This is from the second album with Adrian Belew on vocals, but the track is dominated by Fripp's
- Porcupine Tree, "The Sky Moves Sideways, Phase 2". The only neo-progressive group with
a chance of competing with the Flower Kings for the title of "Best Neo-prog". I don't think that
they quite manage to beat out the Kings, but they come closer than anyone else. This is from their
most "out there" album. A must listen album.
- Pink Floyd, "Astronomy Domine". And we finish off with something very much not
Neo. A track from Pink Floyd's debut album in the 1960s. The version that I'm listening to is the
1969 live performance from Ummagumma. This version just gives me chills. A mediocre quality recording that's nearly 40 years old, and it manages to not sound dated at all.
My friend, fellow ScienceBlogger, and BlogFather Orac asked me to take a look at a paper that purportedly shows that abortion is a
causative risk factor for breast cancer, which he posted about
this morning. When the person who motivated me to start what's turned out to be a shockingly
successful blog asks for something, how could I possibly say no? Especially when it's such a great example
of the misuse of mathematics for political purposes?
One of the problems with many of the interesting graph algorithms is that they're complex. As graphs get large, computations over them can become extremely slow. For example, graph coloring is NP-complete - so the time to run a true optimal graph coloring algorithm on an arbitrary graph grows exponentially in the size of the graph!
So, quite naturally, we look for ways to make it faster. We've already talked about using
heuristics to get fast approximations. But what if we really need the true optimum? The other approach to making it faster, when you really want the true optimum, is parallelism: finding some way to subdivide
the problem into smaller pieces which can be executed at the same time. This is obviously a limited
technique - you can't stop the exponential growth in execution time by adding a specific finite
number of processors. But for particular problems, parallelism can make the difference between
being able to do something fast enough to be useful, and not being able to. For a non-graph
theoretic but compelling example, there's been work in something called microforecasting, which is precise weather forecasting for extreme small areas. It's useful for predicting things like severe lightning storms in local areas during events where there are large numbers of people. (For example, it was used at the Atlanta olympics.) Microforecasting inputs a huge amount of information about local conditions - temperature, air pressure, wind direction, wind velocity, humidity, and such, and computes a short-term forecast for that area. Microforecasting is completely useless if it takes longer to compute the forecast than it takes for the actual weather to develop. If you can find a way to split the computation among a hundred processors, and get a forecast in 5 minutes, you've got something really useful. If you have to run it on a single processor, and it takes 2 hours - well, by then, any storm
that the forecast predicts is already over.
For graphs, there's a very natural way of decomposing problems for parallelization. Many complex graphs for real problems can be divided into a set of subgraphs, which can be handled in parallel. In
fact, this can happen on multiple levels: graphs can be divided into subgraphs, which can be divided
into further subgraphs. But for now, we'll mainly focus on doing it once - one decomposition of
the graph into subgraphs for parallelization.
The bulk of this part of the review is looking at the total train-wreck that is chapter 4, which contains Bittinger's version of dreadful probabilistic arguments for
why Christianity must be true. But before I do that, I need to take care of one loose
end from part 1. I should have included chapter three in part one of the review, since it's really just a continuation of the paradox rubbish, but I didn't.
Time for our second visit with old friends. This time, we're going to check up on "The Lords Witnesses", the bible code geniuses who made somewhere around a dozen attempts at using their code to nail down a date at which the UN building in NYC would be blown up.
These nutters are a spinoff of the Jehovah's witnesses. They believe that there is a secret code
embedded in the bible. They agree that all of the other people who claim to have found secret codes in
the bible are all just a bunch of crackpots - but they have the truth.
As many of you know, I'm a big Doctor Who fan. Big enough that I've grabbed all of the episodes of the new series, and its spinoffs, via BitTorrent. (I also buy them on DVD as soon as they become available.) A few folks have asked me what I think of the spinoffs. And I'm sick at home, feeling like hell, not up to doing any work or any serious math writing. So I've been sitting around watching videos, which makes this the perfect time to tell you about what I think of them. I'll run through my opinions of the episodes of the third season of Doctor Who, the first season of Torchwood, and the episodes of the Sarah Jane adventures that have been broadcast so far.
To be honest, I haven't been following the Carnival of Math much since it's inception; my new job keeps me busy enough that I barely have time to keep the blog going, and so I haven't really looked much at recent editions. In fact, I completely forgot that I was hosting it again until I started receiving
Much to my disappointment, it appears that spam has managed to invade even the carnivals. Close to half of the submissions that I received were blatant spam, including one for a penis-enlargement pill. But hey, when a theme hits me in the face, I run with it. So, welcome to the Carnival of Math: Spam Edition!
Get rich quick, by betting on the World Series! Just learn how to play the odds; we can show you how, with our entertaining and <a href="http://jd2718.wordpress.com/2007/10/19/puzzle-last-one-left-over/"educational probability puzzles! Once you've mastered that, just look at the batting averages, and place your bets!
Refinance your mortgage! Having trouble with rising interest rates? Is your bank balance in the red? Do you feel like no matter how much you scrimp, it never adds up to enough to pay your bills? Like
every time you save 2 dollars, you still have no money left? It's not your fault: the real problem is the numbers you're using! With primitive, old-fashioned numbers, if you're not careful, 1+1=0! Just switch over to our new improved number system, Z2, where there are no negative numbers at all! Our prime polynomials and their relatives can solve your problems! But that's not all - we'll throw in a Catalan ring for free!
Are you lonely? Do women find you dull, the neutral element in any group?
Do you yearn to finding the perfect woman to share your life with? We can help! Our
patented methods can teach you how to attract women, and our ideal ring is
guaranteed to seal the deal with the woman of your dreams!
The world is changing. Globalization is creating a new job market, where
old-fashioned skills aren't enough to succeed. Even if your children are
the best and the brightest, standard education won't give your
children the edge they need. Don't let your children go into their PSATs unprepared! Our methods are guaranteed to help your children excel. Not all test prep
programs are equivalent: enroll your children in the best!
For those of you who just want to be able to see the articles, here's the list, in table form.
|Anne Glamore||Beyonce and I Fail Long Division|
|Charles Daney||Rings and Ideals|
|Dave Marain||Educating our best and brightest: Alec Klein Interview|
|Dave Marain||Last minute PSAT prep|
|David Eppstein||Batting Averages|
|jd2718||Puzzle: last one left over|
|Mark Dominus||The square of the Catalan Sequence|
|Mark Dominus||Relatively prime polynomials over Z2|
|Martin Cooke||Two "proofs" that 1 + 1 = 0|
|Slawomir Kolodynski||Groups and neutral elements|
A few weeks ago, I received an email about a new book, "The Faith Equation", by Marvin Bittinger. Bittinger is an author of math textbooks - including, I think, my first calculus text. The book is supposed to be Bittenger's explanation of how mathematics validates christianity. Needless to say,
I asked for a review copy - this is something right up my alley.
I've taken longer to get around to reviewing it than I intended, but life's been busy
lately. I'm going to review it in several parts: it's too dense, full of bad arguments of so many different kinds that I can't possibly do it justice with only one post.
Today, I'll cover the introdution and first two chapters: "The Beginning of a Mathematician's Journey", "Apologetics and Faith Axioms", "Paradoxes in Mathematics and Christianity".
Today we've got a bit of a treat. I've been holding off on this for a while, because I wanted to do it justice. This isn't the typical wankish crackpottery, but rather a deep and interesting bit of crackpottery. A reader sent me a link to a website of a mathematics professor, N. J. Wildberger, at the University of New South Wales, which contains a long, elegant screed against the evils of set theory, titled "Set Theory: Should You Believe?"
It's an interesting article - and I don't mean that sarcastically. It's over the top, to the point of extreme silliness in places, but the basic idea of it is not entirely unreasonable. Back at the beginnings of set theory, when Cantor was first establishing his ideas, there was a lot of opposition to it. In
my opinion, the most interesting and credible critics of set theory were the constructivists. Put briefly, constructivists believe that all valid math is based on constructing things. If something exists, you
can show a concrete instance of it. If you can describe it, but you can't build it, then
it's just an artifact of logic.
Some of that opposition continues to this day, and it's not just the domain of nuts. There are
serious mathematicians who've questioned the meaningfulness of some of the artifacts of modern
set-theory based mathematics. Just to give one prominent example, Greg Chaitin has given lectures in which he discusses the idea that the real numbers aren't real: they're just logical artifacts which can never actually occur in the real world, and rationals are the only real real numbers. (I don't think that Greg really believes that - just that he thinks it's an interesting idea to consider. He's far
too entranced with set theory. But he clearly considers it valid enough to be worth thinking about
and talking about.)