Saturday, December 24, 2005

Randomized algorithms and randomized life?


在看了一篇關於 randomized algorithm 的 paper 以後,總算利用 group meeting 的時間跟大家做了一次詳盡的報告。我的目的是想引發大家對這方面 topics 的興趣,希望老闆也能跟著投入這領域的研究。而目前看來效果還算不錯。

國內做這領域的學者不多,而且要上手的門檻高得多,加上我對於隨機的概念掌握度還不是甚高,因此常有霧裡看花的感覺。目前我的計畫是先從基本的機率與統計的書籍著手,先對機率統計有一點感覺,還有閱讀相關的 papers 以及 那本 randomized algorithms 的教科書。進度?當然愈快愈好,因為明年老闆要我試著提一個國科會計畫,而且我得把一些概念跟老闆分享討論,老闆才能真正一起投入這領域的研究。

令我吃驚的是,原本對隨機演算法嗤之以鼻的老師們,現在卻對它有高度的興趣。Knuth 就曾經表示隨機演算法是很重要的。

只是說…我畢業的時間說不定也帶著相當高的隨機度了。

目前待解的問題:

  • 由隨機抽樣的一些點中取 average degree 與原圖的 average degree 差異和相關機率的關連?

  • sublinear time algorithms 所花的時間事實上是否為 "expected running time"?

  • 假設現在每次執行的 input 都不一樣(這假設是十分合理的),而 randomized algorithm 每次回答的答案也不盡相同,假設它能回答一個 expected answer,那麼對多個 inputs 多次執行這 randomized algorithm 的 expected answer 又是怎麼樣的一個值?

以上這些問題都尚待釐清當中。


CCLin

Tuesday, December 20, 2005

人生的目標 - 凡事追求自我實現

做什麼事情都會有動機,而那件事會讓你繼續做下去,就必須要讓你有成就感。


附記:做研究和練跑就是例子。

Sunday, December 04, 2005

創意工廠 MIT

創意工廠 MIT……

我知道這本書很讚,但我實在不敢向老闆推薦。因為現在我的壓力已經夠大了 ,要報paper (meeting + 圖論演算法的課)、助教的工作、家教教材的準備…等等,我已經快不行了。最近又找死去挑一篇SIAM Journal on Computing的文章來看,而且還是那篇文章對我而言還是相當陌生的領域。老闆要是看過這本書,一定會覺得我們壓力還不夠……不敢想了。

MIT和Berkeley裡面的學生真厲害。希望我不要輸他們太多。

PS:今天三合一選舉結束了。願上帝祝福台灣 :)

Chuang-Chieh Lin

開始用中文記事好了




我看我還是用中文記事好了。我比較方便寫也比較整理。反正我還有中翻英和Advanced StudioClassroom.

最近練跑很積極。我常常會問自己:「這樣有意義嗎?這樣的意義在哪裡?目標又該是什麼?」

跑步應該是很快樂的,像是馬拉松小子片中的男主角一樣。

我一面跑,一面跟身體對話 。我不想要有懶得去跑的想法出現。因為一旦如此,好像跑步就沒有意義了。


目前的目標,是1500M跑進4'30"以內,以及明年2/28的古坑馬拉松。

我希望跑步追求成績的同時,也能尋得那 "原始的悸動與快樂"



PS: 當然研究更重要,不然就沒意義了。 :P

Chuang-Chieh Lin

Tuesday, September 27, 2005

On L(2, 1)-labeling problem

Oh...It's really tiresome to modify other one's article.

My recent progress is rewriting senior W. H.'s master thesis. Half of the proofs were done.
I hope that I can finish this job as soon as possible.


Too tired I am now.

C. C. Lin in lab

Monday, July 25, 2005

Comparability graphs


Wow~~~Look at these definitions!!

Definition: (first)

A graph G = (V, E) is a comparability graph if there is a transitive orientation of its edges.

