第1題: leetcode 300 延伸 該題求最長遞增子序列(Longest Increasing Subsequence)的長度。 請仿照影片使用dp求解 題目：[4,9,2,8,7,1,4,10,3,7]，求其最長遞增子序列(Longest Increasing Subsequence)的長度。 :::success 過程 LIS

第1題: shortest path in multi-stage graph 下圖為一個multi-stage graph，請分別以forward approach與backward approach，推導出點1到12的最短路徑。 image forward approach :::success d(1,12) $d(1,12)=min{9+d(2,12),7+d(3,12),3+d(4,12),2+d(5,12)}$

第1題: Selection Problem 請以 prune and search 解 selection problem。 在以下 25 個數字中，要找出第 14 小的數。 25 個數字依序為： 15,18,12,10,12,4,6,14,10,1,3,5,1,5,20,3,4,10,7,5,1,15,2,4,8。 分組方式為：第一組為第 1 到 5 個數字，第二組為第 6 到 10 個，依此類推。 (A)請問第一回合找到的 p 值為多少？ (B)請問第一回合，被刪去幾個數字？刪去的數字為何？ :::success

第1題: 01背包問題 已知有六個物品，其價值和重量如下，背包重量限制為34。  仿照課本以tree search來解。 請將下圖中的框框中，填入其upper bound與lower bound image :::info

第1題: 最短路徑 請使用Branch-and-Bound找出下圖中，S到T的最短路徑。請畫出Branch-and-Bound圖，並標示各點的cost，以及被bound住的地方。(可參考ppt20頁) image :::success hill climbing hill 如果Bound會更新的話

第1題: 2-D Maxima Finding Problem 這個題目與解法，與第2章介紹的2-D Ranking Finding Problem相似。請比較此兩個問題與其解法，有何相同與相異之處。 :::success 相同之處： 一樣是切分成左右邊、也是切成一個一個再合併。 相異之處： 主要是合併方式2-D Maxima Finding 是把左邊比右邊的最大值小的直接砍掉，右邊不會受到影響。 2-D Ranking Finding 是幫右邊加上左邊的值，左邊不會被修改到。

第1題: Voronoi Diagram 請畫出下圖兩個VD合併結果，畫出新建立的線段(註明為哪兩點的中垂線)，並說明簡述流程。 image :::info 藍色代表目前線段結果 綠色代表新增的部分 橘色代表刪除的部分 紅色是兩點的連線 :::

第1題: Huffman Code :::info 已知一份文件內7個符號出現的頻率為：A:2, B:8: C:3, D:4, E:6, F:10, G:7。 請找出此7個符號的Huffman code。 若有一組編碼為1100110111，求解碼後的符號。 ::: Huffmancode

第1題: Heap Sort 1-1. 下圖為Max Heap。Heap Sort的每一回合，會將Heap的最大值刪除後，又恢復為Heap。請畫出第一回合恢復的過程 heap-01 1-2. 投影片69頁的公式如下，請解釋此公式的含意。 $\sum\limits_{L=0}^{d-1}2(d-L)2^L$ :::info $L$是目前的樹高，$d$是樹的整體高度 $(d-L)$就是跑到底所需要的成本

第1題: Selection Sort 請使用Selection sort排序，6,4,1,3,5。在四個回合中，每回合的Change of Flag數量為何？總共的Change of Flag數量為何？ :::info Change of Flag的定義(個人想法)： 從$a_0$開始往$a_{n-1}$走，如果遇到比較小的$a_i$就+1， 然後把$a_0$跟$a_i$交換，繼續比對 ::: :::info

第1題：Insertion Sort 請依據課本推導方式，當5個數字用insertion sort排序，data movement的平均值為多少？ :::info 從$j$開始搬運一次的平均data movement $\frac{2}{j}+\frac{3}{j}+\frac{4}{j}+ \cdots+\frac{j+1}{j}=\frac{j+3}{2}$ ::: :::info $X=\sum\limits_{j=2}^{n}\frac{j+3}{2}=\frac{(n+8)(n-1)}{4}$

第1題 $O(n^3)$ , $c=4$ , $n_0=2$ 第2題 $O(n^2)$ , $c=30$ , $n_0=3$ 第3題：數列被轉置 image 1. 解題思路

1. 本週影片中提到的NP-complete問題有哪些？ 0/1有限背包問題 旅行商問題 分區問題 畫廊監視器問題 2. 請上網找一個老師沒說過的NP-complete問題，並舉個例子說明該問題的輸入與輸出。 最簡單的就是N皇后了 在$N \times N$的西洋棋棋盤上放上$N$個皇后棋， 並且要放置在讓它們不會互相攻擊到的位置上，問有幾種擺放方式。