演算法 Algorithm (CSIE-2A)

# 演算法 Algorithm (CSIE-2A) ###### tags: `courses meow` `CSIE-2A` `Algorithm` `2021 Spring` :::success ### 計分 - 兩次期中考 `60%` - 從作業中出題 - 平時成績 `40%` - 演習課（討論作業，每週一次作業(可用時間 < 1week)(7~9題)） > 歷年來的經驗會被當20個人 (沒有刻意當人，單純就分數沒到) ### Book - T.H. Cormen et al., "introduction to Algorithms" 3rd ed,(The MIT Press 2009) - other reference - R. Sedgewick - A. Levitin - ... ### relative web - [UVA online judge(link)](https://onlinejudge.org/index.php) ### 相關競賽 - CPE - ITSA - PTC ::: ## $[Unit 1] Introduction - Traning for an algorithm designer - Design - Analysis - Implementation - some related topic ### What are Algorithm :::info #### Definition > blablabla ::: ### What are Problems - well-sprcified computational problem - 3 compoents - a set of `inputs` (or instances) - a set of `outputs` (or solutions, answers) - ==precise description== of relation between inputs and outputs - > inputs and outputs are all of finite lengths :::warning ### Example: Sorting Algorithm - statment - Input: A sequence of n numbers <$a_1$, $a_2$, ..., $a_3$> - Output: blablabal/not complete/ - Algorithms - Selection sort - Insertion sort - Merge sort ::: ### Problems & Modeling #### Modeling [Probelms in real world] --> [Algorithmic problems] ``` img of modeling ``` # week2 (02/25) > halting problem > 連程式會不會停都不知道了，你也沒辦法證明程式對不對 ## Some modeling example :::info ### model 1: LCS (Longest Common Subsequences) - 可用於語音辨識 (古早味) - sequence: - 可重複拿取 & 次序重要 - subsequence: - 給定一個 n 個字母的 sequence - subsequence 個數: $2^n$ > 在設計演算法的時候，可以想一個“等價”的問題，以方便自己思考[name=教授] ### model 2: Edit Distance - 在只有[insert, delete, replace, twiddle] 操作的情況下的字串相似度 ### model 3: Alignment of Two Strings - 在字串中插入 blank ::: ## Important problem types > 演算法課通常只教離散的 > 數值問題會開在「數值分析」課，需要考慮計算誤差 - Studying Discrete object - Sorting - Searching - String Processing - Combinational problems - Graph problems - Studying Continuous objects - Geometric problems - Algebraic problems - Numerical problems # 0303 ## 演算法基本設計方式 - 觀察，直覺& (trail and error) - > 有時候你的直覺對，有時錯 - 遞迴設計法（數學歸納法） - 轉換法（Transform-and-Conquer）（將問題轉換成自己(別人)會解的問題） - 其他：.....Brute force(xD ## Express Algorithm - Programs - Natural language - Flow charts - **pseudo codes** ## 遞迴 - Selection sort - Merge sort ### Analysis of Selection Sort - Correctness: By induction - > 相當於硬做（每個人都跟其他人比一次 $C^n_2$ - 類似概念的演算法： - Bubble sort - Heap sort - > 當第一名從缺的時候，只比有機會是第一名的人（曾被第一名打敗的） ### Analysis of Merge - Time complexity - $T(n) = T([n/2]) + T(n/2) + M(n), T(1) = 0$ - 假設 $n = 2^k$ - $T(n) = 2T(n/2) + n-1, T(1) = 0$ > 離散有一個算法可以解這種遞迴式[name=教授] > ~~可是我忘記了~~[name=87%的學生] - feature - stable - keys with same value do not exchange - not in-place - need extra space to put some number temporarily.(MergeSort吃空間) ### 遞迴的過程 - Top down(拆解) - Button up(合成) - 省略 - 當 split 為 trivial 時可省略; e.g. Merge sort ### Analysis of insertion sort - correctness: By induction - Time complexty - T(1) = 0 - T(n) = T(n-1) + f(n-1) - **Best case**: f(n-1) = 1 => T(n) = n-1 - **Wrost case**: f(n-1) = n => T(n) = n*(n+1) / 2 - **AVG**: f(n-1) about n/2 => T(n) about n^2/4  :::danger :skull_and_crossbones: 注意: Average case: **絕對不是 (worst + best)/2** ::: :::info #### AVG 如何計算 > 算期望值 - 假設 input N 個數字 - 則總共有 N! 種組合（因為只討論sorting所以只考慮大小排列） ::: ## Analysis of an Algorithm - Correctness - Resources (time, space, ...) consumed - Complexities (worst, avrage, best cases) - Better one exist? - lower bond - >e.g. the lower bond of compare-based sorting is `nlog(n)` - optimality(**Quicksort** is the lower bound of sorting) ### Analysis 的必要性 > 分析演算法是設計者的職責 ~~所以不關我的事~~ - 選擇適當的演算法 - 「適當」的演算法不一定是最快的（達到要求就好） ### Implementation of an Algorithm - Select a suitable data structure & codeing > Program = algorithm + data structure - Empirical(經驗) analysis - Program optimization(優化) - recursion-removal, sentinel(好像跟LOOP有關), tuning, ...)     ### Related Topics in Computation Theory - Machine models - 假設單核，ram 無窮大 - 假設基本運算都是常數時間 - Decidable <-> Undecidable - 有無演算法可以解 - Lower bounds - Tractable <-> Intractable - 找不找的到快的演算法可解 - > A notorious one:`NP-Complete` #### How to Handle Intractable Problem > 這學期不太會講到 - Branch-and-bound - Heuristic algorithm - > Optimization Program - 能得到一個不錯的解，但不保證最佳 - Randomized algorithm - Simulated annealing - genetic algorithm (讓好的解答繁殖，突變，淘汰) - probabilistic algorithm (給出的答案有機率性，多做幾次可信性就可以提高) - Approximation algorithm (有保證就算) - Fixed-parameter algorithm - Others: - quantum, DNA, parallel, neural nets - ...  ## Unit 2 ### Analysis of algorithm #### Issues: - Correctness - ==Time efficiency== - Space(or other resources) efficiency - Optimality > 我們會以討論時間複雜度為主，因為： > 空間通常比較好分析（宣告了哪些空間） > 時間的分析方法也可以套用在空間上 #### Case of analysis - Worst case: 從一樣是輸入長度 n 的輸入內，挑出最差的結果 - Average case: 期望值(uniform distribution) ### Notes on Big-$O$, $\Theta$, $\Omega$ > 有時候大家還是寫成 $O$ 而不是 $\Theta$ > 寫成 $T(n)=O(n)$ 但其實是 $T(n) \in O(n)$ #### The Limitations of asymptotic Notations - $O(n)$ 的執行時間一定會比 $O(n^2)$ 快嗎？ - 理論上會，但是要在 $n$ > 某個 $m$ 的時候 :::info ### 一個不知道該被分在哪裡的東西 - quick sort 可以 random 選擇 pivot 來避免 worst case - merge 算起來比 quick-sort 快，但是這是沒有考慮“搬”的動作的情況下 > 別人比了才搬，merge sort 先搬再說 ::: ### 所有的符號一覽～ - $O(g(n))$ - $\Theta(g(n))$ - $\Omega(g(n))$ - $o(g(n))$ - $\omega(g(n))$ ### Properties of Asymptotic Notations - Transitivity - $\Theta(g(n))$ - Reflexivity - $\Theta(g(n))$ - Symmetry - $\Theta(g(n))$ - Transpose symmetry > 當一個函數滿足 Transitivity, Reflexivity 和 Symmetry，代表**等價**關係。 > 三個符號只有 $\Theta$ 滿足以上三個條件。   :::warning #### 隨堂小測驗 | question | Ans | | ------------------------------------------- | --- | | (i) $n^2 = O(n^3)$ | :O: | | (ii) $n^3 = O(n^2)$ | :X: | | (iii) $2^{n+1} = \Theta(2^n)$ | :O: | | (iv) $(n+1)! = \Theta(n!)$ | :X: | | (v) $f(n)=O(n) -> f(n)*f(n) = O(n^2)$ | :O: | | (vi) $f(n) = O(n) -> 2^{f(n)}$ | :X: | | (vii) $\lg ^{100000}n = o(n^{0.000000001})$ | :O: | | (viii) $n^{1.01} = O(n\lg n)$ | :X: | ::: ### 演算法中常見的函數 | Big-Oh form | Name | |:--------------- | ----------- | | $O(1)$ | Constant | | $O(\lg n)$ | Logarithmic | | $O(n)$ | Linear | | $O(n\lg n)$ | | | $O(n^2)$ | square | | $O(n^3)$ | cube | | $O(n^m), m ≥ 1$ | polynomial | | $O(c^n)$, c > 1 | Exponential | | $O(n!)$ | Factorial | > 只要演算法複雜度到 Exponential，就不用等了.... > 只要 input 稍微大一點，你就算不完了 > 電腦燒掉都跑不出來 --- ### The recursion-tree method $T(n) = T(n/3) + T(2n/3) + n$ ![img_recursion_tree_example](https://i.imgur.com/WiSuKN0.png) > 因此猜測 $n\lg n$ ### The substitution method 1. 先猜一的可能的答案 2. 用數學歸納法證明其之 ### Striling's Formula (or Approximation) - $n! = \sqrt{2πn}(n/e)^n(1+\Theta(1/n))$ > Q: 網路上查到的都沒有後面那個部分$(1+\Theta(1/n))$ > A: 後面的部分是為了表達 n 越大誤差越小，而且誤差在 1/n 的等級 <img src="https://i.imgur.com/H0Vsigg.png" alt="Striling's Formula" width="400"> ### Approximation by Integrals - 用積分來逼近 sigma 的東東 # 0317 ## 矩陣乘法 - 給 n*n 矩陣 - 傳統做法： $\Theta(n^3)$ - 想法：每個矩陣個分成4個 n/2 * n/2 舉證 - T(n) = 8*T(n/2) + $\Theta(n^2)$ - 還是 n^3 - 再用奇怪的方法 - T(n) = 7 * T(n/2) + $\Theta(n^2)$ - T(n) = $\Theta(n^{lg7})$ - $\Theta(n^{2.81})$ ### 長整數運算 - 兩個 n 位整數做乘法 - 傳統：$\Theta(n^2)$ - 可以 n/2 去算，然後用奇怪的分配法減少乘法 - $T(n) \, = \Theta(n^{lg3})$ - = $O(n^{1.585})$ > 這次就用招標的方式吧，想投稿就丟給助教 ### A Stock Buying Problem > STONK![](https://i.imgur.com/fG6PR73.jpg) :::danger **Exercise:** Solve the original stock problem in $O(n)$ time complexity ::: ### Priority Queue & Heap #### Some operations of priority queue - **Construct** a priority queue - **Insert** a new item - **Remove** the largest item (Extract-Max) - **Replace** the largest item with a new item (unless the new item is larger) - **Change** the priority pf an item - **Delete** an arbitrary specified item - **Join** two priority queues into one large one ### Sort' - compaired-based sort: $\Omega(nlgn)$ - other special purpose sort - counting sort - radix sort - bucket sort  ## 0325 ## Dynamic Programming Example: $r_j=max_{1≤i≤j}({p_i+t_{j-i}})$ - Bottom-Up method - Time: $\Theta(n^2)$ - Space $\Theta(n)$ - Top-Down ### Matrix-Chain Multiplication :::info Given a chain of matrices <$A_1, A_2,..., A_n$>, where matrix $A_i$ has dimension $p_{i-1} * p_i$ .... ::: 不同乘法順序會導致不同的複雜度 $A_1 * A_2 * A_3 * A_4$ 13, 5, 89, 3, 34 (A1(A2(A3A4))) => 26418 (A1((A2A3)A4)) => 4055 #### Catalan Number 對於 n+1 個矩陣，括號方式的數量 # = n node 可組成的 Binary tree 數量 = n 組數字經過 stack 後的輸出種類 (push, pop 操作) = n 對括號有多少種配對方式 = n th Catalan Number = $\frac{C^{2n}_n}{n+1}$ = $\Omega(\frac{4^n}{n^{3/2}})≈O(2^n)$ 一對一對應 123 => ()()() 321 => ((())) expression tree #### Solution A1,A2... An k T1, T2 ==TODO==: 畫圖遞迴 ### Steps of developing DP - **Characterize** the structure of a optimal solution - **Derive** a *recursive formula* - **Computing the value** of recursive formula - 寫程式建議使用 **Bottom up** 的方法 - **Construct** an optimal solution from computed information in a "**Top down**" ### Subtleties of Optimal Substructure ### Longest common subsequence > 遇到不知道怎麼解的問題，我喜歡把他變換成其他問題 <x1, x2, ..., xm> <y1, y2, ..., yn> case 1-1: xm != yn then: solve(<x1,...xm>, <y1,...,yn-1>) case 1-2: xm != yn then: solve(<x1,..., xm-1>, <y1,...,yn>) case 2-1: $x_m=y_n$, and they form a match. then: solve(<$x_1, x_2,...,x_{m-1}$>, <$y_1, y_2,..., y_{n-1}$>) + 1 case 2-2: $x_m=y_n$, and they don't form a match. We can change its original pairs to form case 2-1. then: solve(<$x_1, x_2,...,x_{m-1}$>, <$y_1, y_2,..., y_{n-1}$>) + 1 ### Optimal Bianry Search Tree - Definition: $E[$search cost $]$ 最小的 Binary Search Tree ### DP Notes > DP 基本上可以視為聰明的硬做 - DP 子問題不重複做 - DP 需要所有子問題數量不能太大 :::success ### LCS - Improvenments on time - LCS ,, LIS - The Four-Russians Speedup - improvements on space - linear space Algo ::: ## Greedy > 每次都選最好的（~~結果不一定是最好的~~） > Greedy Algorithm Problem: 被證明是可以用 greedy method 來算會是對的 ### Examples #### 辦活動問題 :::warning :slightly_smiling_face: 這題一定會出 ::: - 給定一堆活動（起始時間 ~ 結束時間），活動與活動之間時間可能會衝突，求取最多的活動可以被舉辦 - > 解：Greedy，每次取結束時間最小的 (或最晚開始，因為對稱性) - #### Knapsack Problem (小偷問題) - 找到最有價值的負重，而且背包要能夠承載 - 其他衍生問題 - 0-1 knapsack problem - Fractional knapsack problem (C/P 值最高) - Greedy - (selection problem) ##### 0-1 Knapsack Problem - Time: $O(nK)$ > :heavy_exclamation_mark: a pseudo-polynomial time algorithm > It's possible that $K>2^n$ #### Huffman #### Task-Scheduling Problem - 有 n 個工作 - 期限前做完有獎勵 - 超過期限會有懲罰 ## 4/28 ## Elementary Graph Algorithms ### Königberg Bridge Problem - Euler circuit (一筆畫問題) - Euler grpah: 可以一筆畫走完整張圖且每一條路徑都只有走過一次 ### Hamiltonian Cycle Problem - Hamiltonian cycle ? (應該是走過所有頂點吧？) - Hamiltonian graph ### Utilities Problem > 平面圖定義：邊只在頂點相交 - $\exists$ planar embedding ? (是不是平面圖) - Planar Graph ## 5/19 ### Bellman-ford algorithm - 不斷的對每一個邊做 "Relax" - 是一種 DP <- What!? - > 不能處理負迴圈 - 時間複雜度：$O(VE)$ #### Some tips when implement the algorithm - Is it necessary to do the relaxation for each edge $uv \in E$ ? - 用一個 queue 來紀錄下一次要做 relaxation 的 edge > 實做上有所改進，不過在分析上並沒有改進 > 演算法本身通常都是以精簡的方式呈現，實做時不會直接對著原本的樣子做 [name=教授] ### DAG & DP #### 以剪鋼筋為例子可以當成找最大路徑，點為鋼筋的長度， weight 即是切之後的獲利 ```graphviz digraph { 4->3 [label=""] 4->2 [label=""] 4->1 [label="\n "] 4->0 [label="\n\n "] 3->2 [color="blue" label=""] 3->1 [color="blue" label=""] 3->0 [color="blue" label=""] 2->1 [color="green" label=""] 2->0 [color="green" label=""] 1->0 [label=""] {rank = same; 4; 3; 2; 1; 0} } ``` #### LCS

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.