# AI final project discussion

The process of creating the “lego” databases (can be screenshot and/or SQL/non-SQL statements with text explanation) (8pts) $ brew install postgresql@15 $ brew services start postgresql@15 $ createdb lego $ psql lego After creating the database, use the following SQL statement to define the schema of database. create table part_categories ( id integer primary key,

楊宗儒@Sprout2023 Slido slido.com #2895036 先熱身吧 印1000行"Hello Sprout" 計時一分鐘

最小生成樹-Kruskal介紹+證明＋複雜度分析+實作 (https://hackmd.io/@Ben1102/B1i9zhn3O) 最小生成樹-Prim介紹+證明+複雜度分析+實作 (https://hackmd.io/@Ben1102/BkBlC6h2u) 前中序建立二元樹-證明+實作 (https://hackmd.io/@Ben1102/SkfdIsq2O) BST的退化與解決方法

介紹 queue是一種具有先進先出(FIFO, First-In-First-Out)性質的資料容器，也就是最先被放入的資料會被最先取出。 在生活中，queue通常被用於類似排隊的情形，先入隊的人會先出隊，也就符合queue的性質。 一般來說，queue支援以下操作： push(data)：將資料放入queue的最後。 pop()：將queue最前的資料丟出。 front()：存取queue最前的資料

介紹 stack是一種具有後入先出(Last-In-First-Out, LIFO)性質的資料容器，也就是最後被放進容器的資料，會最先被取出。 以生活的例子來說，一疊堆起來的盤子就具有stack的性質，因為在沒有取出額外的盤子的情況下，只有最上方的盤子能夠被取出，也只能從最上方放入。 事實上，stack是個抽象的觀念，只要符合First-In-Last-Out的性質，我們都會稱之為stack。 一般來說，stack會支援以下操作: push(data)：將資料放入stack的最上方

介紹 霍夫曼編碼是美國計算機科學家大衛．霍夫曼在1952年提出的一種無失真資料壓縮編碼（在保留完整資訊的前提下進行壓縮）。藉由根據字頻的大小選定不同編碼長度，來減少編碼總長的期望值，達到資料壓縮的目的。由於霍夫曼編碼是個二進制的編碼，所以字元集與編碼的對應可以用一個01-Trie來表達，也就是可以使用一個二元樹來表達。 本圖由此網站生成 上圖即是一個霍夫曼樹，基於文本"can you can a can with a cucumber"。首先，由觀察可以得知所有字元皆在樹的葉子上，這是因為要避免一個字元的編碼同時是另一個字元編碼的前綴，導致有多種解碼結果。此外，可以觀察到頻率較高的字元(如'空白'、'c')擁有更短的編碼，如此能夠有效地降低編碼的總長。 如何建立霍夫曼樹 以下將基於"to be or not to be"的文本進行建樹。 首先，統計各字元的出現頻率

記憶體的功用，是提供處理器存取資料，在需要時再進行存取。因此，記憶體對於每個程式而言，都是珍貴的資源。而負責分配記憶體的工作，是由作業系統負責。本文將介紹有關記憶體在一個程式中的分配。 程式的記憶體分配 記憶體分配的示意圖。圖源 一個程式在分配到記憶體後，會被分配為四個部分： Code, Static/Global, Stack和Heap。 Code的部分會儲存程式所需要的指令。

BST的退化 當我們使用BST時，通常會希望節點的分佈是平均的，也就是理想情況下BST任一節點的左右子樹大小越接近越好，這樣樹的深度可以盡可能減小。 然而在最壞的情況下，樹上每個節點可能只有左或右子節點，導致樹的深度即是樹的大小，讓BST退化成一個Linked-List，讓一些複雜度與樹高有關的操作的複雜度從$O(logn)$變成$O(n)$，大幅降低了效率。因此，我們需要維持BST的平衡來防止此事的發生。 上圖是一個退化成Linked-List的樹(圖源) 二元樹的平衡 二元樹的平衡主要有兩種方法：基於樹旋轉與基於隨機平衡，還有其他不常見的方法，在此處不多做介紹。兩種方法各有其優缺點，以下是兩種方法的介紹：

給定一連通帶權無向圖G(V,E)，有n條邊，一個生成樹T就是一個有n-1條邊的連通子圖，求出邊權和最小的T。 Prim演算法概述 Prim演算法步驟如下： 選擇圖上任一頂點為起始點 初始化：$V_{new}={x}$，$x$為選定的起始點，$E_{new}={}$ 重複以下步驟直到$V_{new}=V$： 在E中選權重最小的邊$(u,v)$滿足$u \in V_{new} ,v \in V\backslash V_{new}$

最小生成樹介紹 給定一連通帶權無向圖G(V,E)，有n條邊，一個生成樹T就是一個有n-1條邊的連通子圖，求出邊權和最小的T。 對於此問題，經典的演算法有Kruskal與Prim兩種演算法，將會以兩篇文章來介紹。 Kruskal演算法概述 Kruskal演算法的步驟如下： 將所有邊由小到大排序為$e_1,e_2,...,e_m$。

有一個包含N個節點的二元樹，其中有節點1~N（數字不會重複），給定前序和中序走訪的結果，請求出這棵二元樹後序走訪的結果。 唯一性證明 首先我們先證明，給定一棵二元樹的前序與中序走訪，可以決定出唯一的二元樹 整個證明是利用數學歸納法來進行證明，架構如下: 當N=1時，命題顯然成立。 設N<=k時命題成立。 證明N=k+1時命題成立。

對答案二分搜是個針對模擬問題的一種優化方式，在結果的上下界容易求出，並且結果具有單調性，就能利用二分搜來進行優化。 二分搜 給定一升序排序過的整數陣列，大小為n，給定一整數d，求陣列中第一個$\geq n$的數字的index。 首先第一個最直接的想法，就是直接將整個陣列掃描一遍，直到找到第一個$\geq n$的數字即可。然而這樣的演算法效率較差，複雜度為$O(n)$。 再次觀察題目，會發現我們沒有充分利用陣列是升序排序過的性質。如果在一個位置的數字小dn，那在其左邊的位置皆不可能是答案，同樣地，如果一個數字大於等於d，那答案一定不會在它的右邊。利用這個性質，我們可以每次都從要搜尋的區間檢查其最中間的數字，然後用結果來更新搜尋區間的左右界。由於每次搜尋區間都會被切一半，複雜度為$O(logn)$，大幅度地優化了演算法。