Thursday, January 31, 2008

Some useful mathematical formulae

• $e^a \geq 1+a$

• 1/(1+x) = 1 + O(x) when x is small.

• ${n\choose an} = O((\frac{1}{a^a (1-a)^{(1-a)}})^n)$, where $a\in (0,1)$.

• If $T(1) = 1$ and $T(n) = 2^nT(n/2)$, then $T(n) = 4^n$.
• ${n\choose k}\leq 2^{n\cdot H(k/n)}$, where $H(p) = -p\log p - (1-p)\log (1-p).$
• $\left(\frac{n}{k}\right)^k\leq {{n\choose k}}\leq\frac{n^k}{k!}\leq\left(\frac{n\cdot e}{k}\right)^k.$

Tuesday, January 29, 2008

Interesting papers

• Justin G. Chen, Scott D. Kominers, Robert W. Sinnott:
• 懶是上策?!
• Artur Czumaj and Christian Sohler: (Draft) A survey on sublinear time algorithms.
• 另一篇關於 subliear time algorithms 的 survey
• Ziv Bar-Yossef, Ravi Kumar: Sampling Algorithms: Lower Bounds and Applications. STOC'01
• 看看這篇說不定能幫助我更加深入了解 sampling algorithms
• Rajeev Motwani, Rina Panigrahy, Ying Xu: Estimating Sum by Weighted Sampling. ICALP'07
• 喔？！這一篇算是蠻新的吧！

Best wishes for the paper

Peter 不放心我們的 paper 會不會被接受，所以說想去教堂點一盞燈，祈禱 referees 會接受這篇 paper。我想我也會在每次用餐時祈禱。這麼說來，老師不就可以去孔廟找孔子聊聊了？

Friday, January 25, 2008

The 3n+1 conjecture (Collatz's conjecture)

The 3n+1 conjecture (Collatz's conjecture), forwarded from Open Problem Garden.

Let f(n) = 3n+1 if n is odd and n/2 if n is even. Let f(1) = 1. Assume we start with some number n and repeatedly take the f of the current number. Prove that no matter what the initial number is we eventually reach 1.

It can be also obtained from Wikipedia. This problem is worth at least \$500 US dollars. Refer to this page for some results of computational verification. I also wrote a very simple program to verify this conjecture.

This is an an open problem for the moment, and it seems to be given on an graduate school entrance exam. To find a function g (n) such that f(n) = O(g(n)) is then an open problem, too.

It's very interesting. By the way, I found "Jones' conjecture", posted by Chuan-Min Lee. I hope that someday I will post an interesting and important open problem or a conjecture, too.

Wednesday, January 23, 2008

A picture taken when Peter visited CCU, Taiwan

Professor Peter Rossmanith 於 2007 年造訪中正大學資訊工程學系計算理論實驗室兩次， Post 上這張照片當作紀念。

Tuesday, January 22, 2008

Joseph, Chuang-Chieh Lin's Homepage

Since my homepage cannot be visited by Google robots, I post it here.

It has been updated for several times.

Monday, January 21, 2008

Terence Tao's homepage and blog

http://www.math.ucla.edu/~tao/
http://terrytao.wordpress.com/

Chinese Translation of my personal homepage

http://tinyurl.com/36twpk 中文版
http://tinyurl.com/3y3gsw 德文版

Room405, 計算理論實驗室,

RWTH 亞琛大學, 德國

Maw-Shang Shang Chang (禮物) 教授 ,
R. C. T. 李教授(前)
...
...

Sunday, January 20, 2008

My poor teeth...

There are always troubles with my teeth. I just lost half part of one tooth by accident. I think I'd better go to Josef Kunze's clinic as soon as possible, if I don't want to lose the rest part of it.

So terrible for me. Oops!

W3C HTML 4.01 Transitional validation passed!

Finally I made my personal homepage pass the validation!! It is not so easy for me to refine the homepage from the original Microsoft Frontpage webpage to a valid W3C html one.

Congratulations

The document located at http://www.cs.ccu.edu.tw/~lincc/ was checked and found to be valid HTML 4.01 Transitional. This means that the resource in question identified itself as "HTML 4.01 Transitional" and that we successfully performed a formal validation using an SGML or XML Parser (depending on the markup language used).
And I got this:

The following paragraph is an interesting FAQ:

Is validation some kind of quality control? Does "valid" mean "quality approved by W3C"?

Validity is one of the quality criteria for a Web page, but there are many others. In other words, a valid Web page is not necessarily a good web page, but an invalid Web page has little chance of being a good web page.......

To validate your website, try W3C HTML Validator: http://validator.w3.org/

Tuesday, January 15, 2008

葛若琳 (Caroline Gluck) BBC 特約記者

http://udn.com/NEWS/NATIONAL/NAT5/4181243.shtml

http://udn.com/NEWS/NATIONAL/NAT5/4181243.shtml

Caroline Gluck 的部落格： (caro's choice)
http://caroschoice.blogspot.com/

Monday, January 14, 2008

My Cherie Amour (by Stevie Wonder)

La la la la la la
La la la la la la

My Cherie Amour, lovely as a summer's day
My Cherie Amour, distant as the Milky Way
My Cherie Amour, pretty little one that I adore
You're the only girl my heart beats for
How I wish that you were mine

In a cafe or sometimes on a crowded street
I've been near you, but you have never noticed me
My Cherie Amour, won't you tell me how could you ignore
That behind that little smile I wore
How I wish that you were mine

Maybe someday you'll see my face among the crowd
Maybe someday I'll share your little distant cloud
Oh, Cherie Amour, pretty little one that I adore
You're the only girl my heart beats for
How I wish that you were mine

La la la la la la
La la la la la la

Sunday, January 13, 2008

Runners Point and Dom neighborhood

Josef 的建議與 wes 的很類似，他說寒冷的冬天應以建立里程為主，速度練習可以先擱著。令我訝異的是，一天 30 km 的里程對他而言幾乎是隨手拈來。希望三月底之前，他能確定跟我一起參加 Düsseldorf Marathon。前提是，他得過老婆那一關才行。

Tuesday, January 08, 2008

Glucosamine & chondroitin

http://www.wedar.com/health/show.asp?id=1721

Apotheke am Steppenberg:

Telephone: 0241-873335

Study progress - [JKL01-SICOMP]

T. Jiang, P. Kearney, and M. Li: A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application. SIAM J. Comput. 30 (2001) 1942--1961. [link]

Friday, January 04, 2008

Home - Simply Red

What's worth nothing else but love
Take a walk down any street now
Every one of us in our own little world
Looking for a heart with whom to beat now

What's worth nothing else but love
I'm prepared to take the heat now
What's worth more than anything else at all
To keep you firmly on your feet now

So fake cool image should be over
'Cause I long for a feeling of home
Real life, depicted in song
A loving memory
After long, home is a place where I yearn to belong

Where the land meets the sea
She'll be smiling so sweetly now
I hope that she'll be here much longer than I will
My heart loves her with every beat now

So fake cool image should be over
'Cause I long for a feeling of home
Real life, depicted in song
A loving memory
After long, home is a place where I yearn to belong