在 第一講中，我們證明了有很高的機率，任意 slot 中 element 的個數均為 $\mathcal{\Theta}(\frac{\ln n}{\ln (\ln n)})$ ，而這一講想討論的是，如果今天我們手上有兩個 hash function (from same $\mathcal{H}$)可以選，每次我們就看哪一個 $h$ 回傳的 slot 中元素比較少，就將 element hash 到 slot，那麼現在 $\mathbb{E}[, \text{max num of elements in any slots} , ]$ ?
Hashing 的一個 criteria 是希望儘可能不要發生 collision (也就是 Worst Case 也在 $\mathcal{O}(1)$ lookup)，今天假設我們已知元素的個數，該如何設計一個 hash function 使得不會有任何 collition 發生？
前面提到過一個較為複雜的優化問題， Metric Facility Location Problem ，並給出了一個 4-Approx. Algorithm ，於這講中，我們要來利用前面提到的 Primal-Dual method 來設計演算法。
呈之前的討論，對於 WSC 問題，我們有了利用 LP solver 去對解做 deterministic rounding 及 randomized rounding 的演算法，解法的共通點是必須要先 run 過 LP solver (雖然理論上是 POLY ，實務上現行的 solver 也很有效率)，但我們仍想問說，是否存在不須使用 LP solver 的演算法呢？ 而這也是這講所要提到的 Primal-Dual Method 。
接續前面幾講，一個常用的技巧是，利用 LP solver 得出來的解 $\mathbf{x}^{\star}$， 拿去做 rounding 推出原先問題的解 $\mathbf{x}^{\prime}$ (with 一個還不錯的 approx. ratio)。而這講會講述一個較為複雜的問題 - Metric Facility Location Problem (MFL)。
前兩講討論的是給定起點，問到其他點的最短距離，稱為單源最短路徑問題，而現在我們想考慮 $V$ 中兩兩點對彼此間的最短距離，又稱全點對最短路徑問題。
呈前一講的討論，我們有了個求單源最短路徑的演算法Bellman-Ford (複雜度為 $\mathcal{O}(VE)$ )，現下我們考慮額外的限制條件(邊權重為非負)，想找出是否存在更有效率的演算法
圖的一個常見應用場合是想找出某兩點之間的最短(/長)路徑，此時的邊權重又視為兩節點之間的距離。
給定一張圖，要如何讀取當中的資訊呢？簡單來說就是從一給定點開始，依某種順序去拜訪相鄰(有關係)的點，最後走完所有點，收集完圖中的資訊。以下簡介兩種簡本的 traversal 方法以及應用。
Disjoint Set 顧名思義，代表了一群兩兩交集為空的集合們，常用於處理依據某種關係將元素們「分類」的問題。我們的目標是去 maintain collection of disjoint sets $S_1,S_2,\cdots,S_k$，而每個 $S_i$ (每個 category) 以一個代表值 (representative) 去紀錄。
呈前一講，我們對有限制的 WSC 問題有 $l$-approx. algorithm，但可能並不是太好(比方說 $l=|U|$ 之類)，於是我們嘗試引進一些隨機性，雖然犧牲了 deterministic 的 approx. ratio ，有時候甚至會得到更爛的結果(甚至不滿足 constraint @@)，但可以證明在大部分時候，都可以得到一個還不錯 (approx. ratio ISN'T too bad)的結果。
這一講會展示將問題轉化為線性規劃的 form (但可能是 ILP)，利用 LP solver 得到解，做 LP relaxation 並證明這個解不會太差 (approx. ratio 不太大)。
**Definition:**
A linear programming is a problem of maximizing or minimizing a linear
multivariate function subject to some linear constraints
從前兩講關於分配 (在一堆物品中，決定哪些是要拿的一群，哪些不拿) 的最佳化問題中，我們延伸出新的問題，Bin Packing Problem。不同於在 Knapsack Problem 中，我們只有一個箱子(可以想成你聘了一個工人搬一個箱子)；在Bin Packing 問題中，要取走所有寶物(所有寶物的重量都小於 1 單位)，而你需要聘請一些工人來搬，但今天每個工人都只帶了一個負重為 1 單位的箱子，該如何分配這些寶物(雖說是寶物，但其實我們不care價值惹)，使得需帶的箱子(聘請的工人)為最少？
簡單的 formulation 如下：
Subset Sum Problem 與 Knapsack Problem 相同，也是一個 NPC 問題(可以想成 Knapsack Problem weight 均為 1 的特例)。而在 Knapsack Problem 中，我們發展出等差 的rounding 技巧，犧牲精確度去換取更低的時間複雜度，而這一講中，將利用等比的方式去做 rounding 。
背包問題為一個典型的最佳化問題，想像你來到了一個寶庫，裡頭有一些寶物，都有各自的價值和重量，但你只帶了一個背包(而且負重還有限制)，要怎麼取寶物才能在背得走的前提下，帶走價值總和儘可能高的寶物們呢？
這裡我們考慮最基本的 0/1 - Knapsack Problem 。簡單的 formulation 如下:
上一講利用 Myerson's Lemma 闡述了給定在「好」的 allocation rule 下，該如何定價，使得 auction 具有 DSIC property; 而這講則要說明該如何 derive 出「好」的 allocation rule。
上一講提到了怎樣的 auction 是設計者所希望看到的，有足夠的誘因使參與者做出我們希望看到的決策 (DSIC property)，且此決策所造成的結果為設計者認定的 optimal ，同時又能簡單到能在多項式時間完成。接下來會提供一個更 general 的方式去設計機制，而不單單只是限定於 single-item auction 而已。
Hashing 可以想成是一種 renaming 的方式，原先的名字 (key) 可能很長，但可能的組合並不完全隨機，且數量相對整個宇集少上不少，若我們要建立一個跟宇集一樣大的 Hash Table 並不符合成本(且大部份 slot 是空的)，所以想透由 Hashing 的方式，重新命名 key’ ，並依據 key’ 將資料放到 size 跟資料個數差不多的 Hash Table 中。
Lecture1 提到了我們需要透由好的 mechanism，使得 agent 與 designer 的 incentive 彼此 aligned。這講從最簡單的 Single-item Auction 開始，探討該如何設計合理的 mechanism。
這學期因緣際會之下，選了商研所的賽局，上起課來的感覺跟 EECS 著實差異頗大，直白的文字敘述及直覺居多（課後作業還是電影欣賞），考試也多以申論為主(但即使這樣，期中考還是考了全班最高分XD)，碰巧在網路上找到了這門課程，覺得相當有趣，以資訊科學的角度出發， formulate 各種所謂「直覺」的經濟學想法，去解決現實世界的問題，聽了前兩堂課，感覺之後也會用到不少這學期修的高等演算法的概念，算是相輔相成，希望自己有毅力聽完，並整理筆記囉 :D
