注: 这个问题来自China Theory Week 2008的Open Problems Session。
我们知道在数学里证明一个东西的存在性的时候，有时候只证明了“存在性”，而且在证明过程中并没有说明如何找到它，这种证明方法被称为“非构造性证明”。有些流派的数学家对这种证明方法非常不满，具体这里就不详谈了。
这里要说的是，一个玩意儿，即时你知道它总是存在的，它也是可以算出来的...

下面这个求的函数号称比直接调用sqrt库函数快4倍，来自游戏Quake III的源代码。
float InvSqrt (float x){
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i>>1);
y = *(float*)&i;
y = y*(1.5f - xhalf*y*y);
return x;
}

我们这里分析一下它的原理（指程序的正确性，而不是解释为何快）。
分析程序之前，我们必须解释一下float...

Xie Xie推荐了一本今年出版的一本新书，Encyclopedia of Algorithms，全书1200页，涵盖各类有名问题的算法，概率算法，近似算法，量子算法等。
翻了一下，很多算法都不是直接给出的，只是给出一些原理描述和参考文献。看来这本也真只能当当索引用了。
没事做的话可以先欣赏一下第698页的O(n)的平面图判定算法。
按照推荐人xiexie的说法，看在原书高达309欧元的价...

给定的实数矩阵，每行和每列都是递增的，求这个数的中位数。
使用类似Tarjan的线性中位数的方法，每次找每列中位数，然后找中位数的中位数，之后可以删除前一半列的上半部分或者后一半列的下半部分，这样可以实现复杂性。
但是这个问题是有的算法的，在Top Language Google Group的Obtuse Sword的指点下，找到了这个问题的原始论文：Generalized Selection and Ranking: Sorted M...

珍爱生命，远离政治。我们继续讨论算法。
2008/04/01补充：此算法有重大缺陷。详情请见留言部分。
一年前，我们讨论过一个算法问题，perfect shuffle，据称是个微软面试题：
输入，如何用的时间，的空间，将这个序列顺序改为。

那一次讨论我们翻出了问题的来源，一篇长达12页的论文Computing the Cycles in the Perfect Shuffle Permutation，算法那是非常的复杂，我估...

Xie Xie给我看了一个链接性能调优--永远超乎想象，里面提到了素数筛法的复杂度，作者用实验发现此筛法是线形的。
所谓素数筛法就是那个求小于n的所有素数最简单的算法：
bool* prime(int n) {
bool *p = new bool[n];
memset(p, 0, sizeof p);
for (int i = 2; i < n; i++)
if (!p[i])
for (int j = 2*i; j < n; j+=i)
p[j] = true;
[...]

Rob Pike, 最伟大的 C 语言大师之一 , 在Notes on C Programming(英文原文)中从另一个稍微不同的角度表述了 Unix 的哲学:

你无法断定程序会在什么地方耗费运行时间。瓶颈经常出现在想不到的地方，所以别急于胡乱找个地方改代码，除非你已经证实那儿就是瓶颈所在。
估量。在你没对代码进行估量，特别是没找到最耗时的那部分之前，别去优化速度。
花哨的算法在 n ...

更新：证明的关键一步发现错误，作者更新了论文，结论甚至论文标题都改了（废话），新版本On the graph isomorphism problem。
提交论文到arxiv不需要审阅，一般人都可以提交，所以常有些错误的论文甚至民科作品（在物理和数学领域更多一点）。号称解决图同构问题甚至p vs np以前也有过，不过这次文章的作者的publication记录不错，有2篇ann. of Math.，数量也不少，所以大家稍...

今天香港中文大学的Prof. Cai给我们上graph algorithm。第一节课上教我们玩魔方，先给每人发了一个。我喜欢这样的教学方法 。
魔方的解法，在网上已经有无数了，基本上的思路都是几个定式，玩的时候记住这些定式即可。课上Cai给我们演示了一个他自创的定式，很可惜，我目前为止只学会弄出一面来。
OK，这篇文章的主要目的是讲魔方里的数学，对魔方的群结构研...

一个面试题，号称是微软的
输入，如何在O(n)的时间，用O(1)的空间，将这个序列顺序改为。

刚一眼看上去觉得很容易，做了一回儿才发现深不可测。题目大致是要求在线性时间，常数空间实现下面的置换
x -> 2x mod 2n+1

我做了两小时没做出来，上网一搜，最近这个题目很热，已经有人在讨论这个题目，还翻出了问题的发源地http://www.cs.uvic.ca/~jellis/perfect.ht...