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.
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.
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
submissions.
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.
| Author | Title |
|---|---|
| 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 |
| Eric Macaulay | Equivalence |
| 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.)