Definition: (second)
The comparability graph of a partial order (V,) has node set V, and edge (x, y) whenever xy or yx. G is a comparability if it is the comparability graph of some poset.

Definition: (third)
The comparability graph of a poset P = (X, ≦) is the graph with vertex set X for which vertices x and y are adjacent either xy or yx in P.

I'll keep studying the paper.

Thursday, July 21, 2005

How Do We Pronounce the Word "Skype"?

The answer is as follows.

Skype help

Skype rhymes with ripe and type.
In Chinese, we pronounce it by "史蓋噗".

Brilliant!!

A nice blog

Wow. It's very cute.

I think all the paintings were done only by herself.

If NP = P, then any problem not empty and not Σ* will be NP-complete

The answer was greatly supported by Prof. G. S. Huang.


------------------------------------------------------------------------------------------------

You are wrong.
Since in the assumption one supposes that P=NP, any problem in NP is also in P. Therefore you can solve any NP problem in polynomial time by a deterministic Turing machine under this assumption.

Your another point criticizes on how to find a "yes" instance and a "no" instance from A (which is the one that we intend to show NP-complete). This is indeed not a problem since such two instances always exists and do not bother one really to find them. Actually, you don't have to spend any time to find them since you only have to show that such a reduction does "EXIST" as long as such twoinstances exist.

----- Original Message -----
From: Chuang-Chieh Lin
To: Professor G. S. Huang
Sent: Thursday, July 14, 2005 3:23 PM
Subject: Re: Communication

Dear Professor Huang:

Thank you for your advise.
Recently I found some answers similar to yours.

http://www.cs.brown.edu/courses/cs152/hw5_sol-99.ps
http://www.cc.gatech.edu/classes/AY2005/cs4510_spring/hw4sol.pdf

However, I am still puzzled at how do we find "Y" and "N" in polynomial time.
Shouldn't we require a Turing machine doing this work?
It seems that finding a "Y" and finding an "N" would require exponential time
in the worst case although deciding whether an instance is an "Y" or "N" is of
polynomial time.

Sincerely yours,
Chuang-Chieh Lin

As for your problem, I think the reduction in Sipser's book
is the polynomial reduction. Suppose A is in P and B is in NP.
All you have to do is to prove that any B can be reduced to
such A in polynomial time.

There exist "yes" instances and "no" instances of A since A is not empty or full.
Let's call Y a "yes" instance and N a "no" instance. The reduction is as follows. For any instance of B, we do

1. Solve the instance in polynomial time. This becomes possible since we assume NP=P.
2. If the answer is yes, output Y; else output N.

This is indeed a polynomail-time reduction and you can show
that the instance is "yes" IF AND ONLY IF the output is a
"yes" instance of A, though this reduction is a little nonsense.
Therefore one can claim that A is NP-complete since A is in NP.


A letter coming from Professor G. S. Huang.
-----------------------------------------------------

Test for emailing to my blog

Dear Turtle:

This is a test document.
That's all.

Best regards,
Chuang-Chieh Lin

---

Think hard, not work hard.
                    - Professor R. C. T. Lee

---

Chuang-Chieh Lin (林莊傑)                             
Dept. of Computer Science and Information Engineering,
National Chung-Cheng University                      
Homepage:
http://www.cs.ccu.edu.tw/~lincc           
Email:
lincc@cs.ccu.edu.tw, s1321501@ncnu.edu.tw

---

Wednesday, July 20, 2005

Test for posting photos






Wow!! It is a shame for me to do such a stupid action.

Really.

Chuan-Min Lee's new Blog was done!!




My senior, Chuan-Min Lee, built his blog.
Chuan-Min Lee's Blog: First post

His photo:

Welcome!! By the way, I have to go back to work now.

My FIRST post here




My FIRST post!

Today I found http://www.blogger.com, then I registed to be a member of Bloggers.


Here I decided to post my feelings, thoughts, or ideas. This article is in memory of my first post at Bloggers.

I hope that I can graduate as soon as possible.

That's all.
C. C. Lin