Someone Writes An Algorithm Zen

I like to look at CS 170 as one exponentially large graph search problem. 
We have a plethora of information given to us to guide our way (as a 
search heuristic) to the goal node, which is achieving algorithmic zen. In 
the end, we should eat, sleep, and breathe big O notation. We should 
cringe at exponentials of any form. Our hearts should skip a beat when we 
read the words "constant time", yet remain brave when staring down an 
NP-hard problem. We should be so lucky to have committed to memory all 
algorithms we've learned, yet never assume that our machines can commit 
much to memory at all. Once you have reached this land, you are in the 
enlightened world of efficiency, problem solving, and babes. Well, maybe 
not the last part, but you'll still be really, really cool in my books. 

Now, assuming that we began at the same start node of basic 61b algorithm 
knowledge, we want to find this path to our shangri-la in as short a time 
as possible. If not solely because we are excited to get there, then at 
least because you'll do well on tests if you achieve enlightenment 
faster. Given these requirements, what better method than to call upon 
the prophet Dijkstra who has graced us with his algorithm? Hence, we 
must follow the path of Dijkstra through this land of unintelligible 
mathematics and weird newsgroup posts at 3 am on a Saturday. Now, I 
cannot give you his specific commandments, as any man delivering 
commandments has to have a sweet beard. I do not have a 
sweet beard, though not for lack of trying, and thus I can only provide 
my worldly wisdom as to the way of Dijkstra. 

The most important secret to this course is the practice of writing 
and analyzing algorithms. As any good kung-fu movie shows us, you need 
to have a painful training montage if you are to achieve your goal. 
Though, since we are only beginners, we must learn proof techniques from 
the masters Rao and Papadimitrou. In the chapter, the problem at hand is 
always presented first, and then the algorithm is given. You never 
get to experience the frustration and thought put into discovering what 
is presented. As an example, have you ever seen master Sinclair smile? 
No, for he is tortured by the demons he must wrestle. To really get a 
grasp of this learning process, try to write your own algorithm before it 
is presented to you in the book. Yes, your answer is nowhere near as good 
Papadimitrou's, but you can now compare the approach of an apprentice 
to that of a master. To know where you are headed, you must know where 
you came from and where you are. 

In that vein, approach your homework as if it were a baby lion. It is 
relatively small and beautiful creature, yet it grows to be a dangerous 
beast that will eat your entrails if not tamed. Come prepared with reams 
of paper and sit in your favorite library for at least 3 hours attacking 
the problems by yourself. During this time, you must try every possible 
sneaky way of snatching the solutions from the jaws of ignorance. Do not 
rush, do not cry, do not leave your seat, just write. If the answer does 
not come to you immediately, write a slow inefficient answer. You can 
always recycle the paper later. Thomas Edison was famous claiming "I 
have not failed. I've just found 10,000 ways that don't work." He 
was an amateur. You should have at least O(100!) ways that don't work 
efficiently. 

If one of your many explorations of this solution space 
does not grant you the solution master Rao seeks, then you must go to 
the hours of the office. Though our professors and GSI's do their best 
to schedule them at the same time as our classes, this is only done to 
to ward off the freeloading answer seekers who are not pure in their 
persuit of algorithmic zen. Fret not, for they will meet a negative 
cycle in the graph of life from which they will never escape. It is 
here that you may ask for guidance AND ONLY GUIDANCE to the one true 
solution. 

When you have reached the coveted solution you will realize the 
reward of algorithmic glory. Do not worry if your perspiration 
increases along with your heart rate, this is normal. You will quake 
with excitement as your pen graciously rounds the curves of a paren, 
and stabs sharply with the joint of a sigma. It is this feeling that 
keeps us going forward. For you not only know the answer, but you 
know the dangerous turns to avoid, having taken them yourself. 

May your base cases always be defined, 
May your code always elude perplexity, 
May your run times always be confined 
to the lowest asymptotic complexity. 

http://groups.google.com/group/ucb.class.cs170/browse_thread/thread/1f2cc705af705560?pli=1

pointer 'dirty trick'

ANSI C guarantees that it is safe to cast a pointer to a structure to a pointer to the type of that structure's first element.

example:
struct bst_node {
struct bst_node *link[2];
void *data;
};

struct bst_tree {
struct bst_node *root;
int count;
};

applying the rule:
we know that root is a pointer to bst_node, it's type: bst_node *,
the first element of bst_node is struct bst_node *,too!
so it is safe to cast from struct bst_node * to struct bst_node **,
the latter is a pointer to struct bst_node *,
So if struct bst_tree *t;
then link[0] == (struct bst_node *)&t->root;

reference:http://www.red-bean.com/guile/guile/new/msg02536.html

topological sort taocp 2.2.3,vol 1

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int indegree[9];
vector<vector<int> > vv(9);
typedef vector<int>::iterator it;
queue<int> q;
bool flag[9];

void init() {
    memset(flag, false, sizeof(bool)*9);
    memset(indegree, 0, 9*sizeof(int));
    vv[0].push_back(2);++indegree[2];
    vv[1].push_back(7);++indegree[7];
    vv[2].push_back(6);++indegree[6];
    vv[3].push_back(5);++indegree[5];
    vv[4].push_back(7);++indegree[7];
    vv[6].push_back(3);++indegree[3];
    vv[6].push_back(4);++indegree[4];
    vv[7].push_back(5);++indegree[5];
    vv[8].push_back(1);++indegree[1];
    vv[8].push_back(4);++indegree[4];
}
void tsort() {
    for (int i = 0; i<=8; i++) 
        if (indegree[i] == 0 && !flag[i]) {
            q.push(i);
            while(!q.empty()) {
                int number = q.front();
                cout << number << ' ';
                flag[number]= true;
                q.pop();
                for ( it ii = vv[number].begin(); ii != vv[number].end(); ++ii) {
                    --indegree[*ii];
                    if ( indegree[*ii] == 0)
                        q.push(*ii);
                }
            }
        }
}
int main(){
    init();
    tsort();
    return 0;
}

joke from taocp

Volume 1, p200:

Little old lady，riding a bus."Little boy, can you tell me how to get off at Pasadena Street?"

Little boy. "just watch me, and get off two stops before I do."

百度一面就被fault了

感谢Nvidia，Tencent，Baidu给机会我面试，是时候总结一下自己的面试经历了。笔试了很多公司，大大小小，像阿里巴巴，微软，朗讯，甲骨文，深信服（舍友就是签了这间的），华为等，他们都因为自己幼稚，水平做题水平低下，没有就会面试。总体来说，每次面试自己对缺乏主动询问自己所申请的职位的相关信息，没有把自己的意愿所表示出来，Nvidia是电话面试，面试官叫阿Ted，感觉他很不错，所问的问题都是很简单的，但是自己感觉对硬件不是很感兴趣，所以明知道他问些简单的数字电路问题，也没有去预先准备，这个不能怪谁，因为我知道自己更喜欢往软件或者互联网方向发展。Tencent的一面感觉自己表现不错，面试官很nice，没有问他的名字，太可惜了，毕竟他是第一个现场面试自己的人。但是二面挂了，理由很简单，他们想招的是网管，而我却说出来自己想当个程序员的欲望，后来经理也特意暗示了我的下场，而且还问了些服务器坏掉的解决方案，明知道我没有哪个方面的东西，还是往那边的问，我也没有办法了，临走时，他就主动跟我说“感谢你参加腾讯的这次招聘活动”，唯有泪奔。昨天刚刚面完baidu，这是第一次正式通过笔试，要知道我可以准备了一个多星期的，在那段日子里，我根本就没有再海投，专心一志，看算法导论，看programming peals，看programming interviews exposed，做n多的面试笔试题目，因为华为也同时过来，所以自己很好的准备一番，但不是知道为何，baidu的笔试过了，而华为的没有通过，问谁都知道baidu的题目更加难，而华为考的是基础题目，这个也很遗憾。不过据说华为要群殴，可惜没有机会参加。baidu的面试官人长得很踏实，我进来的是个昨天刚面完华为的牛逼研究生，他可是没有理会百度当天的面试请求，参加华为的面试的，不过据说晚上百度还是邀请他去面试了，够牛的。因为我的简历写着学习进步奖，所以他问了我的成绩，这个意思人人都知道的，我也没有说什么，只能说自己中等生，但是最好一次有点进步所以得到进步奖了，接着他叫我shell小程序，内容就不说了，很简单的，但是我说自己已经忘记语法了，这个和简历上的东西有点不符合把，他说好了，然后叫我做智力题，我心里感觉很不爽，因为知道飞来同学在面试腾讯的时候被问一个智力题而挂了，我还说自己很少做这类东西的，说完题目，他就去上网了，叫我好好思考，我没有法，只能好好想了，最后还真做出了，回来查网上的解答也是同样的做法，据说是ms的题目，这时他说这次的技术方面的东西就结束了，这之前他还叫我介绍了自己的小小项目，这个好像是例牌来的，没有啥好说，然后开始了提问环节，我估计自己就是在这里失败的，最后他问我还有没有别的问题，还很该死的说外面很漂亮，我想出去走走，我也不知道自己为何会说出这种话的，可能自己太紧张了，这时我想他一定是心里说，那么你以后就别再想有机会进来了，这次打击很大，面对自己喜欢的公司，而无力挽回，实在是很伤心。

同宿舍的同学已经有找到不错的工作了，在今年这种气氛，能够及早有着落，太幸福了，仰慕中。刚刚问了一下老托，他说现在17周了，班左里大概有5个右的同学有offer，找工的大概有40人，要加紧点了，写这些东西，希望警戒自己，以后好好努力，能够找到自己向往的工作。千万不要这么早就灰心了，生活毕竟要继续的，baidu的伤要慢慢治疗，不要这样就放弃了。

笔试概率题目

题目
有两个数组A[n], B[m], n
A中的n个元素互不相同，对B中的每一个元素，
都从A中随机取一个元素放入其中，
求A中的n个元素在B中都出现的概率
解答
从古典概率的角度来考虑，相当于从集合A（a1,a2,....,an)中选择元素放到筐子B1,B2,...,Bm中去，求在这m个框子中包含了全部A中元素的概率。

