Stable matching and two simple tricks(mix and comparison)

Stable matching

Recently, we begin our computer science lessons for the second period in A2 in X. The first course is a very interesting subject: Stable matching, which emerges in various situation like job-seeking and the choice of our marriage. (Oh, it's all about the big problem.)

An algorithm proposed by Gale and Shapley is very simple and it applies the idea that we do every day. Imagine that n boys would like to choose their girlfriend and there are n women. Everyone has a list totally ordered. The unstable matching means in two couples, the man and woman have intention to break up and regroup a new couple. So the algorithm of Gale works like this: one guy begins to find his girlfriend from the top to bottom of his list. He dates the girl available or replace the ex-boyfriend. If the latter happens, the poor ex-boyfriend has to find another girlfriend.

This algorithm always works and finishes with a stable matching because the configuration is always stable. Moreover, the boyfriends of the girls become better and better(according to the personal criteria) and the boy never asks a girl two times(so sad).

To implement this algorithm, we have to pay attention to the complexity. We can cut the branching for economize the time, but the greatest problem is that we should construct a table for avoiding the time consumed in comparison between two men. After all, the complexity is about O(n^2).(We can use stacks and lists but they are not essential)

Some other version various is like we can join the possibility of preference of being single. That is to say, we can put ourselves in the list. Then, we will not get married with the man or woman after ourselves.

Tip: Do not put yourself at the first place of the list TT.

Knuth mix
How to make a permutation more random? This is a question. In the famous paper about riffle-shuffle, Diaconis tells us that 7 times can make a deck of cards very random, but it is just a asymptotic way not a perfect solution.

A method from Knuth: we do one cycle and each time, we do the exchange of cards between it and the cards before it.

Some simple calculus shows that it works, but how to get this idea is really amazing.

How many times to get the max and min?
We know n times comparison makes the max, so does min. But if we want both of them, we need 2n times?

NO!We take 2n number and group two-by-two so that n pairs. Then one comparison in every group makes the n "big-one" and n "small-one". The max is in the n "big-one" and the min is in the "small-one". So 3n times comparison make the result.

Therefore, generally, for n number, 3/2 * n times comparison get help us get both the max and the min.

To A2

【写这篇日志的原因】

写这篇日志的原因是今天看到李大潜先生给复旦本科生和研究生的一些讲话。李先生是土生土长的复旦人，后来也曾留学法国，在应用数学方面造诣相当深厚了。李先生的讲话大意可以分成三个。第一层是鼓励和激励：每个数学系的学生都应该有一个数学家的梦想，所以应该好好学数学。或者说，即使真的只是瞄准业界，也应该在本科阶段打好基本功。第二层是方法论，数学不好学，得花功夫，求精深而不应浅尝辄止或者泛泛而谈。第三层，大概是批评下时下的诸多现象，例如本科生只想着出国，最终大学四年只带走了一个成绩，成为复旦的匆匆过客。例如研究生博士生现在不努力，办公室总是空着。

作为一个都已经毕业一年的老人，现在看这些话觉得字字珠玑。很遗憾当年这样的谈话连一遍都没有听过，只记得软件学院老师告诉大家好好努力以后好找工作之类的话了。不过现在听起来也不晚吧，毕竟我还在读书。

哦，好吧，现在做的事情也不只是读书了。

【关于到目前为止的一切】

张媛学姐曾经有句话我还是认同的：直接去美国读PhD和来法国读工程师，当然是不一样的。但前者的收获未必会更多，后者也未必更少。

当然，我们对这句话的解释是不一样的。我发现好像去读PhD的同学并不都那么开心。他们有些感觉课业压力大，对怎样成为数学家有疑惑。有些对学校课程设置诸多不满，有些竞争环境太激烈了不开心。而一切都Hold住的又寂寞了，总在考虑人生大事到处相亲……好吧，还有他们不得不盼的绿卡。

要我说都是物质太丰富了，惯出来的。在山上多清净多好！

但我觉得真正意外的收获是两个。第一个是，学校还会非常认真负责的去照顾到每一个学生。或者说是制定规则和服从吧，反正我还挺喜欢的，或许是当年复旦给的自由太多了。第二个是，我在大学毕业后还有集体生活，尽管有时候价值观也不尽相同，总比办公室生活看起来好像有趣多了。

总结一下，来法国一半原因就是当年一时一个轻易的许诺，对X是什么我也不了解。当然了，我还是相信姚老师的，他给的建议还是靠谱的。

【关于A2】

说说A2的课程。非常懂的数学课基本也上完了，后面的都是不懂的。开学了觉得还是挺吃力的，然而这种事情不就是攻坚战么，只有一步一步跨过去了。

我还是保留了相当数量的分析课，综上算是一个平衡吧。当然也在布局开拓一些其他可能发展的方向了。

然后哲学老师让我重新有了上哲学课的想法。所以一个“坏”的哲学家和一个好的哲学家差别还是很大的。

纵观人生，每个阶段的第二年都是非常艰难的，我在各个阶段的第二年往往会有一种懈怠的习惯，原因是第一年都还比较认真成绩不错。然后到第三年再来幡然悔悟奋发向上。好吧，这种烂俗的剧本我可不想再演了。其实每一天都是新的，都值得去珍惜，尤其是当年华不再的时候。

希望能像每天坚持跑步一样，在这一年的每一天里保持能量！

【关于未来】

虽然我来法国之前，还是糊里糊涂的，但是没有多久就把问题想清楚了。所以说困境和痛苦是能促进人思考问题的。

X的校长在第一天就和我们说过，我们每个人都会成功，只要我们努力，学校也会帮助我们。事实看起来学校资源确实很多，多到平摊到人均根本花不完。

那么如果学校愿意帮助我实现一个愿望（也只有一个哦），该怎么说呢？我想了还挺久的，觉得如果只能许一个愿望，那么还是希望能在这几年里面好好修炼，成为一个数学家吧。

也就是这么一个简单的愿望。

【最后】

最后的最后，感谢周围的朋友，尤其多说点的，像老秦、C哥、校长、小明、缪，还有周医生、张医生和黄同学，还有实际上从幼儿园同学一路做到大学同学的胡爷，还有我的二哥和朱老师啊。

还有我们山上的小伙伴，2004年我认识的小伙伴们陪我度过了人生美好的10年，希望山上的小伙伴们在接下来10岁月里，也能像家人一样，彼此激励、关心。

Welcome to my blog!

Thanks to the development of technology, we can create a website easily and freely.

I come from China and I have finished my undergraduate in Fudan University. Now, I am studying in Ecole Polytechnique.（Donc, je parle français.）My interests are always mathematics and its applications in other fields like computer science, physics and finance.

Sometimes I wonder how Prof.Tao can create so many ideas and share them on the Internet. I am not as clever, but I would like also share my study and my life with you.