Introduction Memory 想要同時兼顧速度快且空間大花費又小幾乎是不可能的，必須在Speed與Space間trade off，因此本篇主要講述如何利用有限的Memory資源，透過Memory Hierarchy 達到Memory Access efficiency Principle of Locality Temporal localityitems accessed recently are likely to be accessed again soon Spatial localityitems near those accessed recently are likely to be accessed soon 利用Principle of Locality優勢，Memory可以採用Hierarchy方式存取 Store everything on disk

:bulb: Background pipeline (review)   pipeline 將一個指令分為5個stage (IF、ID、EX、MEM、WB)，使得同一個clock cycle可以同時處理多條指令。   ideal pipeline speed up = # of stages，然而如果each stage執行秒數各不同，受限於執行時間最大的stage，使得speed up 小於理想值。 image :book: Introduction   pipeline存在一種情況使得下一條指令無法在下一個clock cycle 順利執行。這種情形稱為pipeline hazard

資源介紹 Logic Design Fast Adder Data Structure Disjoint Sets Dijkstra's Algorithm Algorithm of MST Red Black Tree

資源介紹 Hi大家好，這裡是關於轉考攻略組文章整合列表，依照文章對應科目進行整合，方便大家快速尋找對應內容 轉考生若想查看考古題，可在側欄尋找，有學長姊們提供的詳解與筆記 (只到109年)  外部資源 (由 K. Wei 學長提供) 編譯器設計概論 演算法概論-Heap and Heap sort 作業系統概論

Introduction Definition 1. subsequence \begin{align} &\text{Given a sequence } X = \langle x_1,x_2,...,x_m \rangle \text{ ,}\ &\text{another sequence } Z = \langle z_1,z_2,...,z_k \rangle \text{ is a }

Introduction Definition :::info Flow networks ::: A flow network $G = (\ V,\ E\ )$ is a directed graph in which each edge $(u,\ v) \in E$ has nonnegative capacity $c \ (u, \ v) \ge 0$ $if \ (u, \ v) \in E \implies (v, u) \not\in E$ (not allow self-loops)

:speech_balloon: 介紹 此為LeetCode 75的解題筆記與紀錄，裡面包含解題Code與想法 先備知識C++ program Dynamic Programming (只有一題用到) 文章分類 (針對初學者) 難度：★★★ ~ ★★★★

:speech_balloon: 介紹 初學Ｃ++時常用Array儲存多筆資料，若欲進行新增與刪除Array第一個元素或最後一個元素需要$\ O(1)$ 時間，但刪除<span class="red">任意位置</span>卻需要$\ O(N)$時間，面臨時常增刪情況顯得很沒有效率，故相較Array而言List符合上述使用情境。 Linked ListLinked List 常見類別Single Linked List Double Linked List Circular Linked List Circular Double Linked List 特點

Half Adder Adds 2 bits, generates sum and carry Step 1: Capture the function Inputs Outputs

Introduction 隨著Binary Search Tree節點成長BST容易產生偏重一邊形成skewed tree，使得資料搜尋時間複雜度變為$O(n)$。為了解決上述問題，現今已有不同的資料結構維持BST平衡，如：AVL Tree、Red Black Tree擁有各自獨特的規則使得BST不會產生歪斜情況發生，而本篇將著重介紹台綜大111考古題出現的Red Black Tree AVL Tree Review Case1-LL image Case2-RR image

Introduction Rods-cutting Problem描述給定長度為$n$ inches的長竿與各個inches所能賣出的價格$p_i\text{ for i = 1, 2, ..., n}$，找出將長竿切成數份分別賣出所能獲得的最大收益。 Given a rod of length n inches and a table of prices p~i~ for i=1,2,...,n, determine the maximum revenue r~n~ obtainable by cutting up the rods and selling the prices Content 1. Observation 假設$n=4$則切法總共有 $2^{n-1} = 2^3 = 8$ 種(包含重複)，如下圖(a)~(h)所示。然而實際上的不重複的切法只有(a)、(b)、(c)、(e)、(h)，其不重複切法總數可用<span class="keyword">partition function</span>表示，其近似值為$e^{\pi\sqrt{2n/3}}/4n\sqrt{3}$。雖然實際不同切法小於$2^{n-1}$，但其數量仍遠大於polynomial $n$。 image image