首先，从A中选择元素放置到框子中的方法有n^m中，是没有问题的，
其次，需要计算这些放置方法中把A中所有元素都取了一遍的方法个数。楼下这种方法给出的是n!*n^(m-n),我可以看成是取了前n个筐子莱放置A中n个元素，那么有n!种方式，然后后面的m-n个筐子可以随便放，有n^(m-n)种方式，所以是n!*n^(n-m)中。但是这种方式减少了可能的次数。考虑将m个不同的元素分成n份，这个数目记为S(m,n), 那么我们需要计算的这个数应该是n!*S(m,n)
那么概率就是 n!*S(m,n)/n^m
因为是有标号的，所以Stirling数前面乘一个n!嘛。
ps:
stirling数
将n个不同颜色的球放人k个无标号的盒子中( n>=k>=1，且盒子不允许为空)的方案数就是stirling数.(即含 n 个元素的集合划分
为 k 个集合的情况数)
递推公式:
S(n,k) = 0 (k > n)
S(n,1) = 1 (k = 1)
s(n,k)=1 (n=k)
S(n,k) = S(n-1,k-1)+k*S(n-1,k) (n >= k >= 2)

在北京大学2008年开学典礼上的发言

在北京大学2008年开学典礼上的发言 英语系80级校友、新东方教育科技集团董事长兼总裁俞敏洪 2008年9月21日 　　北大原来从未邀请过校友在开学典礼上讲话，2008年开学典礼，北大邀请了新东方教育科技集团董事长兼总裁俞敏洪老师讲话，这是俞老师的一种荣幸，更是新东方的一种荣誉。 各位同学、各位领导： 大家上午好！（掌声） 非常高兴许校长给我这么崇高的荣誉，谈一谈我在北大的体会。（掌声） 可以说，北大是改变了我一生的地方，是提升了我自己的地方，使我从一个农村孩子最后走向了世界的地方。毫不夸张地说，没有北大，肯定就没有我的今天。北大给我留下了一连串美好的回忆，大概也留下了一连串的痛苦。正是在美好和痛苦中间，在挫折、挣扎和进步中间，最后找到了自我，开始为自己、为家庭、为社会能做一点事情。 学生生活是非常美好的，有很多美好的回忆。我还记得我们班有一个男生，每天都在女生的宿舍楼下拉小提琴，（笑声）希望能够引起女生的注意，结果后来被女生扔了水瓶子。我还记得我自己为了吸引女生的注意，每到寒假和暑假都帮着女生扛包。（笑声、掌声）后来我发现那个女生有男朋友，（笑声）我就问她为什么还要让我扛包，她说为了让男朋友休息一下（笑声、掌声）。我也记得刚进北大的时候我不会讲普通话，全班同学第一次开班会的时候互相介绍，我站起来自我介绍了一番，结果我们的班长站起来跟我说：“俞敏洪你能不能不讲日语？”（笑声）我后来用了整整一年时间，拿着收音机在北大的树林中模仿广播台的播音，但是到今天普通话还依然讲得不好。 人的进步可能是一辈子的事情。在北大是我们生活的一个开始，而不是结束。有很多事情特别让人感动。比如说，我们很有幸见过朱光潜教授。在他最后的日子里，是我们班的同学每天轮流推着轮椅在北大里陪他一起散步。（掌声）每当我推着轮椅的时候，我心中就充满了对朱光潜教授的崇拜，一种神圣感油然而生。所以，我在大学看书最多的领域是美学。因为他写了一本《西方美学史》，是我进大学以后读的第二本书。 为什么是第二本呢？因为第一本是这样来的，我进北大以后走进宿舍，我有个同学已经在宿舍。那个同学躺在床上看一本书，叫做《第三帝国的兴亡》。所以我就问了他一句话，我说：“在大学还要读这种书吗？”他把书从眼睛上拿开，看了我一眼，没理我，继续读他的书。这一眼一直留在我心中。我知道进了北大不仅仅是来学专业的，要读大量大量的书。你才能够有资格把自己叫做北大的学生。（掌声）所以我在北大读的第一本书就是《第三帝国的兴亡》，而且读了三遍。后来我就去找这个同学，我说：“咱们聊聊《第三帝国的兴亡》”，他说：“我已经忘了。”（笑声） 　　我也记得我的导师李赋宁教授，原来是北大英语系的主任，他给我们上《新概念英语》第四册的时候，每次都把板书写得非常的完整，非常的美丽。永远都是从黑板的左上角写起，等到下课铃响起的时候，刚好写到右下角结束。（掌声）我还记得我的英国文学史的老师罗经国教授，我在北大最后一年由于心情不好，导致考试不及格。我找到罗教授说：“这门课如果我不及格就毕不了业。”，罗教授说：“我可以给你一个及格的分数，但是请你记住了，未来你一定要做出值得我给你分数的事业。”（掌声）所以，北大老师的宽容、学识、奔放、自由，让我们真正能够成为北大的学生，真正能够得到北大的精神。 当我听说许智宏校长对学生唱《隐形的翅膀》的时候，我打开视频，感动得热泪盈眶。因为我觉得北大的校长就应该是这样的。（掌声） 我记得自己在北大的时候有很多的苦闷。一是普通话不好，第二英语水平一塌糊涂。尽管我高考经过三年的努力考到了北大——因为我落榜了两次，最后一次很意外地考进了北大。我从来没有想过北大是我能够上学的地方，她是我心中一块圣地，觉得永远够不着。但是那一年，第三年考试时我的高考分数超过了北大录取分数线七分，我终于下定决心咬牙切齿填了“北京大学”四个字。我知道一定会有很多人比我分数高，我认为自己是不会被录取的。没想到北大的招生老师非常富有眼光，料到了三十年后我的今天。（掌声）但是实际上我的英语水平很差，在农村既不会听也不会说，只会背语法和单词。我们班分班的时候，五十个同学分成三个班，因为我的英语考试分数不错，就被分到了A班，但是一个月以后，我就被调到了C班。C班叫做“语音语调及听力障碍班”。（ 笑声） 我也记得自己进北大以前连《红楼梦》都没有读过，所以看到同学们一本一本书在读，我拼命地追赶。结果我在大学差不多读了八百多本书，用了五年时间（掌声）。但是依然没有赶超上我那些同学。我记得我的班长王强是一个书癖，现在他也在新东方，是新东方教育研究院的院长。他每次买书我就跟着他去，当时北大给我们每个月发二十多块钱生活费，王强有个癖好就是把生活费一分为二，一半用来买书，一半用来买饭菜票。买书的钱绝不动用来买饭票。如果他没有饭菜票了就到处借，借不到就到处偷。（笑声）后来我发现他这个习惯很好，我也把我的生活费一份为二，一半用来买书，一半用来买饭菜票，饭票吃完了我就偷他的。（笑声掌声） 毫不夸张地说，我们班的同学当时在北大，真是属于读书最多的班之一。而且我们班当时非常地活跃，光诗人就出了好几个。后来挺有名的一个诗人叫西川，真名叫刘军，就是我们班的。（掌声）我还记得我们班开风气之先，当时是北大的优秀集体，但是有一个晚上大家玩得高兴了，结果跳起了贴面舞，第二个礼拜被教育部通报批评了。那个时候跳舞是必须跳得很正规的，男女生稍微靠近一点就认为违反风纪。所以你们现在比我们当初要更加幸福一点。不光可以跳舞，而且可以手拉手地在校园里面走，我们如果当时男女生手拉手在校园里面走，一定会被扔到未名湖里，所以一般都是晚上十二点以后再在校园里面走。（笑声掌声） 我也记得我们班五十个同学，刚好是二十五个男生二十五个女生，我听到这个比例以后当时就非常的兴奋（笑声），我觉得大家就应该是一个配一个。没想到女生们都看上了那些外表英俊潇洒、风流倜傥的男生。像我这样外表不怎么样，内心充满丰富感情、未来有巨大发展潜力的，女生一般都看不上。（笑声掌声） 我记得我奋斗了整整两年希望能在成绩上赶上我的同学，但是就像刚才吕植老师说的，你尽管在中学高考可能考得很好，是第一名，但是北大精英人才太多了，你的前后左右可能都是智商极高的同学，也是各个省的状元或者说第二名。所以，在北大追赶同学是一个非常艰苦的过程，尽管我每天几乎都要比别的同学多学一两个小时，但是到了大学二年级结束的时候我的成绩依然排在班内最后几名。非常勤奋又非常郁闷，也没有女生来爱我安慰我。（笑声）这导致的结果是，我在大学三年级的时候得了一场重病，这个病叫做传染性侵润肺结核。当时我就晕了，因为当时我正在读《红楼梦》，正好读到林黛玉因为肺结核吐血而亡的那一章，（笑声）我还以为我的生命从此结束，后来北大医院的医生告诉我现在这种病能够治好，但是需要在医院里住一年。我在医院里住了一年，苦闷了一年，读了很多书，也写了六百多首诗歌，可惜一首诗歌都没有出版过。从此以后我就跟写诗结上了缘，但是我这个人有丰富的情感，但是没有优美的文笔，所以终于没有成为诗人。后来我感到非常的庆幸，因为我发现真正成为诗人的人后来都出事了。我们跟当时还不太出名的诗人海子在一起写过诗。后来他写过一首优美的诗歌，叫做《面朝大海，春暖花开》，我们每一个同学大概都能背。后来当我听说他卧轨自杀的时候，嚎啕大哭了整整一天。从此以后，我放下笔，再也不写诗了。（掌声） 记得我在北大的时候，到大学四年级毕业时，我的成绩依然排在全班最后几名。但是，当时我已经有了一个良好的心态。我知道我在聪明上比不过我的同学，但是我有一种能力，就是持续不断的努力。所以在我们班的毕业典礼上我说了这么一段话，到现在我的同学还能记得，我说：“大家都获得了优异的成绩，我是我们班的落后同学。但是我想让同学们放心，我决不放弃。你们五年干成的事情我干十年，你们十年干成的我干二十年，你们二十年干成的我干四十年”。（ 掌声）我对他们说：“如果实在不行，我会保持心情愉快、身体健康，到八十岁以后把你们送走了我再走。”（笑声掌声） 有一个故事说，能够到达金字塔顶端的只有两种动物，一是雄鹰，靠自己的天赋和翅膀飞了上去。我们这儿有很多雄鹰式的人物，很多同学学习不需要太努力就能达到高峰。很多同学后来可能很轻松地就能在北大毕业以后进入哈佛、耶鲁、牛津、剑桥这样的名牌大学继续深造。有很多同学身上充满了天赋，不需要学习就有这样的才能，比如说我刚才提到的我的班长王强，他的模仿能力就是超群的，到任何一个地方，听任何一句话，听一遍模仿出来的绝对不会两样。所以他在北大广播站当播音员当了整整四年。我每天听着他的声音，心头咬牙切齿充满仇恨。（笑声）所以，有天赋的人就像雄鹰。但是，大家也都知道，有另外一种动物，也到了金字塔的顶端。那就是蜗牛。蜗牛肯定只能是爬上去。从低下爬到上面可能要一个月、两个月，甚至一年、两年。在金字塔顶端，人们确实找到了蜗牛的痕迹。我相信蜗牛绝对不会一帆风顺地爬上去，一定会掉下来、再爬、掉下来、再爬。但是，同学们所要知道的是，蜗牛只要爬到金字塔顶端，它眼中所看到的世界，它收获的成就，跟雄鹰是一模一样的。（掌声）所以，也许我们在座的同学有的是雄鹰，有的是蜗牛。我在北大的时候，包括到今天为止，我一直认为我是一只蜗牛。但是我一直在爬，也许还没有爬到金字塔的顶端。但是只要你在爬，就足以给自己留下令生命感动的日子。（掌声） 我常常跟同学们说，如果我们的生命不为自己留下一些让自己热泪盈眶的日子，你的生命就是白过的。我们很多同学凭着优异的成绩进入了北大，但是北大绝不是你们学习的终点，而是你们生命的起点。在一岁到十八岁的岁月中间，你听老师的话、听父母的话，现在你真正开始了自己的独立生活。我们必须为自己创造一些让自己感动的日子，你才能够感动别人。我们这儿有富裕家庭来的，也有贫困家庭来的，我们生命的起点由不得你选择出生在富裕家庭还是贫困家庭，如果你生在贫困家庭，你不能说老爸给我收回去，我不想在这里待着。但是我们生命的终点是由我们自己选择的。我们所有在座的同学过去都走得很好，已经在十八岁的年龄走到了很多中国孩子的前面去，因为北大是中国的骄傲，也可以说是世界的骄傲。但是，到北大并不意味着你从此大功告成，并不意味着你未来的路也能走好，后面的五十年、六十年，甚至一百年你该怎么走，成为了每一个同学都要思考的问题。就本人而言，我觉得只要有两样东西在心中，我们就能成就自己的人生。 第一样叫做理想。我从小就有一种感觉，希望穿越地平线走向远方，我把它叫做“穿越地平线的渴望”。也正是因为这种强烈的渴望，使我有勇气不断地高考。当然，我生命中也有榜样。比如我有一个邻居，非常的有名，是我终生的榜样，他的名字叫徐霞客。当然，是五百年前的邻居。但是他确实是我的邻居，江苏江阴的，我也是江苏江阴的。因为崇拜徐霞客，直接导致我在高考的时候地理成绩考了九十七分。（掌声）也是徐霞客给我带来了穿越地平线的这种感觉，所以我也下定决心，如果徐霞客走遍了中国，我就要走遍世界。而我现在正在实现自己这一梦想。所以，只要你心中有理想，有志向，同学们，你终将走向成功。你所要做到的就是在这个过程要有艰苦奋斗、忍受挫折和失败的能力，要不断地把自己的心胸扩大，才能够把事情做得更好。 第二样东西叫良心。什么叫良心呢？就是要做好事，要做对得起自己对得起别人的事情，要有和别人分享的姿态，要有愿意为别人服务的精神。有良心的人会从你具体的生活中间做的事情体现出来，而且你所做的事情一定对你未来的生命产生影响。我来讲两个小故事，讲完我就结束我的讲话，已经占用了很长的时间。 第一个小故事。有一个企业家和我讲起他大学时候的一个故事，他们班有一个同学，家庭比较富有，每个礼拜都会带六个苹果到学校来。宿舍里的同学以为是一人一个，结果他是自己一天吃一个。尽管苹果是他的，不给你也不能抢，但是从此同学留下一个印象，就是这个孩子太自私。后来这个企业家做成功了事情，而那个吃苹果的同学还没有取得成功，就希望加入到这个企业家的队伍里来。但后来大家一商量，说不能让他加盟，原因很简单，因为在大学的时候他从来没有体现过分享精神。所以，对同学们来说在大学时代的第一个要点，你得跟同学们分享你所拥有的东西，感情、思想、财富，哪怕是一个苹果也可以分成六瓣大家一起吃。（掌声）因为你要知道，这样做你将来能得到更多，你的付出永远不会是白白付出的。 我再来讲一下我自己的故事。在北大当学生的时候，我一直比较具备为同学服务的精神。我这个人成绩一直不怎么样，但我从小就热爱劳动，我希望通过勤奋的劳动来引起老师和同学的的注意，所以我从小学一年级就一直打扫教室卫生。到了北大以后我养成了一个良好的习惯，每天为宿舍打扫卫生，这一打扫就打扫了四年。所以我们宿舍从来没排过卫生值日表。另外，我每天都拎着宿舍的水壶去给同学打水，把它当作一种体育锻炼。大家看我打水习惯了，最后还产生这样一种情况，有的时候我忘了打水，同学就说“俞敏洪怎么还不去打水”。（笑声）。但是我并不觉得打水是一件多么吃亏的事情。因为大家都是一起同学，互相帮助是理所当然的。同学们一定认为我这件事情白做了。又过了十年，到了九五年年底的时候新东方做到了一定规模，我希望找合作者，结果就跑到了美国和加拿大去寻找我的那些同学，他们在大学的时候都是我生命的榜样，包括刚才讲到的王强老师等。我为了诱惑他们回来还带了一大把美元，每天在美国非常大方地花钱，想让他们知道在中国也能赚钱。我想大概这样就能让他们回来。后来他们回来了，但是给了我一个十分意外的理由。他们说：“俞敏洪，我们回去是冲着你过去为我们打了四年水。”（掌声）他们说：“我们知道，你有这样的一种精神，所以你有饭吃肯定不会给我们粥喝，所以让我们一起回中国，共同干新东方吧。”才有了新东方的今天。（掌声） 人的一生是奋斗的一生，但是有的人一生过得很伟大，有的人一生过得很琐碎。如果我们有一个伟大的理想，有一颗善良的心，我们一定能把很多琐碎的日子堆砌起来，变成一个伟大的生命。但是如果你每天庸庸碌碌，没有理想，从此停止进步，那未来你一辈子的日子堆积起来将永远是一堆琐碎。所以，我希望所有的同学能把自己每天平凡的日子堆砌成伟大的人生。（掌声）

