Wednesday, October 29, 2008

Writing solutions to exercises

我花了五天的時間去寫兩次作業的解答,不曉得是我太認真還是題目太多,總之忙到研究的題目都沒力沒時間去想。現在還有兩個作業等著我寫解答,以及一個 11/21 截止的期中報告。

然後看看學弟妹寫的錯誤答案,就會有股小朋友般的脾氣湧上腦門,想要直接在上面劈哩啪啦打幾個大叉撇掉(阿不過線上作業是要怎麼打叉呢)。話說回來,還是等心平氣和之後再來改作業比較好。

老婆的擔心是有道理的,如果忙個不停但是研究沒甚麼進展,也是白搭啊。只能說盡量再擠出點時間好好想問題吧。

附註:作業的題目和解答也順便放在之前我做的隨機演算法網頁上了,但是目前只有前兩章有答案。Ton 跟我說,這些題目做起來很無趣,因為大多只是單純套一套定義和定理下去跑一跑而已,不過對我來講,其實算是不錯的練習啦。

Wednesday, October 22, 2008

Research discussion today

其實我原本可以延至下週或更久之後才報告,但是就這麼一念之差,讓進度快了一個禮拜。這讓我體認某些時間點的關鍵性,該拼時不得不拼。

因為我已經習慣早上起床晨跑,所以今天有足夠的意志力在六點前起床,趕工尚未完工的投影片。我所報告的 paper 是 Alon 與 Krivelevich 在 2002 年寫的 "Testing k-Colorability",不過我只針對 paper 裡頭的第四章 (k > 2) 的部份來準備。因為我使用 Beamer 的關係,投影片頁數多達 90 頁,但是只相當於 ppt 的 30 頁左右。

因為 Ton Kloks 跟我提過他想來聽我的演講,所以在早上十點整左右投影片一完工,就請 Ling-Ju 幫忙叫他來參加我們的 group meeting。有一陣子沒有練習用英文演講的我,今天講起來還算是很順暢。不過,投影片還是熱騰騰的,我也沒有把它們好好順過一次,以致 Ton 與老師在某些地方不甚了解。尤其是 ε-far from k-colorable 與 colorless or restricting vertices 數目的關係,是老師一直很 care 的地方。這裡所倚賴的理論根據就是 Claim 4.1,講的是 violating edges (違反 k-coloring 的邊) 數目的上限。從這個事實可以接著導出 colorless vertices 與 restricting vertices 的下限。因為時間的關係,我沒有講述怎麼利用一個 auxiliary tree 來分析這個 testing algorithm 的 query complexity 以及 error probability 上限。

中午我們幾個學生和 Ton 一齊用餐,Ton 提出了一些想法,主要是從 square of a graph 的觀點,我覺得是不錯的點子!但是目前想起來似乎覺得有一點問題尚待釐清。下午接近五點的時候,老師找我下來一起討論這篇 paper。我們兩個人就這樣順著 paper 看,有問題就立刻討論。第一次跟老師「一起看 paper」,有點小感動。我想,老師應該是有抓住了演算法和分析的精神。我個人認為,這篇 paper 雖然有一些 typos,但是大致上還蠻精彩的,也不算難懂。不曉得老師的感覺怎麼樣。Ton 也會找時間讀這篇 paper,也許我們有機會做出一些結果出來也說不一定。

Tuesday, October 14, 2008

A tool for calculating branching numbers

之前在 RWTH-Aachen 時,我的研究室 Linux-PC 裡有一支小程式,可以計算一個 branching vector 對應的 branching number。回到台灣以後,那邊的帳號已經失效了,所以勢必得自己搞出一個計算 branching number 的程式。

其實去年年底之前,我就已經在某個程式裡寫出一個簡單計算 branching number 的 function 了。今天下午稍微改寫一下,就輕鬆得到看起來跟 Peter 那邊一模一樣的程式。程式碼可於這裡下載。其實算法很簡單,只不過是利用十分逼近法去求反轉特徵多項式的根值罷了。

在 Linux OS 底下,可以使用 gcc br.c -lm -o br 得到執行檔 br,然後將它移動至 /bin 底下,這樣子所有的使用者都可以在任何地方輸入 "br ",就可以得到 對應的 branching number 了。單純的 gcc 指令會出狀況,好像是因為 math.h 裡面沒有 pow() 這個函式的緣故。改用 gcc -lm 或是直接用 g++ 硬做都可以成功編譯。

至於使用方式呢?只要在 command line 輸入 br 和 branching vector 再按下 return 就可以了。比如說,輸入 "br 1 1 1 1",當然就是得到 4 啦,而輸入 "br 1 2" 就可以得到跟黃金比例的比值 1.61803401...。至於精準度,我只有設小數點後八位,應該是夠用了。

Sunday, October 12, 2008

A bash file for backup

以下是一個可以用來備份的 bash file



#!/bin/bash
# Program:
# Backup the tex file.
# History:
# 2008/10/12 Joseph C. C. Lin First release
# bash scrip name: backup.sh

file="paper"
tex=".tex"
day=`date +%G%m%d%H%M`
original="$file""$tex"
backup="$file""-""$day""$tex"
cp $original PAST/$backup
echo "Backup '$backup' to PAST"


這個 bash scrip 很好用!只要修改完 paper 後,執行 "sh backup.sh",它就會自動幫我把 paper.tex 備份到 PAST 資料夾去,而且檔名還會加上日期,譬如 "paper-200810121925.tex",說明這份文件是在 2008 年 10 月 12 日 19 點 25 分編寫後備份。

對於文件的備份和撰寫,使用 cvs (Concurrent Versions System) 應該是最好的方式,但是目前有遭遇一些問題,所以日後再說。

Saturday, October 04, 2008

Installing MPlayer in a Linux OS

參考資料來源:
http://www.linux.com/feature/37196

Linux 預設的影音播放軟體很難用,或者不知道哪裡才會用的上。所以,可以選擇安裝 MPlayer 與 Realplayer 這兩套好用的軟體。MPlayer 的參考安裝方式如下:

  1. 首先,前往 MPlayer download 網站,下載 MPlayer 的 source code (for example, MPlayer v1.0rc2 source: 檔名為 MPlayer-1.0rc2.tar.bz2)
  2. 下載完 source code 之後,接著解壓縮 .bz2 檔至某個資料夾,例如 temp
  3. 打開 terminal,進入 temp 資料夾中
  4. 執行以下指令
    ./configure --enable-gui
    make
    su (if you're not already root)
    make install

這樣子,MPlayer 就安裝好了!我之前想試經由 rpm 或 yum 的方式安裝,都沒辦法成功,現在終於 okay 了。至於 Realplayer,可以從這個 rpm 連結去下載安裝,簡單很多。

MPlayer 播放結果


Realplayer 播放結果 (德語第一課)