寒假二三事 前言 大家是否計概已經讀的差不多了呢？大家辛苦了，接下來距離轉學考不到半年的時間，繼續堅持相信離自己心目中的夢想不遠了，寒假將是一段提升自我的好時間，無論讀的如何，這段時間都可以翻盤一切，如果讀的差不多了，加油繼續保持；若是進度不如預期，寒假會是最佳補救時機，不要放棄，一切都還有可能！！！ 接下來這篇會是關於我對寒假期間的一些建議事項供大家參考，希望能夠幫助大家 寒假建議事項 1. 讀原文書內容 雖然政大加入台聯大考試內容似乎有些變化，但離不開基本核心Data storage、Date Manipulation、Operating Systems、Data Structure、Computer Networking...等，無論考題如何變化都大部分的分數都離不開原文書內容，甚至109以前的台聯考古沒見過的名詞或者概念都在兩大原文書冷門章節，題目甚至是課本講解例題。

:speech_balloon: 介紹 Dynamic Programming動態規劃用於解決<span class="blue">最佳化問題(optimization problems)</span>常用的演算法之一，透過將大問題不斷<span class="blue">分割為相關子問題</span>，並<span class="blue">紀錄子問題最佳解</span>回推原始問題的optimal solution即具有<span class="blue">全域解</span>的特性。 :::success :bell: 基本上沒有硬性的先備知識，Dynamic Programming為一種解題方法與思想，可直接閱讀 ::: 先備知識(建議)基本演算法 資料結構

Introduction 本篇將介Set如何利用Data Strucutre表達一個集合(Set)，以便在Graph Algorithm中使用 Content 1. Set Operations Set的操作定義如下 Union($S_i$ , $S_j$) if $S_i$ and $S_j$ are two disjoint sets, then their union

:speech_balloon: 介紹 Dijkstra 演算法的目的為找出G(V, E)圖上某一點到另一點的最短路徑，是一種Greedy Algorithm，搭配Binary Heap來尋找最短路徑所需的時間是O(E log(V))。在現實生活中，它則是應用在網路、地圖、交通...。 :::info G = Graph、 V = Verices (節點)、 E = Edges(邊) ::: :::warning 本篇文章從基礎到進階實作皆有，下面是關於建議閱讀章節

:speech_balloon: 介紹 由於餘數題目在台聯大與台綜大考古題出現過，對於餘數不熟悉的同學常以暴力破解法的方式算餘數，即使知道考題相關概念卻得花費大量時間進行計算，此篇將引入一些離散數學計算技巧節省計算時間。 適合閱讀的人計算機概論有一定基礎 想了解mod題型運算 文章分類 (參考) 難度：★★ 重要程度：★★★

Prerequisites Asymptotics Notation Basic Mathematical Concept Growth of Functions Question 1 How to compare an insertion sort taking $\ c1*n^2$ time and a merge sort taking $\ c2＊nlogn$ time? Which $\ c1$ is much more smaller than $\ c2$.(You can use different methods to prove it) Question 2 Suppose that computer A executes 10 billion instructions per second and computer B executes 10 million instructions per second. How long will it take to sort 10 million numbers on computer A using an algorithm costing $\ 2n^2$. And how long will it take to sort 10 million numbers on computer B using an algorithm costing $\ 50nlog(n)$ ?

Greedy Algorithm 什麼是 Greedy Algorithm（貪婪演算法） 持續找到「目前」最佳解，直到完成「全域」最佳解。 每一步都貪婪！ 貪婪演算法永遠選擇「現在」看起來最佳的解法。 Key Idea 一次做出一個選擇

:book: 介紹 C++為了實現重複使用程式碼(reusability)，所採的方法為繼承，共分成三種繼承方式: public, protected, private。分別能夠使用的member functions, member varibles, access range(存取範圍)有所不同。 繼承權限: public: 可以在原class、繼承的class內使用，也可以在主函式裡面使用 protected: 類似於private，可使用的變數、函式為base的public, protected內的東西，都只能在繼承的class使用 private: 僅能在作宣告的那個class內使用，使用此權限繼承時會將base的public、protected轉成繼承的class的private PS: base為最原本的class。 繼承的class == derived class

:penguin: :penguin: :penguin: :::warning 何謂C++? C語言 + Classes + STL，換句話說就是升級版的C語言，但並非因為升級了就代表它比較好，還有許多硬體、韌體、嵌入式系統是用C語言撰寫。而C＋＋的經典應用也有非常多，一些作業系統或是遊戲都有用到C＋＋，其中經典的遊戲「部落衝突(野豬騎士)」就是用C＋＋寫的。 ::: :::warning