腾讯二面，这么少人，我还是被BS了

Find missing number in 4 billinon 32 bit integers

Problem
Given a file with 4 billion 32bit integers, how do you find an missing integer from the file? In other words, which integer didn't show up in this file? You are given only 16MB memory.( not using external sorting)
solution
Like 3 bits. Suppose my list has 0, 1, 2, 3, 4, 6, 7. (sorted for convenience of explanation, but that's not a requirement)
000
001
010
011
100
110
111

Now count the bits:
number of bits from most significant to least significant bit position:

msb lsb
zeros: 4 3 4
ones: 3 4 3

Since the most-significant bit position is missing a 1, the middle bit position is missing a 0, and the least-significant bit position is missing a 1, we get this number to fill in the gaps:
101, or 5 decimal.

code

#include <iostream>
#include <fstream>
using namespace std;

int main() {
 unsigned int number;
 int bits[2][32] = {0};
 ifstream numbers_file;
 numbers_file.open("numbers.txt");
 int i = 0;
 numbers_file >> number;
 while( ! numbers_file.eof()) {
   for (i =0; i<32; i++){
     int shifted = number>>i;
     int bit = shifted % 2;
     bits[bit][i]++;
   }
   numbers_file >> number;
 }
unsigned int missing = 0;
 for (i =31; i> -1; i--){
   if(bits[0][i]>bits[1][i]) missing++;
   missing = (missing<<1);
 }
 cout << "missing number is " << missing << endl;
}

面试很热门的抛鸡蛋问题

分析
Q: 只给你二个鸡蛋，你能上100层楼，你想知道鸡蛋的硬度。鸡蛋可能很硬或很脆弱，如果鸡蛋从第m层掉下而没破裂，而从第m+1层掉下就破裂了，那么这个鸡蛋的硬度就是m。你需要找出这个m和在最坏情况下最少试验次数。(经典鸡蛋问题)
A: 计算机学生可能会首先用第一个鸡蛋做二分搜索(O(logN))再用第二个递增做线性搜索（O(N)），最后必将用线性搜索结束因为用第二个鸡蛋时你无法确定最高一层。因此，问题变为如何使用第一个鸡蛋来减少线性搜索。
于是如果第一个蛋破裂在最高点我们要扔x-1次并且我们必须从x层高扔第一个蛋。现在如果第一个蛋的第一次扔没有破裂，如果第一个蛋在第二次扔破了我们要扔x-2次第二个蛋。假如16是答案，我需要扔16次才能找到答案。来验证一下是否可以从16层开始扔，首先从16层扔如果它破裂了，我们尝试所有其下的楼层从1到15；如果没破我们还能扔15次，于是我们将从32层(16+15+1)再扔。原因是如果它在32层破裂我们能尝试其下所有楼层从17到31最坏扔第二个蛋14次（总共能扔16次了）。如果32层并没破，我们还剩下能扔13次，依此类推得：
1 + 15 16 如果它在16层破裂，从1到15层最坏扔15次第二个蛋
1 + 14 31 如果它在31层破裂，从17到30层最坏扔14次第二个蛋
1 + 13 45.....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 在最后我们能轻易地做到因为我们有足够多扔的次数来完成任务
从上表我们能看到最佳的一个在最后一步将需要0次线性搜索。
能把上述规律写为: (1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.
令1+p=q上述式子变为q(q+1)/2>=100,对100解答得到q=14。
扔第一个蛋从层14，27，39，50，60，69，77，84，90，95，99，100直到它破裂，再开始扔第二个蛋。最坏情况只需14次。

代码
设计一个状态f[i][j]，表示有i层楼j个鸡蛋，最坏情况下要扔鸡蛋的次数。
由于一个鸡蛋扔下去就只有破和不破两种可能，所以状态转移就是f[i][j] = min(1+max(f[k-1][j-1], f[i-k][j]))，(1 <= k <= i)。如果要构造出一个可行解的话，稍微修改一下代码，记录下路径就应该可以了吧。

#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;

const int MAXN = 1001; // change it to the number you want
const int MAXM = 1001;

int n; // the number of floors
int m; // the number of eags
int f[MAXN][MAXM]; // the result

void init()
{
   memset(f, 0, sizeof(f));
   for (int j=1; j<MAXM; j++)
   {
       for (int i=1; i<MAXN; i++)
       {
           if (j == 1)
               f[i][j] = i;
           else{
               for (int k=1; k<=i; k++)
               {
                   int tmp = 1+max(f[k-1][j-1], f[i-k][j]);
                   if (f[i][j]==0 || f[i][j]>tmp)
                       f[i][j] = tmp;
               }
           }
       }
   }
}

int main()
{
   init();
   printf("Hey cin n, m\n");
   while (scanf("%d%d", &n, &m) != EOF)
       printf("%d\n", f[n][m]);
   return 0;
}

Nvidia took my first Interview of life

This is a phone interview, i really feel excited about it:-), i hope i could get a pretty offer from such an amazing company!

Understanding reference counting with Objective C

Let's start with retain and release; autorelease is really just a special case once you understand the basic concepts.

In Cocoa, each object keeps track of how many times it is being referenced (specifically, the NSObject base class implements this). By calling retain on an object, you are telling it that you want to up its reference count by one. By calling release, you tell the object you are letting go of it, and its reference count is decremented. If, after calling release, the reference count is now zero, then that object's memory is freed by the system.

The basic way this differs from malloc and free is that any given object doesn't need to worry about other parts of the system crashing because you've freed memory they were using. Assuming everyone is playing along and retaining/releasing according to the rules, when one piece of code retains and then releases the object, any other piece of code also referencing the object will be unaffected.

What can sometimes be confusing is knowing the circumstances under which you should call retain and release. My general rule of thumb is that if I want to hang on to an object for some length of time (if it's a member variable in a class, for instance), then I need to make sure the object's reference count knows about me. As described above, an object's reference count is incremented by calling retain. By convention, it is also incremented (set to 1, really) when the object is created with an "init" method. In either of these cases, it is my responsibility to call release on the object when I'm done with it. If I don't, there will be a memory leak.

Example of object creation:

NSString* s = [[NSString alloc] init]; // Ref count is 1
[s retain]; // Ref count is 2 - silly
// to do this after init
[s release]; // Ref count is back to 1
[s release]; // Ref count is 0, object is freed

Now for autorelease. Autorelease is used as a convenient (and sometimes necessary) way to tell the system to free this object up after a little while. From a plumbing perspective, when autorelease is called, the current thread's NSAutoreleasePool is alerted of the call. The NSAutoreleasePool now knows that once it gets an opportunity (after the current iteration of the event loop), it can call release on the object. From our perspective as programmers, it takes care of calling release for us, so we don't have to (and in fact, we shouldn't).

What's important to note is that (again, by convention) all object creation class methods return an autoreleased object. For example, in the following example, the variable "s" has a reference count of 1, but after the event loop completes, it will be destroyed.

NSString* s = [NSString stringWithString:@"Hello World"];

If you want to hang onto that string, you'd need to call retain explicitly, and then explicitly release it when you're done.

Consider the following (very contrived) bit of code, and you'll see a situation where autorelease is required:

- (NSString*)createHelloWorldString
{
NSString* s = [[NSString alloc] initWithString:@"Hello World"];

// Now what? We want to return s, but we've upped its reference count.
// The caller shouldn't be responsible for releasing it, since we're the
// ones that created it. If we call release, however, the reference
// count will hit zero and bad memory will be returned to the caller.
// The answer is to call autorelease before releasing the string. By
// explicitly calling autorelease, we pass the responsibility for
// releasing the string on to the thread's NSAutoreleasePool, which will
// happen at some later. The consequence is that the returned string
// will still be valid for the caller of this function.
return [[s autorelease] release];
}

I realize all of this is a bit confusing - at some point, though, it will click. Here are a few references to get you going:

* Apple's introduction to memory management.
* Cocoa Programming for Mac OS X (3rd Edition), by Aaron Hillegas - a very well written book will lots of great examples. It reads like a tutorial.
* If you're truly diving in, you could head to Big Nerd Ranch. This is a training facility run by Aaron Hillegas - the author of the book mentioned above. I attended the Intro to Cocoa course there several years ago, and it was a great way to learn.

9 Tips for the aspiring Emacs playboy

Introduction

I consider myself a beginning Lisper. I've been developing my software in Emacs for 8 months now. At first, I was clumsy at it. Emacs can be difficult and daunting. The terminology is different from what I'm used to, the key bindings are different, and there are just so many commands, configurations, and modes. But I've persevered and I now find myself quite nimble with key bindings and structured editing. And yet there's still more to learn.

The subject of what to learn is treated in many online tutorials and printed books. But here, now, I thought I'd share some tips I use to keep the key bindings in my head from being garbage collected.

1. Post up a cheat sheet

Create your own cheat sheet with ten key bindings you'd like to learn. No more than 10. Don't burden yourself with a gigantic list you'll have to search through. You won't be able to find them quickly enough, and you'll stop referring to the sheet.

Make it a point to use bindings from the cheat sheet while you code.

At first, your cheat sheet will have the basic commands you need to master. But it will evolve as you do . . .

2. Don't use the mouse

The mouse is a crutch for the beginner. It will keep you from learning keyboard commands. Using the keyboard will let you edit faster than the mouse ever can.

Get rid of the tool bar (tool-bar-mode -1) and the menu bar (menu-bar-mode -1).

Don't touch the mouse. If you find yourself using the mouse too much, open up emacs in a terminal instead of in X. When you find yourself reaching for the mouse, think of a way to use the keyboard to get to where you want. In no time, you'll be flying around the text like a crazy rocket-powered hamster on steroids instead of some wimpy mouse.

3. Read other people's .emacs file

Lots of people post their .emacs file for bragging/demonstration purposes. These often have great tips/insights into a configuration/mode that you didn't know about. This is like getting a look directly into the brain of an experienced Emacs user. Cut and paste and read the comments.

4. Write down any interesting commands you discover

While perusing help, reading .emacs files, loitering in the newsgroups, or surfing the web, you'll invariably find an Emacs command that you'll want to remember. You won't remember it unless you write it down. Sure, you may remember some, but not all. Keep a list of key bindings you don't want to forget. You will not be able to find it again.

5. Update your cheat sheet

Ok, so you've got a cheat sheet. Now what? After a week or two of using a single, ten item cheat sheet, go through the sheet and decide which key bindings you've graduated from.

For each item on you cheat sheet, ask yourself these questions:

Do you use it often enough not to forget it?

Do you want to forget it?

Will you remember it without the cheat sheet?

Do you remember what it does?

When you've whittled down your sheet so that it again contains only those key bindings that you want to remember but don't, add some more from the list of interesting commands you've been keeping. But don't exceed a total list size of ten!

6. Keep your key bindings standard

There are a lot of key bindings that are universally accepted as standard. When you're still learning, you won't know which those are, and you'll destroy any chance you have of fluency in another Emacs window if you change them. There's nothing worse than sitting down at a terminal and being totally lost with the commands because you're used to rebinding most of them. You might even do something awful.

It's like being parachuted into a foreign country where "Hello, I come in peace." means "Your mother is ugly but she's good in bed." But at the same time, you might use some commands so much you want to rebind them to something more useful. It's a dilemma but I suggest keeping as many of the original key bindings as possible, especially at first.

7. Use help

Online help is a great help (wow, really bad pun). Some help commands that you might find helpful (not again):

• describe-key (C-h k): Asks you to strike a keystroke and describes the command it is bound to.
• describe-bindings (C-h b): Lists all of you key bindings.
• command-apropos (C-h a): Search all of the commands in the system, and gives you a brief description of each matching command(with its key binding).
• view-order-manuals (C-h RET): View all help commands

Also, watch when you you type a command using M-x. If there is a key binding for it, it will tell it to you.

8. Experiment

In order to strengthen the human-Emacs symbiotic bond, you should experiment with different editing commands and editing modes. Most text editors only offer a couple of ways of navigating text. Here are some common ones: Arrow Keys, Home/End keys, PageUp/PageDown, and find. One of the strengths of Emacs is that you can treat the same text differently depending on what command you use. For instance, you treat it as characters with C-f and C-b. But you treat it as words with M-f and M-b. You treat it as s-exprs with C-M-f and C-M-b. Etc.

In order to know when it is best to use which command, experimentation is your best option. Try out different commands and learn their strengths and weaknesses.

9. Create keyboard macros

Keyboard macros are a great thing to learn in their own right, but they can help you learn commands like a pro. When recording your macros, you have to think: "How can I do this so that this command will work perfectly a hundred times?". The thought process you have to go through to compose those commands will reinforce all of the possible ways to perform an action.

王泛森院士-如果让我重做一次研究生.

如果让我重做一次研究生......
    在所里碰到刚从美国读完博士回来的同事，因为他们刚离开博士生的阶段，比较有一些自己较独特的想法，我就问他：「如果你讲这个问题，准备要贡
献什么？」……
一、研究生与大学生的区别


首先跟大家说明一下研究生和大学生的区别。大学生基本上是来接受学问、接受知识的，然而不管是对于硕士时期或是博士时期的研究而言，都应该准备要开始制
造新的知识，我们在美国得到博士学位时都会领到看不懂的毕业证书，在一个偶然的机会下，我问了一位懂拉丁文的人，上面的内容为何？他告诉我：「里头写的
是恭喜你对人类的知识有所创新，因此授予你这个学位。」在中国原本并没有博硕士的学历，但是在西方他们原来的用意是，恭贺你已经对人类普遍的知识有所创
新，这个创新或大或小，都是对于普遍的知识有所贡献。这个创新不会因为你做本土与否而有所不同，所以第一个我们必须要很用心、很深刻的思考，大学生和研
究生是不同的。


（一）选择自己的问题取向，学会创新


你一旦是研究生，你就已经进入另一个阶段，不只是要完全乐在其中，更要从而接受各种有趣的知识，进入制造知识的阶段，也就是说你的论文应该有所创新。由
接受知识到创造知识，是身为一个研究生最大的特色，不仅如此，还要体认自己不再是个容器，等着老师把某些东西倒在茶杯里，而是要开始逐步发展和开发自
己。做为研究生不再是对于各种新奇的课照单全收，而是要重视问题取向的安排，就是在硕士或博士的阶段里面，所有的精力、所有修课以及读的书里面都应该要
有一个关注的焦点，而不能像大学那般漫无目标。大学生时代是因为你要尽量开创自己接受任何东西，但是到了硕士生和博士生，有一个最终的目的，就是要完成
论文，那篇论文是你个人所有武功的总集合，所以这时候必须要有个问题取向的学习。


（二）尝试跨领域研究，主动学习


提出一个重要的问题，跨越一个重要的领域，将决定你未来的成败。我也在台大和清华教了十几年的课，我常常跟学生讲，选对一个领域和选对一个问题是成败的
关键，而你自己本身必须是带着问题来探究无限的学问世界，因为你不再像大学时代一样泛滥无所归。所以这段时间内，必须选定一个有兴趣与关注的主题为出发
点，来探究这些知识，产生有机的循环。由于你是自发性的对这个问题产生好奇和兴趣，所以你的态度和大学部的学生是截然不同的，你慢慢从被动的接受者变成
是一个主动的探索者，并学会悠游在这学术的领域。


我举一个例子，我们的中央研究院院长李远哲先生，得了诺贝尔奖。他曾经在中研院的周报写过几篇文章，在他的言论集里面，或许各位也可以看到，他反复提到
他的故事。他是因为读了一个叫做马亨教授的教科书而去美国柏克莱大学念书，去了以后才发现，这个老师只给他一张支票，跟他说你要花钱你尽量用，但是从来
不教他任何东西。可是隔壁那个教授，老师教很多，而且每天学生都是跟着老师学习。他有一次就跟那个老师抱怨：「那你为什么不教我点东西呢？」那个老师就
说：「如果我知道结果，那我要你来这边念书做什么？我就是因为不知道，所以要我们共同探索一个问题、一个未知的领域。」他说其实这两种教法都有用处，但
是他自己从这个什么都不教他，永远碰到他只问他「有没有什么新发现」的老师身上，得到很大的成长。所以这两方面都各自蕴含深层的道理，没有所谓的好坏，
但是最好的方式就是将这两个方式结合起来。我为什么讲这个故事呢？就是强调在这个阶段，学习是一种「 self-help 」，并且是在老师的引导下学
习「 self-help 」，而不能再像大学时代般，都是纯粹用听的，这个阶段的学习要基于对研究问题的好奇和兴趣，要带着一颗热忱的心来探索这个领
域。


然而研究生另外一个重要的阶段就是 Learn how to learn ，不只是学习而已，而是学习如何学习，不再是要去买一件很漂亮的衣服，而是
要学习拿起那一根针，学会绣出一件漂亮的衣服，慢慢学习把目标放在一个标准上，而这一个标准就是你将来要完成硕士或博士论文。如果你到西方一流的大学去
读书，你会觉得我这一篇论文可能要和全世界做同一件问题的人相比较。我想即使在***也应该要有这样的心情，你的标准不能单单只是放在旁边几个人而已，
而应该是要放在领域的普遍人里面。你这篇文章要有新的东西，才算达到的标准，也才符合到我们刚刚讲到那张拉丁文的博士证书上面所讲的，有所贡献与创
新。

二、一个老师怎么训练研究生


第二个，身为老师你要怎么训练研究生。我认为人文科学和社会科学的训练，哪怕是自然科学的训练，到研究生阶段应该更像师徒制，所以来自个人和老师、个人
和同侪间密切的互动和学习是非常重要的，跟大学部坐在那边单纯听课，听完就走人是不一样的，相较之下你的生活应该要和你所追求的知识与解答相结合，并且
你往后的生活应该或多或少都和这个探索有相关。


（一）善用与老师的伙伴关系，不断 Research


我常说英文 research 这个字非常有意义， search 是寻找，而 research 是再寻找，所以每个人都要 research ，不
断的一遍一遍再寻找，并进而使你的生活和学习成为一体。中国近代兵学大师蒋百里在他的兵学书中曾说：「生活条件要跟战斗条件一致，近代欧洲凡生活与战斗
条件一致者强，凡生活与战斗条件不一致者弱。」我就是藉由这个来说明研究生的生活，你的生活条件与你的战斗条件要一致，你的生活是跟着老师与同学共同成
长的，当中你所听到的每一句话，都可能带给你无限的启发。


回想当时我在美国念书的研究生生活，只要随便在楼梯口碰到任何一个人，他都有办法帮忙解答你语言上的困难，不管是英文、拉丁文、德文、希腊文 ……
等。所以能帮助解决问题的不单只是你的老师，还包括所有同学以及学习团体。你的学习是跟生活合在一起的。当我看到有学生呈现被动或是懈怠的时候，我就会
用毛泽东的「革命不是请客吃饭！」来跟他讲：「作研究生不是请客吃饭。」


（二）藉由大量阅读和老师提点，进入研究领域


怎样进入一个领域最好，我个人觉得只有两条路，其中一条就是让他不停的念书、不停的报告，这是进入一个陌生的领域最快，又最方便的方法，到最后不知不觉
学生就会知道这个领域有些什么，我们在不停念书的时候常常可能会沉溺在细节里不能自拔，进而失去全景，导致见树不见林，或是被那几句英文困住，而忘记全
局在讲什么。藉由学生的报告，老师可以讲述或是厘清其中的精华内容，经由老师几句提点，就会慢慢打通任督二脉，逐渐发展一种自发学习的能力，同时也知道
碰到问题可以看哪些东西。就像是我在美国念书的时候，我修过一些我完全没有背景知识的国家的历史，所以我就不停的念书、不停***着自己吸收，而老师也
只是不停的开书目，运用这样的方式慢慢训练，有一天我不再研究它时，我发现自己仍然有自我生产及蓄发的能力，因为我知道这个学问大概是什么样的轮廓，碰
到问题也有能力可以去查询相关的资料。所以努力让自己的学习产生自发的延展性是很重要的。


（三）循序渐进地练习论文写作


到了硕士或博士最重要的一件事，是完成一篇学位论文，而不管是硕士或博士论文，其规模都远比你从小学以来所受的教育、所要写的东西都还要长得多，虽然我
不知道教育方面的论文情况是如何，但是史学的论文都要写二、三十万字，不然就是十几二十万字。写这么大的一个篇幅，如何才能有条不紊、条理清楚，并把整
体架构组织得通畅可读？首先，必须要从一千字、五千字、一万字循序渐进的训练，先从少的慢慢写成多的，而且要在很短的时间内训练到可以从一万字写到十万
字。这么大规模的论文谁都写得出来，问题是写得好不好，因为这么大规模的写作，有这么许多的脚注，还要注意首尾相映，使论述一体成型，而不是散落一地的
铜钱；是一间大礼堂，而不是一间小小分割的阁楼。为了完成一个大的、完整的、有机的架构模型，必须要从小规模的篇幅慢慢练习，这是一个最有效的办法。


因为受计算机的影响，我发现很多学生写文章能力都大幅下降。写论文时很重要的一点是，文笔一定要清楚，不要花俏、不必漂亮，「清楚」是最高指导原则，经
过慢慢练习会使你的文笔跟思考产生一致的连贯性。我常跟学生讲不必写的花俏，不必展现你散文的才能，因为这是学术论文，所以关键在于要写得非常清楚，如
果有好的文笔当然更棒，但那是可遇不可求的，文彩像个人的生命一样，英文叫 style ， style 本身就像个人一样带有一点点天生。因此最重要
的还是把内容陈述清楚，从一万字到最后十万字的东西，都要架构井然、论述清楚、文笔清晰。
我在念书的时候，有一位欧洲史、英国史的大师 Lawrence Stone ，他目前已经过世了，曾经有一本书访问十位最了不起的史学家，我记得他在
访问中说了一句非常吸引人注意的话，他说他英文文笔相当好，所以他一辈子没有被退过稿。因此文笔清楚或是文笔好，对于将来文章可被接受的程度有举足轻重
的地位。内容非常重要，有好的表达工具更是具有加分的作用，但是这里不是讲究漂亮的 style ，而是论述清楚。


三、研究生如何训练自己


（一）尝试接受挑战，勇于克服


研究生如何训练自己？就是每天、每周或每个月给自己一个挑战，要每隔一段时间就给自己一个挑战，挑战一个你做不到的东西，你不一定要求自己每次都能顺利
克服那个挑战，但是要努力去尝试。我在我求学的生涯中，碰到太多聪明但却一无所成的人，因为他们很容易困在自己的障碍里面，举例来说，我在普林斯顿大学
碰到一个很聪明的人，他就是没办法克服他给自己的挑战，他就总是东看西看，虽然我也有这个毛病，可是我会定期给我自己一个挑战，例如：我会告诉自己，在
某一个期限内，无论如何一定要把这三行字改掉，或是这个礼拜一定要把这篇草稿写完，虽然我仍然常常写不完，但是有这个挑战跟没这个挑战是不一样的，因为
我挑战三次总会完成一次，完成一次就够了，就足以表示克服了自己，如果觉得每一个礼拜的挑战，可行性太低，可以把时间延长为一个月的挑战，去挑战原来的
你，不一定能做到的事情。不过也要切记，硕士生是刚开始进入这一个领域的新手，如果一开始问题太小，或是问题大到不能控制，都会造成以后研究的困难。


（二）论文的写作是个训练过程，不能苛求完成精典之作


各位要记得我以前的老师所说的一句话：「硕士跟博士是一个训练的过程，硕士跟博士不是写经典之作的过程。」我看过很多人，包括我的亲戚朋友们，他之所以
没有办法好好的完成硕士论文，或是博士论文，就是因为他把它当成在写经典之作的过程，虽然事实上，很多人一生最好的作品就是硕士论文或博士论文，因为之
后的时间很难再有三年或六年的时间，沉浸在一个主题里反复的耕耘，当你做教授的时候，像我今天被行政缠身，你不再有充裕的时间好好探究一个问题，尤其做
教授还要指导学生、上课，因此非常的忙碌，所以他一生最集中又精华的时间，当然就是他写博士、或是硕士论文的时候，而那一本成为他一生中最重要的著作也
就一点都不奇怪了。


不一定要刻意强求，要有这是一个训练过程的信念，应该清楚知道从哪里开始，也要知道从哪里放手，不要无限的追下去。当然我不是否认这个过程的重要性，只
是要调整自己的心态，把论文的完成当成一个目标，不要成为是一种的心理障碍或是心理负担。这方面有太多的例子了，我在普林斯顿大学念书的时候，那边旧书
摊有一位非常博学多文的旧书店老板，我常常赞叹的对他说：「你为什么不要在大学做教授。」他说：「因为那篇博士论文没有写完。」原因在于他把那个博士论
文当成要写一本经典，那当然永远写不完。如果真能写成经典那是最好，就像美丽新境界那部电影的男主角 John Nash 一样，一生最大的贡献就是博
士那二十几页的论文，不过切记不要把那个当作是目标，因为那是自然而然形成的，应该要坚定的告诉自己，所要完成的是一份结构严谨、论述清楚与言之有物的
论文，不要一开始就期待它是经典之作。如果你期待它是经典之作，你可能会变成我所看到的那位旧书摊的老板，至于我为什么知道他有那么多学问，是因为那时
候我在找一本书，但它并没有在旧书店里面，不过他告诉我：「还有很多本都跟他不相上下。」后来我对那个领域稍稍懂了之后，证明确实如他所建议的那般。一
个旧书店的老板精熟每一本书，可是他就是永远无法完成，他梦幻般的学位论文，因为他不知道要在哪里放手，这一切都只成为空谈。


（三）论文的正式写作


1. 学习有所取舍
到了写论文的时候，要能取也要能舍，因为现在信息爆炸，可以看的书太多，所以一定要建构一个属于自己的知识树，首先，要有一棵自己的知识树，才能在那棵
树挂相关的东西，但千万不要不断的挂不相关的东西，而且要慢慢的舍掉一些挂不上去的东西，再随着你的问题跟关心的领域，让这棵知识树有主干和枝叶。然而
这棵知识树要如何形成？第一步你必须对所关心的领域中，有用的书籍或是数据非常熟悉。


2. 形成你的知识树
我昨天还请教林毓生院士，他今年已经七十几岁了，我告诉他我今天要来作演讲，就问他：「你如果讲这个题目你要怎么讲？」他说：「只有一点，就是那重要的
五、六本书要读好几遍。」因为林毓生先生是海耶克，还有几位近代思想大师在芝加哥大学的学生，他们受的训练中很重要的一部份是精读原典。这句话很有道
理，虽然你不可能只读那几本重要的书，但是那五、六本书将逐渐形成你知识树的主干，此后的东西要挂在上面，都可以参照这一个架构，然后把不相干的东西暂
放一边。生也有涯，知也无涯，你不可能读遍天下所有的好书，所以要学习取舍，了解自己无法看遍所有有兴趣的书，而且一但看遍所有有兴趣的书，很可能就会
落得普林斯顿街上的那位旧书店的老板一般，因为阅读太多不是自己所关心的领域的知识，它对于你来说只是一地的散钱。


3. 掌握工具
在这个阶段一定要掌握语文与合适的工具。要有一个外语可以非常流畅的阅读，要有另外一个语文至少可以看得懂文章的标题，能学更多当然更好，但是至少要有
一个语文，不管是英文、日文、法文 …… 等，一定要有一个语文能够非常流畅的阅读相关书籍，这是起码的前提。一旦这个工具没有了，你的视野就会因此大
受限制，因为语文就如同是一扇天窗，没有这个天窗你这房间就封闭住了。为什么你要看得懂标题？因为这样才不会有重要的文章而你不知道，如果你连标题都看
不懂，你就不知道如何找人来帮你或是自己查相关的数据。其它的工具，不管是统计或是其它的任何工具，你也一定要多掌握，因为你将来没有时间再把这样的工
具学会。


4. 突破学科间的界线
应该要把跨学科的学习当作是一件很重要的事，但是跨学科涉及到的东西必须要对你这棵知识树有帮助，要学会到别的领域稍微偷打几枪，到别的领域去摄取一些
概念，对于本身关心的问题产生另一种不同的启发，可是不要泛滥无所归。为什么要去偷打那几枪？近几十年来，人们发现不管是科学或人文，最有创新的部份是
发生在学科交会的地方。为什么会如此？因为我们现在的所有学科大部分都在西方十九世纪形成的，而中国再把它转借过来。十九世纪形成这些知识学科的划分的
时候，很多都带有那个时代的思想跟学术背景，比如说，中研院的李院长的专长就是物理化学，他之所以得诺贝尔奖就是他在物理和化学的交界处做工作。像诺贝
尔经济奖，这二十年来所颁的奖，如果在传统的经济学奖来看就是旁门走道，古典经济学岂会有这些东西，甚至心理学家也得诺贝尔经济奖，连 John
Nash 这位数学家也得诺贝尔经济奖，为什么？因为他们都在学科的交界上，学科跟学科、平台跟平台的交界之处有所突破。在平台本身、在学科原本最核心
的地方已经 search 太多次了，因此不一定能有很大的创新，所以为什么跨领域学习是一件很重要的事情。
常常一篇硕士论文或博士论文最重要、最关键的，是那一个统摄性的重要概念，而通常你在本学科里面抓不到，是因为你已经泡在这个学科里面太久了，你已经拿
着手电筒在这个小仓库里面照来照去照太久了，而忘了还有别的东西可以更好解释你这些材料的现象，不过这些东西可遇而不可求。 John Nash 这一
位数学家为什么会得诺贝尔数学奖？为什么他在赛局理论的博士论文，会在数十年之后得诺贝尔经济奖？因为他在大学时代上经济学导论的课，所以他认为数学可
以用在经济方面来思考，而这个东西在一开始，他也没有想到会有这么大的用处。他是在数学和经济学的知识交界之处做突破。有时候在经济学这一个部分没有大
关系，在数学的这一个部分也没有大关系，不过两个加在一起，火花就会蹦出来。


5. 论文题目要有延展性
对一个硕士生或博士生来说，如果选错了题目，就是失败，题目选对了，还有百分之七十胜利的机会。这个问题值得研一、博一的学生好好思考。你的第一年其实
就是要花在这上面，你要不断的跟老师商量寻找一个有意义、有延展性的问题，而且不要太难。我在国科会当过人文处长，当我离开的时候，每次就有七千件申请
案，就有一万四千个袋子，就要送给一万四千个教授审查。我当然不可能看那么多，可是我有个重要的任务，就是要看申诉。有些申诉者认为：「我的研究计划很
好，我的著作很好，所以我来申诉。」申诉通过的大概只有百分之十，那么我的责任就是在百分之九十未通过的案子正式判决前，再拿来看一看。有几个印象最深
常常被拿出来讨论的，就是这个题目不必再做了、这个题目本身没有发展性，所以使我更加确认选对一个有意义、有延展性、可控制、可以经营的题目是非常重要
的。
我的学生常常选非常难的题目，我说你千万不要这样，因为没有人会仔细去看你研究的困难度，对于难的题目你要花更多的时间阅读史料，才能得到一点点东西；
要挤很多东西，才能筛选出一点点内容，所以你最好选择一个难易适中的题目。
我写过好几本书，我认为我对每一本书的花的心力都是一样，虽然我写任何东西我都不满意，但是在过程中我都绞尽脑汁希望把他写好。目前为止很多人认为我最
好的书，是我二十几岁刚到史语所那一年所写的那本书。我在那本书花的时间并不长，那本书的大部分的稿子，是我和许添明老师同时在当兵的军营里面写的，而
且还是用我以前旧的笔记写的。大陆这些年有许多出版社，反复要求出版我以前的书，尤其是这一本，我说：「不行。」因为我用的是我以前的读书笔记，我怕引
文有错字，因为在军队营区里面随时都要出操、随时就要集合，手边又没有书，怎么可能好好的去核对呢？而如果要我重新校正一遍，又因为引用太多书，实在没
有力气校正。


为什么举这个例子呢？我后来想一想，那本书之所以比较好，可能是因为那个题目可延展性大，那个题目波澜起伏的可能性大。很多人都认为，我最好的书应该是
剑桥大学出的那一本，不过我认为我最好的书一定是用中文写的，因为这个语文我能掌握，英文我没办法掌握得出神入化。读、写任何语文一定要练习到你能带着
三分随意，那时候你才可以说对于这一个语文完全理解与精熟，如果你还无法达到三分的随意，就表示你还在摸索。


回到我刚刚讲的，其实每一本书、每一篇论文我都很想把它写好。但是有些东西没办法写好，为什么？因为一开始选择的题目不够好。因此唯有选定题目以后，你
的所有训练跟努力才有价值。我在这里建议大家，选题的工作要尽早做，所选的题目所要处理的材料最好要集中，不要太分散，因为硕士生可能只有三年、博士生
可能只有五年，如果你的材料太不集中，读书或看数据可能就要花掉你大部分的时间，让你没有余力思考。而且这个题目要适合你的性向，如果你不会统计学或讨
厌数字，但却选了一个全都要靠统计的论文，那是不可能做得好。
6. 养成遵照学术格式的写作习惯


另一个最基本的训练，就是平时不管你写一万字、三万字、五万字都要养成遵照学术规范的习惯，要让他自然天成，就是说你论文的脚注、格式，在一开始进入研
究生的阶段就要培养成为你生命中的一个部份，如果这个习惯没有养成，人家就会觉得这个论文不严谨，之后修改也要花很多时间，因为你的论文规模很大，可能
几百页，如果一开始弄错了，后来再重头改到尾，一定很耗时费力，因此要在一开始就养成习惯，因为我们是在写论文而不是在写散文，哪一个逗点应该在哪里、
哪一个书名号该在哪里、哪一个地方要用引号、哪一个要什么标点符号，都有一定的规定，用中文写还好，用英文有一大堆简称。在 1960 年代***知识
还很封闭的时候，有一个人从美国回来就说：「美国有个不得了的情形，因为有一个人非常不得了。」有人问他为什么不得了，他说：「因为这个人的作品到处被
引用。」他的名字就叫 ibid 。所谓 ibid 就是同前作者，这个字是从拉丁文发展出来的，拉丁文有一大堆简称，像 et. al. 就是两人共
同编的。英文有一本 The Chicago Manual of Style 就是专门说明这一些写作规范。各位要尽早学会中英文的写作规范，慢慢练
习，最后随性下笔，就能写出符合规范的文章。


7. 善用图书馆
图书馆应该是研究生阶段最重要的地方，不必读每一本书，可是要知道有哪些书。我记得我做学生时，新进的书都会放在图书馆的墙上，而身为学生最重要的事
情，就是要把书名看一看。在某些程度上知道书皮就够了，但是这仍和打计算机是不一样的，你要实际上熟悉一下那本书，摸一下，看一眼目录。我知道现在从计
算机就可以查到书名，可是我还是非常珍惜这种定期去 browse 新到的书的感觉，或去看看相关领域的书长成什么样子。中研院有一位院士是哈佛大学信
息教授，他告诉我他在创造力最高峰的时候，每个礼拜都到他们信息系图书室里，翻阅重要的信息期刊。所以图书馆应该是身为研究生的人们，最熟悉的地方。不
过切记不重要的不要花时间去看，你们生活在信息泛滥的时代，跟我生长在信息贫乏的时代是不同的，所以生长在这一个时代的你，要能有所取舍。我常常看我的
学生引用一些三流的论文，却引得津津有味，我都替他感到难过，因为我强调要读有用、有价值的东西。


8. 留下时间，精致思考
还要记得给自己保留一些思考的时间。一篇论文能不能出神入化、能不能引人入胜，很重要的是在现象之上作概念性的思考，但我不是说一定要走理论的路线，而
是提醒大家要在一般的层次再提升两三步， conceptualize 你所看到的东西。真切去了解，你所看到的东西是什么？整体意义是什么？整体的轮
廓是什么？千万不要被枝节淹没，虽然枝节是你最重要的开始，但是你一天总也要留一些时间好好思考、慢慢沉淀。 conceptualize 是一种非常
难教的东西，我记得我念书时，有位老师信誓旦旦说要开一门课，教学生如何 conceptualize ，可是从来都没开成，因为这非常难教。我要提醒
的是，在被很多材料和枝节淹没的时候，要适时跳出来想一想，所看到的东西有哪些意义？这个意义有没有广泛连结到更大层面的知识价值。


傅斯年先生来到***以后，同时担任中央研究院历史语言研究所的所长及台大的校长。台大有个傅钟每小时钟声有二十一响、敲二十一次。以前有一个人，写了
一本书叫《钟声二十一响》，当时很轰动。他当时对这二十一响解释是说：因为台大的学生都很好，所以二十一响是欢迎国家元首二十一响的礼炮。不久前我发现
台大在每一个重要的古迹下面竖一个铜牌，我仔细看看傅钟下的解释，才知道原来是因为傅斯年当台大校长的时候，曾经说过一句话：「人一天只有二十一个小
时，另外三小时是要思考的。」所以才叫二十一响。我觉得这句话大有道理，可是我觉得三小时可能太多，因为研究生是非常忙的，但至少每天要留个三十分钟、
一小时思考，想一想你看到了什么？学习跳到比你所看到的东西更高一点的层次去思考。


9. 找到学习的楷模
我刚到美国念书的时候，每次写报告头皮就重的不得了，因为我们的英文报告三、四十页，一个学期有四门课的话就有一百六十页，可是你连脚注都要从头学习。
后来我找到一个好办法，就是我每次要写的时候，把一篇我最喜欢的论文放在旁边，虽然他写的题目跟我写的都没关系，不过我每次都看他如何写，看看他的注
脚、读几行，然后我就开始写。就像最有名的男高音 Pavarotti 唱歌剧的时候都会捏着一条手帕，因为他说：「上舞台就像下地狱，太紧张了。」他
为了克服紧张，他有习惯性的动作，就是捏着白手帕。我想当年那一篇论文抽印本就像是我的白手帕一样，能让我开始好好写这篇报告，我学习它里面如何思考、
如何构思、如何照顾全体、如何用英文作脚注。好好的把一位大师的作品读完，开始模仿和学习他，是入门最好的方法，逐步的，你也开始写出自己的东西。我也
常常鼓励我的学生，出国半年或是一年到国外看看。像现在国科会有各式各样的机会，可以增长眼界，可以知道现在的餐馆正在卖些什么菜，回来后自己要作菜也
才知道要如何着手。


四、用两条腿走路，练习培养自己的兴趣


最后还有一点很重要的，就是我们的人生是两只脚，我们不是靠一只脚走路。做研究生的时代，固然应该把所有的心思都放在学业上，探索你所要探索的那些问
题，可是那只是你的一只脚，另外还有一只脚是要学习培养一、两种兴趣。很多人后来会发现他的右脚特别肥重（包括我自己在内），也就是因为忘了培养左脚。
很多很有名的大学者最后都陷入极度的精神困扰之中，就是因为他只是培养他的右脚，他忘了培养他的左脚，他忘了人生用两只脚走路，他少了一个小小的兴趣或
嗜好，用来好好的调解或是排遣自己。
去年夏天，香港《亚洲周刊》要访问我，我说：「我不想接受访问，我不是重要的人。」可是后来他们还是把一个简单的对话刊出来了，里面我只记得讲了一段
话：做一个研究生或一个学者，有两个感觉最重要 -- 责任感与罪恶感。你一定要有很大的责任感，去写出好的东西，如果责任感还不够强，还要有一个罪恶
感，你会觉得如果今天没有好好做几个小时的工作的话，会有很大的罪恶感。除非是了不得的天才，不然即使爱因斯坦也是需要很努力的。很多很了不得的人，他
只是把所有的努力集中在一百页里面，他花了一千小时和另外一个人只花了十个小时，相对于来说，当然是那花一千个小时所写出来的文章较好。所以为什么说要
赶快选定题目？因为如果太晚选定一个题目，只有一年的时间可以好好耕耘那个题目，早点选定可以有二、三年耕耘那个题目，是三年做出的东西好，还是一年的
东西好？如果我们的才智都一样的话，将三年的努力与思考都灌在上面，当然比一年还要好。


五、营造卓越的大学，分享学术的氛围


现在很多人都在讨论，何谓卓越的大学？我认为一个好的大学，学校生活的一大部份，以及校园的许多活动，直接或间接都与学问有关，同学在咖啡厅里面谈论
的，直接或间接也都会是学术相关的议题。教授们在餐厅里面吃饭，谈的是「有没有新的发现」？或是哪个人那天演讲到底讲了什么重要的想法？一定是沉浸在这
种氛围中的大学，才有可能成为卓越大学。那种交换思想学识、那种互相教育的气氛不是花钱就有办法获得的。我知道钱固然重要，但不是唯一的东西。一个卓越
的大学、一个好的大学、一个好的学习环境，表示里面有一个共同关心的焦点，如果没有的话，这个学校就不可能成为好的大学.

表达我一直的想法，日后努力实践！

记住以下几点：
1，对于数学分析的学习，勤奋永远比天分重要。
2，学数学分析不难，难得是长期坚持做题和不遗余力的博览群书。
3，别指望第一遍就能记住和掌握什么，请看第二遍，第三遍，…,第阿列夫遍。
4，看得懂的仔细看，看不懂的硬着头皮看。
5，课本一个字一个字的看完，至少再看一本参考书，尽量做一本习题集。
6，开始前三遍，一本书看三遍效果好于三本书看一遍；第四遍开始相反。
7，经常回头看看自己走过的路

以上几点请在学其他课程时参考。

Model-View-Controller

Context

Application presents content to users in numerous pages containing various data. Also, the engineering team responsible for designing, implementing, and maintaining the application is composed of individuals with different skill sets.

Problem

Now, more than ever, enterprise applications need to support multiple types of users with multiple types of interfaces. For example, an online store may require an HTML front for Web customers, a WML front for wireless customers, a Java^TM (JFC) / Swing interface for administrators, and an XML-based Web service for suppliers

When developing an application to support a single type of client, it is sometimes beneficial to interweave data access and business rules logic with interface-specific logic for presentation and control. Such an approach, however, is inadequate when applied to enterprise systems that need to support multiple types of clients. Different applications need to be developed, one to support each type of client interface. Non-interface-specific code is duplicated in each application, resulting in duplicate efforts in implementation (often of the copy-and-paste variety), as well as testing and maintenance. The task of determining what to duplicate is expensive in itself, since interface-specific and non-interface-specific code are intertwined. The duplication efforts are inevitably imperfect. Slowly, but surely, applications that are supposed to provide the same core functionality evolve into different systems.

Forces

• The same enterprise data needs to be accessed when presented in different views: e.g. HTML, WML, JFC/Swing, XML
• The same enterprise data needs to be updated through different interactions: e.g. link selections on an HTML page or WML card, button clicks on a JFC/Swing GUI, SOAP messages written in XML
• Supporting multiple types of views and interactions should not impact the components that provide the core functionality of the enterprise application

Solution

By applying the Model-View-Controller (MVC) architecture to a Java^TM 2 Platform, Enterprise Edition (J2EE^TM) application, you separate core business model functionality from the presentation and control logic that uses this functionality. Such separation allows multiple views to share the same enterprise data model, which makes supporting multiple clients easier to implement, test, and maintain.

Structure

The following diagram represents the Model-View-Controller pattern:

Participants & Responsibilities

The MVC architecture has its roots in Smalltalk, where it was originally applied to map the traditional input, processing, and output tasks to the graphical user interaction model. However, it is straightforward to map these concepts into the domain of multi-tier enterprise applications.

• Model - The model represents enterprise data and the business rules that govern access to and updates of this data. Often the model serves as a software approximation to a real-world process, so simple real-world modeling techniques apply when defining the model.
• View -The view renders the contents of a model. It accesses enterprise data through the model and specifies how that data should be presented. It is the view's responsibility to maintain consistency in its presentation when the model changes. This can be achieved by using a push model, where the view registers itself with the model for change notifications, or a pull model, where the view is responsible for calling the model when it needs to retrieve the most current data.
• Controller - The controller translates interactions with the view into actions to be performed by the model. In a stand-alone GUI client, user interactions could be button clicks or menu selections, whereas in a Web application, they appear as GET and POST HTTP requests. The actions performed by the model include activating business processes or changing the state of the model. Based on the user interactions and the outcome of the model actions, the controller responds by selecting an appropriate view.

Strategies

• Web-based clients such as browsers. JavaServer Pages^TM (JSP^TM) pages to render the view, Servlet as the controller, and Enterprise JavaBeans^TM (EJB^TM) components as the model. The Java Pet Store sample application illustrates this strategy.

• Centralized controller. Instead of having multiple servlets as controllers, a main Servlet is used to make control more manageable. TheFront Controller pattern describes this strategy in more detail.

• Wireless clients such as cell phones. The Smart Ticket sample application illustrates this strategy.

Consequences

• Re-use of Model components. The separation of model and view allows multiple views to use the same enterprise model. Consequently, an enterprise application's model components are easier to implement, test, and maintain, since all access to the model goes through these components.

• Easier support for new types of clients. To support a new type of client, you simply write a view and some controller logic and wire them into the existing enterprise application.

• Increased design complexity. This pattern introduces some extra classes due to the separation of model, view, and controller.

Related Patterns

[BRMSS96]: Presentation-Abstraction-Control defines a structure with a hierarchy or cooperating agents, each with specific duties of the application functionality. It divides the functionality responsibilities into three components: presentation, abstraction, and control.

A regular expression to check for prime numbers

Regular expressions are extremely powerful. This is something I read at least once or twice every day while reading articles and blogs on the Web.

While browsing today, I found this page which thoroughly describes the use of the regular expression /^1?$|^(11+?)\1+$/ in Perl to check if a number is prime or not!!!

To be frank, I was skeptical. The regular expression looks like magic! And I wanted to understand it better. I rewrote it in Ruby using irb and I tested it:

Avinash@noulakaz:~$ irb
irb(main):001:0> def is_prime(n)
irb(main):002:1> ("1" * n) !~ /^1?$|^(11+?)\1+$/
irb(main):003:1> end
=> nil
irb(main):004:0> is_prime(10)
=> false
irb(main):005:0> is_prime(11)
=> true
irb(main):006:0> is_prime(12)
=> false
irb(main):007:0> is_prime(13)
=> true
irb(main):008:0> is_prime(99)
=> false
irb(main):009:0> is_prime(100)
=> false
irb(main):010:0> is_prime(101)
=> true

Great! It also works in Ruby! This means that there is no (Perl) magic going on. The regular expression really works. But how? Let’s try to follow the logic behind it.

Is 7 prime?

To know this, the function first generates “1111111″ (from “1″ * 7) and tries to see if that string does not match/^1?$|^(11+?)\1+$/. If there is no match, then the number is prime.

Notice that the regular expression has two parts (separated with the vertical bar |).

The first part is /^1?$/ is trivial and matches with beginning of line (^), an optional 1 (1?)
and end of line ($) which implies that it matches either the empty string or “1″. This simply indicates that calling that function with n==0 or n==1 will correctly return false (as the “1″ * n will match with the first part of the regular expression)

The second part is where the magic occurs…

/^(11+?)\1+$/ matches with beginning of line (^) then by (11+?) then by \1+ and finally by end of line ($). I guess that you know that \1 is a variable which is bound to whatever was matched previously (in our case by (11+?)).

Let’s proceed slowly…

(11+?) does two things

1. It matches with “1″ followed by one or more ones minimally. This means that it matches with “11″ initially (notice that if there was no ? (i.e. (11+) was used instead, the whole string would have matched)
2. The string obtained (”11″ initially) is bound to the variable \1.

\1+ then matches with whatever has been matched above (”11″ initially) repeated one or more times. If this match succeeds then the number is not prime.

If you are following, you’ll realise that this eliminates all even numbers except 2 (for example, 8 is “11111111″ and therefore (11+?) will match with “11″ and \1+ will match with “111111″).

As for odd numbers (in our case 7), the (11+?) matches with “11″ initially but \1+$ cannot be true (notice the $) as there are 5 remaining ones. The regular expression engine willbacktrack and will make (11+?) match “111″ and here also \1+$ won’t be true because there will be 4 remaining ones (and \1+$ will only match with a number of ones which is a multiple of 3 followed by end of line) etc. hence “1111111″ will not match the regular expression which implies that 7 will be considered as being prime 

When I showed this to Christina this morning (true), she told me that this only checked for a number being odd or not. This is also what I felt at the beginning. But it really works. For instance, let’s try to apply it to 9 (which is obviously not even), “1″ * 9 should match the regular expression…

“1″ * 9 = “111111111″. (11+?) matches “11″ initially. \1+$ cannot match because there are 7 remaining ones. Backtracking occurs. (11+?) now matches “111″. And here \1+$ matches the remaining 6 remaining ones! Hence, 9 is not prime.

Easy… and beautiful at the same time 

Original from:http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/

20 Best Websites To Download Free EBooks

本文原文出自：20 Best Websites To Download Free EBooks，

译言翻译：20个免费下载各类电子书(Ebooks)的网站。

1.FreeBookSpot
FreeBookSpot有4485本免费的E-BOOKS分成96个类别，多达71,97 GB。 您可以在类別搜寻找和下载免费的书，如:科学、设计、编码、小说和许多其他的书。您可以在类别搜寻和下载免费的书，如:科学、设计、编码、小说和许多其他的书。

2.4eBooks
4eBooks 有数量相当庞大的程式设计ebooks，下载的ebook都有简短的描述。您可以找到数以千计程式设计领域的ebooks，如:Net、Actionscript、Ajax、Apache..等等。

3.Free-eBooks

Free-eBooks是一个以网络为收集来源的免费ebook下载网站，除了免费ebooks以外，您也下载免费杂志或上传您收集的ebook作为交流。

4.ManyBooks

ManyBooks 提供PDA、iPod或者一般读者免费ebooks阅读与下载，这里有21,282 eBooks可利用，完全免费!

5.GetFreeEBooks

GetFreeEBooks 是一个免费ebook下载网站，所有网站内的ebooks都是有经版权许可免费可使用的。

6.FreeComputerBooks

FreeComputerBooks 包括免费网络、编程、数学、技术、演讲笔记和教学的丰富资料库。分类按照标题，分成12个根目录和150个子目录。

7.FreeTechBooks

FreeTechBooks 包括网络电脑科学，工程学和程序方面的书，课本还有演讲笔记，所有网站内的ebooks都是有经版权许可免费可使用的。

8.Scribd

Scribd是线上文件分享网站，支援格式有:Word、Excel、PowerPoint、PDF与其他一些常用的格式，您可以下载或是贴在你的blog。详细介绍。

9.GlobuszGlobusz 是特別为发表ebooks设计的网站，专门研究免费eBook下载。文章与作者也以星等加以评价。

10.KnowFreeKnowFree免费交换ebooks、录影和其他材料，授权做为教育用途或是非商业用途。

11.OnlineFreeEBooksOnlineFreeEBooks 提供9大类的ebooks：汽车Ebooks，商业Ebooks、设计Ebooks、套件Ebooks、硬件Ebooks、健康与医疗Ebooks、软件与技术Ebooks，体育与武术Ebooks。

12.MemoWareMemoWare 有数以万计收藏(数据库、文学、地图、技术参考等等)特别的格式化的文件可以容易的传输到您的PalmOS、Pocket PC、Windows CE、EPOC、Symbian或其他PDA设备。

13.BluePortal

14.OnlineComputerBooksOnlineComputerBooks 包含关于免费电脑书

15.SnipFiles

16.BookYards

17.The Online Books Page

The Online Books Page 超过30,000本免费ebooks。

18AskSam Ebooks

AskSam Ebooks 有免费的收藏，如:莎士比亚、法律与政府文件。

19.Baen Free Library

Baen Free Library是下载科幻小说的在线图书馆。

20.eBookLobby

包括商务、艺术、电脑及教育。

21.Issuu

Issuu是一个专业的在线PDF分享服务网站，或者也可以认为是一个很不错的在线PDF文档图书馆。详细介绍。

22.Yudu

Yudu是一个在线PDF文档分享网网站，你可以发布自己的PDF文件，上面也有很丰富的PDF电子书资源。

23.Calameo

Calameo同样是一个PDF文档分享网站，上面也有丰富的PDF文件可供下载。

24.Onsitecatalog

Onsitecatalog也是一个在线PDF发布服务，上面同样有很多的免费的PDF文件资源。

Using gnus In Windows with gmail's imap

1.Download stunnel installer and openssl

2.Install them, edit stunnel.conf:

output = stunnel.log

client = yes

[SMTP Gmail]

accept = 127.0.0.1:466

connect = smtp.gmail.com:465

[IMAPS Gmail]

accept = 127.0.0.1:996

connect = imap.gmail.com:993

3.Run stunnel sevice start, so it can run in backgroud

4.Edit .gnus(default configure file)

(defun fs-change-smtp ()

  "Change the SMTP server according to the current from line."

  (save-excursion

    (let ((from

       (save-restriction

       (message-narrow-to-headers)

       (message-fetch-field "from"))))

       (message "From is `%s', setting `smtpmail-smtp-server' to `%s'"

          from

          (cond

          ((string-match "xxx@gmail.com" from)

          ;; Use stmp-auth

          (message "Using smtp-auth")

          ;; Sending mail

          (setq message-send-mail-function 'smtpmail-send-it)

          (setq smtpmail-starttls-credentials '(("127.0.0.1" 466 nil nil)))

(setq smtpmail-auth-credentials '(("127.0.0.1" 466 "xxx@gmail.com" nil)))

          (setq smtpmail-default-smtp-server "127.0.0.1")

          (setq smtpmail-smtp-server "127.0.0.1")

          (setq smtpmail-smtp-service 466)

        )

        ;;((string-match "xxx@gmail.com" from)

        ;; Use local sendmail

        ;; (message "Using local sendmail")

        ;;(setq message-send-mail-function `message-send-mail-with-sendmail))

        (t

           (error

           (concat "Don't know which mail server to use for "

         from))))))))

(add-hook 'message-setup-hook 'fs-change-smtp)

(setq user-mail-address "xxx@gmail.com")

(setq user-full-name "xxx")

(setq gnus-select-method '(nnimap "imap.gmail.com"

                                  (nnimap-address "127.0.0.1")

                                  (nnimap-server-port 996)

))

 

(add-hook 'gnus-topic-mode-hook 'gnus-topic-mode) 

5.M+x gnus, That's it!