Computing Strongly Connected Components

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
of Kosaraju’s.

Continue reading Computing Strongly Connected Components

Friday Not-So-Random 10

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.

  1. 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.
  2. 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
    are.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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
    listening to.
  8. 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
    unique guitar.
  9. 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.
  10. 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.

Tag-Teaming with Orac: Bad, Bad Breast Cancer Math in JPANDS

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?

Continue reading Tag-Teaming with Orac: Bad, Bad Breast Cancer Math in JPANDS

Making Graph Algorithms Fast, using Strongly Connected Components

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.

Continue reading Making Graph Algorithms Fast, using Strongly Connected Components

The Faith Equation: Part Two of the Review

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.

Continue reading The Faith Equation: Part Two of the Review

More Old Friends: The Bible Code Guys

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.

Continue reading More Old Friends: The Bible Code Guys

Doctor Who and Spinoffs

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.

Continue reading Doctor Who and Spinoffs