Adversary Argument

還是先懺悔：我去年幾乎沒做助教出的 voluntary exercises，只記得有次助教解答有附一份關於 adversary argument 的文件，但那時看沒什麼感覺 XD。

這次為了證明 "double-end problem"（說不定隨機客的一大樂趣就是為問題取名字？XD）的比較次數下界為 3n/2 苦思良久。昨晚十一點多想到說不定可以把它化成圖論問題（因為 "champion problem" 的比較次數下界用 graph connectedness 思考非常直覺），但沒看出什麼性質。接著從 decision tree model 慢慢磨出 adversary argument 的邏輯，但因為我是從圖論的脈絡過來，討論繁複，沒辦法找到足夠簡單的分析方式。後來上網一找發現 "adversary argument" 這詞，才知道是以前不認真，自食惡果 XD。

--
今年就趁機會把隨機客的演算法作業都想一遍吧。（其實是不得不想 ─ 也是自食惡果？XD）