Sunday, November 21, 2004

Give Thanks!

I suspect that the thing I'm most grateful for this year is the fact that we get a week off for Thanksgiving; I need the break! I'm looking forward to seeing Boston and New York and meeting family. Photographs will be forthcoming.

Oh, and I've always been curious about this: What's the origin of "the Bean and Cod"? I googled it, but was surprised to find no useful links except for a poem by William Corbett. I'm too lazy to look it up, so I'd be grateful for a reference.

Updates from Iraq

The Iraqi Electoral commission has confirmed that national elections will be held on Jan 30th. A commission spokesman, Farid Ayar, said that violence-prone areas like Falluja and Mosul will have elections at the same time.
"No Iraqi province will be excluded because the law considers Iraq as one constituency, and therefore it is not legal to exclude any province," he said.

In other news, the Post reports that American forces have found the houses where several hostages were tortured and killed in Falluja. The city appears to be slowly coming under American/Iraqi control, but an increasing number of resistance fighters are using white flags to pose as civilians and then attack deceived soldiers.

One can only hope that elections bring some peace to the country, but it seems doubtful.

Tuesday, November 09, 2004

And finally...

Firefox 1.0 has been launched. Download it today!

Sunday, November 07, 2004

Fighting in Fallujah

Not that it wasn't expected, but Fallujah is under attack. What's most disturbing is that Iraqi Prime Minister Ayad Allawi has declared a state of emergency, not exactly the best start to democracy. Quoting the Times and Post:
Hours earlier, Prime Minister Ayad Allawi, faced with an expanding outbreak of insurgent violence across the country, formally proclaimed a state of emergency for 60 days across most of Iraq. The proclamation gave him broad powers that allow him to impose curfews, order house-to-house searches and detain suspected criminals and insurgents. The order will run for 60 days but could be extended through elections planned for January.

An Eternal Golden Braid

I'm reading (for the first time, much as it pains me to admit it!) Godel, Escher, Bach: an Eternal Golden Braid by Douglas R. Hofstadter. I had meant to read it on many previous occasions, but never got around to it; now, that seems like criminal procrastination. So far, it's a superb book; the author's idea to intersperse dialogues with chapters was nothing less than inspired.

I expected to like the book and find the material not too difficult to follow (Four years of a Computer Science had to have been good for something! -ed.), but the presentation is so lucid that the material should be accessible to a high school student with no exposure to formal systems and so on. In fact, the author's interest in the subject was sparked when he was in high school and read Godel's Proof by Nagel and Newman.

Definitely one of November's Books of the Month!

Saturday, November 06, 2004

High School curricula

Continuing our math theme, we just conducted our second CS225 mid-term, and I've been grading exams for the last few days. I've noticed something interesting; students tend to provide reasonably good answers to questions which require them to write code, but are often unable to write proofs/justification for running times and correctness of algorithms. When I find a particularly good answer to a mathematical question, I often turn to the front and check the student's name out of curiosity; it appears that the best solutions are often written by non-Americans (judging solely by names). Before I get flamed for being racist, I should reiterate that I mean American, not Caucasian. Students of different ethnicities who went through school in America don't seem to do better than average; at least, I haven't noticed any evidence of it.

The most compelling reason for the discrepancy that I can find (since I absolutely refuse to accept any claim that Americans are 'inherently' less mathematically able than others) is the difference in the way Math is taught at the school level. (Disclaimer: I only have India as a basis for comparison, so perhaps this isn't reasonable either.) An Indian student who enters engineering college has already studied (differential and integral) calculus for two years, probability and statistics for at least as long, some form of co-ordinate geometry (with its emphasis on proofs) and algebra for over five years, besides some combinatorics, matrix algebra, and complex analysis. Some high school syllabi even include a fair bit of group theory! Graders in India also tend to be demanding (bordering on ruthless!) when evaluating exams, so students quickly learn when an answer is sufficiently precise to deserve full credit.

So is that a better system? I'm not sure; many Indian students never see a complex number after leaving high school and years of demanding Math often leave them hating the subject. I know several Indians who feel uncomfortable answering an exam question unless they're reasonably sure how to do it; a lack of partial credit (much less common in India than in America) discourages people from risk-taking. And I've noticed that American students are often more creative with solutions to both exam problems and random problems discussed in section, which makes teaching fun. It looks like they make up most of the relative deficiency in college, so doing less math in school doesn't seem like much of a loss. Perhaps the syllabi will change to embrace the best of both systems.

Right now, though, I often wish that there were more emphasis on rigorously correct solutions. Some of the best students seem to think that proof by example is completely reasonable! And it always makes me feel like I've done a terrible job in section when I have to grade papers which make warm, fuzzy statements like:
Trees are a Good Thing (tm) in general when compared to lists (except when they (the trees) are unbalanced, but that doesn't happen for Red-Black Trees (because they are always balanced), so it doesn't make a difference to this answer) and so searching in a tree is usually better than in a list (because we don't have to look at all the tree nodes), so we would rather use a tree.

(Admit it, that's an exaggeration! -ed.) Granted, but I yearn for a plain O(log n)!

Friday, November 05, 2004

Math was never this interesting

2 is an interesting number : Among other things it is the smallest prime. Ramanujam's number ,1729, is interesting, it is the smallest number that can be written as the sum of two cubes in two different ways. Perhaps the largest interesting number we know of is Graham's number.

Is it possible to define exactly what the set of 'interesting' numbers is? Not in any non-trivial way, if you're working with only the natural numbers. Suppose I is a set of of interesting numbers, such that I' is non-empty. Let d be the least element of I'. Since d is the least non-interesting number, it is therefore interesting. This contradicts the assumption that I' is non-empty. Therefore we have,

Theorem: There does not exist a set of dull natural numbers.

Corollary : Every natural number is interesting.

This argument can be extended to any countable set of numbers. How about the real numbers?

Can there exist a dull set of real numbers? Maybe, as long as they are uncountable and do not contain any natural numbers (or integers or rationals) , for then the least such natural number (or integer or rational) would be interesting.

It might seem that since a countable set can always be embedded into such a uncountable dull set of real numbers, its minimum element must always be interesting, but we have to be careful here. We cannot consider arbitrary orderings since they are not interesting.

Thus, if there exists only a countable number of interesting orderings, then there must exist a set of dull real numbers, because each interesting number can also be represented as the least element of an interesting ordering (interesting because it has an interesting element as its least element). Assuming the continuum hypothesis, the converse follows.

(Disclaimer: This article was written after drinking one too many tequila shots and should therefore be taken with a generous dose of salt, rather like the tequila.)

Wednesday, November 03, 2004

Four More Years!

It looks like President Bush will return to the White House for another 4 years. It was evident for several hours that Ohio would decide the election. With 98% of Ohio precincts reporting results, President Bush leads by 51% to 49%, a margin of 136,000 votes. Provisional and absentee ballots are still uncounted, but given that there won't be more than 250,000 of these (a very loose upper bound) and that some of them will be disallowed, I think it's unlikely that Senator Kerry will win enough of these to offset the Bush margin.

Still, the Kerry campaign is not giving up. Mary Beth Cahill, one of the campaign managers said, "The vote count in Ohio has not been completed. There are more than 250,000 remaining votes to be counted. We believe when they are, John Kerry will win Ohio." A few minutes ago, Vice Presidential candidate Senator John Edwards made this announcement to the Democratic supporters outside campaign headquarters: "We've waited four years for this victory, so we can wait one more night."

Since many Democrats were unhappy with Al Gore for not fighting "hard enough or smart enough" (quoting George Stephanopoulos) after the Florida debacle four years ago, Senator Kerry is understandably unwilling to concede the election until he has explored every avenue that could lead to victory. I'm not exactly thrilled by the prospect of a protracted battle, though; such wrangling could have the effect of polarizing the country further. Surely the statisticians employed by the Kerry campaign have reported exactly how unlikely it is that the Senator can pull off a win.

The Republicans appear set to dominate Congress as well. They held 51 seats in the Senate earlier; they have 52 so far, and are leading in all 3 seats for which final results have not been declared. Democrat Tom Daschle, the Senate Minority Leader, appears to be one of the casualties. The Republicans will also probably have a comfortable majority in the House. We'll have to wait to see how all this plays out.

Tuesday, November 02, 2004

Record Voter Turnouts?

Looking through early news stories, one thing is clear: regardless of who wins, the turnout at this election will be among the highest in recent memory. In spite of heavy rain in many parts of the country, this election is expected to witness at least 118 million voters, and may set the all-time record. Two newsbites that struck me:

From the New York Times,
In North Philadelphia, Valerie Morman, a legal secretary, walked to her polling place at St. Malachy School. "The last time I voted," she said, "was about 20 years ago."

From the Washington Post,
In north Milwaukee, 19-year-old Maurice Dodson waited in a long line to cast the first presidential vote of his life. "No way I'm leaving," he said after an hour with no ballot in sight. "I'm very excited.