Algorithms Lab for Online Course

--- tags: computer science, algorithm, data structure, leetcode --- # **Algorithms Lab Online Course** <div> "Premature optimization is the root of all evil." -- <a href = "https://en.wikipedia.org/wiki/Donald_Knuth">Donald Ervin Knuth</a> (1938-) "If you want to master something, teach it. The more you teach, the better you learn. Teaching is a powerful tool to learning." -- <a href = "https://en.wikipedia.org/wiki/Richard_Feynman">Richard Feynman</a> (1918-1988)  </div> ### Goal This short course is designed for students who plan to learn about common data structures with efficient algorithms, solve [LeetCode](https://leetcode.com/) problems, and know state-of-the-art information techniques. The achievements of **Algorithms Lab** are listed below: <img src = "https://i.imgur.com/IjQYhVQ.png" height = 150px style="float:right"/> - Develop problem-solving skills; - Implement data structures and algorithms; - Expand horizons by solving problems; - Solve LeetCode problems which are marked medium, even hard. ### Instructor Information * Instructor name: 盧政良 (Zheng-Liang Lu, Arthur) * Email address: arthurzllu@gmail.com ### Textbook - Robert Sedgewick and Kevin Wayne, <a href = "https://algs4.cs.princeton.edu/lectures/">Algorithms</a>, 4/e, 2011 ![](https://i.imgur.com/HHMLOiF.png =100x) - You may also follow the course [COS 226 Data Structures and Algorithms](https://www.cs.princeton.edu/courses/archive/fall23/cos226/syllabus.php) for further studies. ### Programming Languages - Mainly use [Java](https://www.csie.ntu.edu.tw/~d00922011/java.html) in most of slides. - You could also use C, [C++](https://www.csie.ntu.edu.tw/~d00922011/cpp.html), [C#](https://www.csie.ntu.edu.tw/~d00922011/csharp.html), [Python](https://hackmd.io/@arthurzllu/HJNXq84SO) and JavaScript in this course. - I also plan to organize a reference table for multiple languages. Check out this [page](https://docs.google.com/spreadsheets/d/e/2PACX-1vSK9NZyZJIH-pU2Ta6m1sbHNb1OYpyRk113JctcEonKYSIRvUOEM8VM7J-b0haYfRNGgE2VYaya-wA7/pubhtml?gid=0&single=true). You are welcomed to leave comments for this work. - More about how to set up your development environment could be found [here](https://hackmd.io/@arthurzllu/ry-PIcBlO). ## **Syllabus** ### ++**Analysis of Algorithms**++ - Lecture slides - Analysis of algorithms: a quick review [link](https://www.csie.ntu.edu.tw/~d00922011/java2/big_O.pdf) - About log-time algorithms [link](https://www.csie.ntu.edu.tw/~d00922011/java/log-time_algorithm.pdf) - Selected problems - **78. Subsets** https://leetcode.com/problems/subsets/ - **509. Fibonacci Number** https://leetcode.com/problems/fibonacci-number/ - **50. Pow(x, n)** https://leetcode.com/problems/powx-n/ - Supplementary materials - https://algs4.cs.princeton.edu/lectures/keynote/14AnalysisOfAlgorithms.pdf - https://www.bigocheatsheet.com/ - Steven Halim, https://visualgo.net/en - Rodrigo Pontes and David Galles, [CS1332 Data Structures and Algorithms Visualizations](https://csvistool.com/), 2011 - J. Hartmanis and R. E. Stearns, [On the Computational Complexity of Algorithms](https://www.ams.org/journals/tran/1965-117-00/S0002-9947-1965-0170805-7/S0002-9947-1965-0170805-7.pdf), 1965 - DeepMind: AlphaGo 2017 [youtube](https://www.youtube.com/watch?v=WXuK6gekU1Y&ab_channel=DeepMind) - Zheng-Liang Lu, [High School Math in Computer Science](https://hackmd.io/@arthurzllu/r1yS6hxqc), 2022 <center> ![](https://i.imgur.com/iVvwBzn.png =300x) </center> ---- ### ++**Array**++ - Concept check - The main [memory](https://www.anandtech.com/show/15912/ddr5-specification-released-setting-the-stage-for-ddr56400-and-beyond) can be regarded as an array (the biggest one). - An array occupies one continuous space in the memory. - Note that array memory allocation is actually continuous in the [virtual memory](https://pages.cs.wisc.edu/~remzi/OSTEP/vm-intro.pdf). - Why is the first element of arrays starting from the array index 0? ```Java= public static void main(String[] args) { int[] A = new int[3]; A[0] = 100; A[1] = 200; A[2] = 300; System.out.println(A[0]); // print 100. } /* * This "rule" is also applicable in C, C++, C#, JavaScript, Python, PHP, * Go, Rust, etc. * Note that the first element of arrays starts with 1 in MATLAB, R, and * Julia. */ ``` - Make sure that you understand the sketch of memory allocation, especially the stack and the heap of the memory. - See also [Java 面試 - JVM 的 Stack 和 Heap](https://blog.marklee.tw/java-interview-jvm-stack-heap/). - See also [Memory Management in Python](https://www.honeybadger.io/blog/memory-management-in-python/). - See also [Stack and Heap Memory in C#](https://dotnettutorials.net/lesson/stack-and-heap-dotnet/). - See also [Memory Management in JavaScript](https://www.geeksforgeeks.org/memory-management-in-javascript/). - See also [Memory allocations in Go](https://dev.to/karankumarshreds/memory-allocations-in-go-1bpa). - [The Go Memory Model](https://go.dev/ref/mem) - See also [Memory management in The Rust Programming Language](https://web.mit.edu/rust-lang_v1.25/arch/amd64_ubuntu1404/share/doc/rust/html/book/first-edition/the-stack-and-the-heap.html). - How about the following code snippet? ```java= String[] A = { "ntu", "csie", "algorithm" }; ``` - Selected problems - **27. Remove Element** https://leetcode.com/problems/remove-element/ - **674. Longest Continuous Increasing Subsequence** https://leetcode.com/problems/longest-continuous-increasing-subsequence/solution/ - LeetCode learning cards - [https://leetcode.com/explore/learn/card/fun-with-arrays/](https://leetcode.com/explore/learn/card/fun-with-arrays/) - [https://leetcode.com/explore/learn/card/array-and-string/](https://leetcode.com/explore/learn/card/array-and-string/) - [https://leetcode.com/explore/learn/card/queue-stack/](https://leetcode.com/explore/learn/card/queue-stack/) - Supplementary materials - Christopher Moretti, [Storage Hierarchy, Caching, and Locality](https://www.cs.princeton.edu/courses/archive/fall20/cos217/lectures/16_StorageHierarchy.pdf), Princeton Unversity, 2020fa - Ulrich Drepper, [What Every Programmer Should Know About Memory](https://www.akkadia.org/drepper/cpumemory.pdf)</a>, 2007 <center> ![](https://hackmd.io/_uploads/H1GlMxXqi.jpg =600x) ![](https://i.imgur.com/XpEgwaD.png =400x) </center> ---- ### ++**Recursion**++ - Concept check - Try https://pythontutor.com/visualize.html - Can you describe the program flow in the stack during the execution of the following code snippet? ```java= public static void main(String[] args) { int x = 1, y = 2; int z = max(x, y); } public static int max(int a, int b) { return a > b ? a : b; // Halt at this line. /* equivalent to the following code snippet: if (a > b) return a; else return b; */ } ``` - LeetCode learning cards - [https://leetcode.com/explore/learn/card/recursion-i/](https://leetcode.com/explore/learn/card/recursion-i/) - [https://leetcode.com/explore/learn/card/recursion-ii/](https://leetcode.com/explore/learn/card/recursion-ii/) - Supplementary materials - Equivalence between iteration (loops) and recursion? - Martin Davis, [The Church-Turing Thesis: Consensus and Opposition](https://link.springer.com/chapter/10.1007/11780342_13), 2005 - Udi Boker and Nachum Dershowitz, [What is the Church-Turing Thesis?](http://www.cs.tau.ac.il/~nachumd/papers/CTsurvey.pdf) - Problem set https://leetcode.com/tag/recursion/ - **1137. N-th Tribonacci Number** https://leetcode.com/problems/n-th-tribonacci-number/ <center> ![](https://i.imgur.com/HtvMBLw.png =500x) </center> ---- ### ++**Sorting & Searching**++ - Lecture slides - (FYR) https://algs4.cs.princeton.edu/lectures/keynote/21ElementarySorts.pdf - (FYR) https://algs4.cs.princeton.edu/lectures/keynote/22Mergesort.pdf - (FYR) https://algs4.cs.princeton.edu/lectures/keynote/23Quicksort.pdf - Leetcode learning cards - https://leetcode.com/explore/learn/card/binary-search/ - https://leetcode.com/explore/learn/card/heap/ - Supplementary materials - Sorting by distribution: counting sort, bucket sort, and radix sort - http://www.cs.nthu.edu.tw/~wkhon/algo09/lectures/lecture6.pdf - Selected problem sets - Sorting https://leetcode.com/tag/sorting/ - Searching https://leetcode.com/tag/binary-search/ - **34. Find First and Last Position of Element in Sorted Array** https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/ - **704. Binary Search** https://leetcode.com/problems/binary-search/ - **35. Search Insert Position** https://leetcode.com/problems/search-insert-position/ - **69. Sqrt(x)** https://leetcode.com/problems/sqrtx/ ---- ### ++**Linked List**++ <center> ![](https://i.imgur.com/3GQZWOU.png =450x) Source https://www.educative.io/ </center> - Lecture slides - https://algs4.cs.princeton.edu/lectures/keynote/13StacksAndQueues.pdf - Stack: FILO behavior, order reversing. - Selected problems - **20. Valid Parentheses** https://leetcode.com/problems/valid-parentheses/ - Queue: FIFO behavior, buffering; see also [priority queues](https://en.wikipedia.org/wiki/Priority_queue) (stay tuned). - LeetCode learning card - [https://leetcode.com/explore/learn/card/linked-list/](https://leetcode.com/explore/learn/card/linked-list/) - Problem set https://leetcode.com/tag/linked-list/ - **876. Middle of the Linked List** https://leetcode.com/problems/middle-of-the-linked-list/ - **160. Intersection of Two Linked Lists** https://leetcode.com/problems/intersection-of-two-linked-lists/ - **206. Reverse Linked List** https://leetcode.com/problems/reverse-linked-list - **237. Delete Node in a Linked List** https://leetcode.com/problems/delete-node-in-a-linked-list - **83. Remove Duplicates from Sorted List** https://leetcode.com/problems/remove-duplicates-from-sorted-list/ - **24. Swap Nodes in Pairs** https://leetcode.com/problems/swap-nodes-in-pairs/ - **19. Remove Nth Node From End of List** https://leetcode.com/problems/remove-nth-node-from-end-of-list - **141. Linked List Cycle** https://leetcode.com/problems/linked-list-cycle/ - **234. Palindrome Linked List** https://leetcode.com/problems/palindrome-linked-list/ - **707. Design Linked List** https://leetcode.com/problems/design-linked-list/ - **21. Merge Two Sorted Lists** https://leetcode.com/problems/merge-two-sorted-lists/ - **23. Merge k Sorted Lists** https://leetcode.com/problems/merge-k-sorted-lists/ - **2. Add Two Numbers** https://leetcode.com/problems/add-two-numbers/ - **203. Remove Linked List Elements** https://leetcode.com/problems/remove-linked-list-elements/ - Supplementary materials - Two-pointer technique - https://leetcode.com/articles/two-pointer-technique/ - haogroot, [Two Pointer 快慢指標篇](https://haogroot.com/2020/09/07/two-pointer-leetcode/) - [雙指標技巧總彙](https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484505&idx=1&sn=0e9517f7c4021df0e6146c6b2b0c4aba&chksm=9bd7fa51aca07347009c591c403b3228f41617806429e738165bd58d60220bf8f15f92ff8a2e&scene=21#wechat_redirect) - Sorting linked lists - http://www.cs.ecu.edu/karl/3300/spr16/Notes/DataStructure/List/listsort.html - https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html - Implementation in Linux kernel: https://github.com/torvalds/linux/blob/master/lib/list_sort.c - Jserv, [你所不知道的 C 語言: linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list) - https://www.data-structures-in-practice.com/intrusive-linked-lists/ - If you are interested in design patterns, you may refer to the booklist [here](https://www.csie.ntu.edu.tw/~d00922011/java.html#Object-Oriented-Analysis-amp-Design). ---- ### ++**Tree**++ <center> ![](https://i.imgur.com/BDjyt7A.png =400x) Source https://www.educative.io/ </center> - Lecture slides - Binary search tree https://algs4.cs.princeton.edu/lectures/keynote/32BinarySearchTrees.pdf - Selected problems :::spoiler Expand - **700. Search in a Binary Search Tree** https://leetcode.com/problems/search-in-a-binary-search-tree/ - **701. Insert into a Binary Search Tree** https://leetcode.com/problems/insert-into-a-binary-search-tree/ - **450. Delete Node in a BST** https://leetcode.com/problems/delete-node-in-a-bst/ - **98. Validate Binary Search Tree** https://leetcode.com/problems/validate-binary-search-tree/ - **226. Invert Binary Tree** https://leetcode.com/problems/invert-binary-tree/ - Follow-up question: use iteration to avoid stack overflow. - **94. Binary Tree Inorder Traversal** https://leetcode.com/problems/binary-tree-inorder-traversal/ - Traversal: 走訪 - **144. Binary Tree Preorder Traversal** https://leetcode.com/problems/binary-tree-preorder-traversal/ - **145. Binary Tree Postorder Traversal** https://leetcode.com/problems/binary-tree-postorder-traversal/ - **105. Construct Binary Tree from Preorder and Inorder Traversal** https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ - https://medium.com/@ChYuan/leetcode-no-105-construct-binary-tree-from-preorder-and-inorder-traversal-%E5%BF%83%E5%BE%97-medium-12dd4fcfa654 - **106. Construct Binary Tree from Inorder and Postorder Traversal** https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ - **102. Binary Tree Level Order Traversal** https://leetcode.com/problems/binary-tree-level-order-traversal/ - **429. N-ary Tree Level Order Traversal** https://leetcode.com/problems/n-ary-tree-level-order-traversal/ - **112. Path Sum** https://leetcode.com/problems/path-sum/ - **113. Path Sum II** https://leetcode.com/problems/path-sum-ii/ - **99. Recover Binary Search Tree** https://leetcode.com/problems/recover-binary-search-tree/ - **104. Maximum Depth of Binary Tree** https://leetcode.com/problems/maximum-depth-of-binary-tree/ - **111. Minimum Depth of Binary Tree** https://leetcode.com/problems/minimum-depth-of-binary-tree/ - **559. Maximum Depth of N-ary Tree** https://leetcode.com/problems/maximum-depth-of-n-ary-tree/ - **404. Sum of Left Leaves** https://leetcode.com/problems/sum-of-left-leaves/ - **1373. Maximum Sum BST in Binary Tree** https://leetcode.com/problems/maximum-sum-bst-in-binary-tree/ - **655. Print Binary Tree** https://leetcode.com/problems/print-binary-tree/ - **965. Univalued Binary Tree** https://leetcode.com/problems/univalued-binary-tree/ - **572. Subtree of Another Tree** https://leetcode.com/problems/subtree-of-another-tree/ - **530. Minimum Absolute Difference in BST** https://leetcode.com/problems/minimum-absolute-difference-in-bst/ ::: - Balanced search tree & red-black (RB) tree https://algs4.cs.princeton.edu/lectures/keynote/33BalancedSearchTrees.pdf - **109. Convert Sorted List to Binary Search Tree** https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/ - **110. Balanced Binary Tree** https://leetcode.com/problems/balanced-binary-tree/ - **1382. Balance a Binary Search Tree** https://leetcode.com/problems/balance-a-binary-search-tree/ - Supplementary materials - Tree traversal - https://en.wikipedia.org/wiki/Tree_traversal - Preorder traversal: depth-first search (DFS), tree cloning. - Postorder traveral: reverse Polish notation, freeing tree nodes. - Red-black tree - Robert Sedgewick (2008): https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf - Eddie Kohler: [Left-Leaning Red-Black Trees Considered Harmful](https://read.seas.harvard.edu/~kohler/notes/llrb.html) - 2-3-4 tree and red-black tree: https://www.cs.purdue.edu/homes/ayg/CS251/slides/chap13b.pdf - Red-black tree and AA tree: http://ccf.ee.ntu.edu.tw/~yen/courses/ds17/chapter-4g.pdf - Jserv, [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree) - 紅黑樹 (附完整 C 代碼) https://www.itread01.com/articles/1476031214.html - 對各種樹的整理 https://warmgrid.github.io/2019/06/14/about-trees.html - ASTs, Grammars, Parsing, Tree Traversals https://www.cs.cornell.edu/courses/cs2110/2018fa/L14-Trees/L14-ParsingTrees.pdf - More about the B tree and its variants: - https://zh.wikipedia.org/zh-tw/B樹 - Difference between the B tree and the B+ tree: https://www.javatpoint.com/b-plus-tree - 為什麼 MySQL 使用 B+ 樹 https://draveness.me/whys-the-design-mysql-b-plus-tree/ - Let's Build a Simple Database https://cstack.github.io/db_tutorial/ - Splay tree - https://www.cs.umd.edu/class/fall2020/cmsc420-0201/Lects/lect10-splay.pdf - http://dept.cs.williams.edu/~cs136/lectures/aaron/25-splay.pdf - A proof of time complexity for BST deletion (why $\sqrt{n}$ per op?): https://dl.acm.org/doi/pdf/10.1145/22145.22168 - Why not construct a binary search tree in a 1D array? - Deletion in RB tree: https://hackmd.io/@sysprog/linux-rbtree#%E7%B4%85%E9%BB%91%E6%A8%B9%E7%9A%84%E7%A7%BB%E9%99%A4 - LeetCode learning cards - [https://leetcode.com/explore/learn/card/data-structure-tree/](https://leetcode.com/explore/learn/card/data-structure-tree/) - [https://leetcode.com/explore/learn/card/n-ary-tree/](https://leetcode.com/explore/learn/card/n-ary-tree/) - [https://leetcode.com/explore/learn/card/introduction-to-data-structure-binary-search-tree/](https://leetcode.com/explore/learn/card/introduction-to-data-structure-binary-search-tree/) - Problem set: https://leetcode.com/tag/tree/ ---- ### ++**Hashing**++ <center> ![](https://i.imgur.com/vQOtzJK.png =500x) Source https://miro.medium.com/max/3856/1*SCHCrY-GeCGjSbVk7P8kaQ.png </center> - Lecture slides https://algs4.cs.princeton.edu/lectures/keynote/34HashTables.pdf - Problem set https://leetcode.com/tag/hash-table/ - **1. Two Sum** https://leetcode.com/problems/two-sum/ - **204. Count Primes** https://leetcode.com/problems/count-primes/ - **217. Contains Duplicate** https://leetcode.com/problems/contains-duplicate/ - **219. Contains Duplicate II** https://leetcode.com/problems/contains-duplicate-ii/ - **929. Unique Email Addresses** https://leetcode.com/problems/unique-email-addresses/ - **706. Design HashMap** https://leetcode.com/problems/design-hashmap/ - **705. Design HashSet** https://leetcode.com/problems/design-hashset/ - **311. Sparse Matrix Multiplication** https://leetcode.com/problems/sparse-matrix-multiplication - **299. Bulls and Cows** https://leetcode.com/problems/bulls-and-cows/ - **348. Design Tic-Tac-Toe** https://leetcode.com/problems/design-tic-tac-toe - **146. LRU Cache** https://leetcode.com/problems/lru-cache/ - **460. LFU Cache** https://leetcode.com/problems/lfu-cache/ - Don't use hashtable in the following problems: - **1748. Sum of Unique Elements** https://leetcode.com/problems/sum-of-unique-elements/ - Supplementary materials - Bitwise operations - https://en.wikipedia.org/wiki/Two%27s_complement - Selected problem set: https://leetcode.com/tag/bit-manipulation/ - **190. Reverse Bits** https://leetcode.com/problems/reverse-bits/ - **191. Number of 1 Bits** https://leetcode.com/problems/number-of-1-bits/ - **371. Sum of Two Integers** https://leetcode.com/problems/sum-of-two-integers/ - **231. Power of Two** https://leetcode.com/problems/power-of-two/ - Secure Hash Algorithms https://en.wikipedia.org/wiki/Secure_Hash_Algorithms - Cryptography https://en.wikipedia.org/wiki/Cryptography - Creating your first blockchain with Java: [link](https://medium.com/programmers-blockchain/create-simple-blockchain-java-tutorial-from-scratch-6eeed3cb03fa) - https://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/ - Python Hash Tables: Understanding Dictionaries [link](http://thepythoncorner.com/dev/hash-tables-understanding-dictionaries/) - Cuckoo Hashing [wiki](https://en.wikipedia.org/wiki/Cuckoo_hashing) - Daniel Jslin, [List, HList, and Hash Table](https://danielmaker.github.io/blog/linux/list_hlist_hashtable.html) (in C), 2016-11-20 - Checksum https://en.wikipedia.org/wiki/Checksum <center> ![](https://i.imgur.com/uwdjOko.png =400x) Source [link](https://computersciencewiki.org/images/thumb/2/24/One_way_function.png/600px-One_way_function.png) </center> ---- ### ++**Graph**++ <center> ![](https://i.imgur.com/hFx7ZSE.jpg =550x) </center> - Lecture slides - Undirected graphs https://algs4.cs.princeton.edu/lectures/keynote/41UndirectedGraphs.pdf - Depth-first search (DFS) implementated by recursion or stacks. - MazeDemo: https://www.csie.ntu.edu.tw/~d00922011/java/Maze.jar - Breadth-first search (BFS) implemented by queues. - Problem set: https://leetcode.com/tag/graph/ - **1971. Find if Path Exists in Graph** https://leetcode.com/problems/find-if-path-exists-in-graph/ - **133. Clone Graph** https://leetcode.com/problems/clone-graph - **200. Number of Islands** https://leetcode.com/problems/number-of-islands/ - **463. Island Perimeter** https://leetcode.com/problems/island-perimeter/ - **547. Number of Provinces** https://leetcode.com/problems/number-of-provinces/ - **323. Number of Connected Components in an Undirected Graph** https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/ - **785. Is Graph Bipartite?** https://leetcode.com/problems/is-graph-bipartite/ - Try to reduce to [2-coloring](https://en.wikipedia.org/wiki/Graph_coloring). - **886. Possible Bipartition** https://leetcode.com/problems/possible-bipartition/ <img src = "https://hackmd.io/_uploads/rk58TQLA9.png" height = 100px style="float:right"/> - Directed graphs https://algs4.cs.princeton.edu/lectures/keynote/42DirectedGraphs.pdf - Topological sort - Problem set https://leetcode.com/tag/topological-sort/ - **207. Course Schedule** https://leetcode.com/problems/course-schedule/ - **210. Course Schedule II** https://leetcode.com/problems/course-schedule-ii/ - **1462. Course Schedule IV** https://leetcode.com/problems/course-schedule-iv/ - Strongly connected components https://leetcode.com/tag/strongly-connected-component/ - Case study: the PageRank algorithm [pdf](https://web.archive.org/web/20110818093436/http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf) - Take the stock market as an example for transition matrices or [Markov chains](https://en.wikipedia.org/wiki/Markov_chain): https://en.wikipedia.org/wiki/Examples_of_Markov_chains#Stock_market - Allen B. Downey, [PageRank](https://allendowney.github.io/DSIRP/pagerank.html), 2021 - Brain, [PageRank：最大的SEO排名因素，５分鐘弄懂SEO的核心演算法知識](https://hubofcontent.com/seo-101/pagerank.html), 2021-05-18 - Chonyy, [PageRank: Link Analysis Explanation and Python Implementation from Scratch](https://towardsdatascience.com/pagerank-3c568a7d2332), 2021-01-08 - iLeafy11, [Desktop Search and PageRank Parallelization](https://hackmd.io/@qJEZpNvuSHe0kzJAmMSeQg/ByXZQ1nMi), 2023 - Minimum spanning trees https://algs4.cs.princeton.edu/lectures/keynote/43MinimumSpanningTrees.pdf - ++Union-find algorithm++ https://algs4.cs.princeton.edu/lectures/keynote/15UnionFind.pdf - Iterated log function: https://en.wikipedia.org/wiki/Iterated_logarithm - Problem set https://leetcode.com/tag/union-find/ - ++Priority queue++ https://algs4.cs.princeton.edu/lectures/keynote/24PriorityQueues.pdf - Case study: [collision simulation](https://www.csie.ntu.edu.tw/~d00922011/java2/CollisionSystem.zip) - Problem set https://leetcode.com/tag/heap-priority-queue/ - **167. Two Sum II - Input Array Is Sorted** https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/ - **215. Kth Largest Element in an Array** https://leetcode.com/problems/kth-largest-element-in-an-array/ - **347. Top K Frequent Elements** https://leetcode.com/problems/top-k-frequent-elements - **378. Kth Smallest Element in a Sorted Matrix** https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/ - **502. IPO** https://leetcode.com/problems/ipo/description/ - **703. Kth Largest Element in a Stream** https://leetcode.com/problems/kth-largest-element-in-a-stream/ - **973. K Closest Points to Origin** https://leetcode.com/problems/k-closest-points-to-origin/ - Practical view - For sparse graphs, use Kruskal's algorithm; use Prim's if your graph is dense. - Can we find a cutoff of graph size $E$ to determine which algorithm should be used? - Problem set https://leetcode.com/tag/minimum-spanning-tree/ - **1135. Connecting Cities With Minimum Cost** https://leetcode.com/problems/connecting-cities-with-minimum-cost/ - **1584. Min Cost to Connect All Points** https://leetcode.com/problems/min-cost-to-connect-all-points/ - Shortest paths https://algs4.cs.princeton.edu/lectures/keynote/44ShortestPaths.pdf - Problem set https://leetcode.com/tag/shortest-path/ - Applications - Shai Avidan and Ariel Shamir, [Seam Carving for Content-Aware Image Resizing](https://inst.eecs.berkeley.edu/~cs194-26/fa16/hw/proj4-seamcarving/imret.pdf), 2007 - [Caire](https://github.com/esimov/caire) is a content aware image resize library based on Seam Carving for Content-Aware Image Resizing paper. - Graham Gobieski, Kevin Kwan, Ziyi Zhu, and Shang Li, [High-Frequency Foreign Exchange Currency Trading](http://www.cs.columbia.edu/~sedwards/classes/2016/4840-spring/designs/FOREX.pdf), 2016 - William Fiset, [Bellman Ford Algorithm | Shortest path & Negative cycles | Graph Theory](https://www.youtube.com/watch?v=lyw4FaxrwHg), 2018 - Supplementary materials<img src = "https://hackmd.io/_uploads/ryTfSGP83.png" height = 200px style="float:right"/> - Maximum flow https://algs4.cs.princeton.edu/lectures/keynote/64MaxFlow.pdf - More problems on graphs [link](http://web.ntnu.edu.tw/~algo/Domination.html) - Packing: independent set, clique - Covering: vertex cover, edge covering, set covering - Microsoft, [Influence Maximization](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/kdd12-tutorial-inf-part-iii.pdf), KDD-2012 - Ju Fan, [Influence Maximization on Big Social Graphs](http://iir.ruc.edu.cn/~fanj/talks/im-tsinghua.pdf), Renmin University of China, 2017 - Andrea Marino, [Graph Clustering Algorithms](https://pages.di.unipi.it/marino/cluster18.pdf), 2018 - The handshaking theorem states that $\sum_{v \in V} \text{degree}(v) = 2 \times |\,E\,|$ for any graph $G(V, E).$ - Tarjan's algorithm - https://bbs.huaweicloud.com/blogs/240222 - [Biconnectivity](https://en.wikipedia.org/wiki/Biconnected_graph ) and articulation point - https://cp-algorithms.com/graph/cutpoints.html - Graph coloring - 4-coloring: https://thomas.math.gatech.edu/FC/fourcolor.html - You could find some selected coloring problems in [演算法筆記](https://web.ntnu.edu.tw/~algo/Coloring.html). - If you are interested in graph theory, you may start from this book: https://link.springer.com/book/10.1007/978-3-319-49475-3 - [Journal of Graph Algorithms and Applications](https://jgaa.info/) - You can find Python implementation for graphs below: - https://networkx.org/ <center> ![](https://i.imgur.com/p2R0X0K.png =500x) Source https://xkcd.com/399/ </center> ---- ### ++**Strings**++ - Lecture slides - Key-indexed counting, LSD/MSD radix sort: https://algs4.cs.princeton.edu/lectures/keynote/51StringSorts.pdf - R-way trie and ternary search trie (TST): https://algs4.cs.princeton.edu/lectures/keynote/52Tries.pdf - **208. Implement Trie (Prefix Tree)** https://leetcode.com/problems/implement-trie-prefix-tree/ - Substring search using the Knuth-Morris-Prat (KMP) algorithm: https://algs4.cs.princeton.edu/lectures/keynote/53SubstringSearch.pdf - **1408. String Matching in an Array** https://leetcode.com/problems/string-matching-in-an-array/ - Regular expressions: https://algs4.cs.princeton.edu/lectures/keynote/54RegularExpressions.pdf - You may try some examples for regular expressions here: https://regexone.com/ - You can find packages/modules for the regular expressions here: [Java](https://docs.oracle.com/en/java/javase/18/docs/api/java.base/java/util/regex/package-summary.html), [Python](https://docs.python.org/3/library/re.html), [grep](https://man7.org/linux/man-pages/man1/grep.1.html) in Linux. - Selected problems - **10. Regular Expression Matching** https://leetcode.com/problems/regular-expression-matching/ - **44. Wildcard Matching** https://leetcode.com/problems/wildcard-matching/ - Data compression: https://algs4.cs.princeton.edu/lectures/keynote/55DataCompression.pdf - **443. String Compression** https://leetcode.com/problems/string-compression/ - Explain why the Huffman algorithm generates prefix-free codewords. - Supplementary materials - Information theory - Claude E. Shannon (1948): [A Mathematical Theory of Communication](https://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf) - Illustration for entropy: https://www.youtube.com/watch?v=v68zYyaEmEA - JPEG compression - https://web.stanford.edu/class/ee376a/files/irena_lecture.pdf - Morse's code - https://en.wikipedia.org/wiki/Morse_code - https://www.youtube.com/watch?v=xsDk5_bktFo - https://www3.nd.edu/~busiforc/handouts/cryptography/letterfrequencies.html ---- ### ++**Dynamic Programming**++ - Lecture slides - Fibonacci number: https://www.csie.ntu.edu.tw/~yvchen/f107-ada/doc/181004_DynamicProgramming1.pdf - Rod cutting, stamp problem, knapsack problem: https://www.csie.ntu.edu.tw/~yvchen/f107-ada/doc/181011_DynamicProgramming2.pdf - Longest common subsequence: https://www.csie.ntu.edu.tw/~yvchen/f107-ada/doc/181018_DynamicProgramming3.pdf - Supplementary materials - Digression: https://neilchughes.com/2014/08/03/up-in-the-air-speech-whats-in-your-backpack/ - Linear programming https://algs4.cs.princeton.edu/lectures/keynote/99LinearProgramming.pdf - Selected problems - **509. Fibonacci Number** https://leetcode.com/problems/fibonacci-number/ - **50. Pow(x, n)** https://leetcode.com/problems/powx-n/ - **698. Partition to K Equal Sum Subsets** https://leetcode.com/problems/partition-to-k-equal-sum-subsets/ - https://leetcode.com/discuss/study-guide/1152328/01-Knapsack-Problem-and-Dynamic-Programming - **53. Maximum Subarray** https://leetcode.com/problems/maximum-subarray/ - https://en.wikipedia.org/wiki/Maximum_subarray_problem - Kadanes Algorithm - https://web.ntnu.edu.tw/~algo/MaximumSubarrayProblem.html#4 - **918. Maximum Sum Circular Subarray** https://leetcode.com/problems/maximum-sum-circular-subarray/ - **1143. Longest Common Subsequence** https://leetcode.com/problems/longest-common-subsequence/ - **72. Edit Distance** https://leetcode.com/problems/edit-distance/ - **1547. Minimum Cost to Cut a Stick** https://leetcode.com/problems/minimum-cost-to-cut-a-stick/ - **630. Course Schedule III** https://leetcode.com/problems/course-schedule-iii/ - **55. Jump Game** https://leetcode.com/problems/jump-game/ - **45. Jump Game II** https://leetcode.com/problems/jump-game-ii/ - **1306. Jump Game III** https://leetcode.com/problems/jump-game-iii <center> ![](https://i.imgur.com/VSpeRni.png =300x) </center> ---- ### ++**Greedy Algorithms**++ - Lecture slides - https://www.csie.ntu.edu.tw/~yvchen/f107-ada/doc/181018_Greedy1.pdf - https://www.csie.ntu.edu.tw/~yvchen/f107-ada/doc/181025_Greedy2.pdf - Supplementary materials - https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsI.pdf - https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsII.pdf - Selected problems: https://leetcode.com/tag/greedy/ - **435. Non-overlapping Intervals** https://leetcode.com/problems/non-overlapping-intervals/ - **322. Coin Changing** https://leetcode.com/problems/coin-change/ - **621. Task Scheduler** https://leetcode.com/problems/task-scheduler/ <center> ![](https://i.imgur.com/eXNbcFN.jpg =300x) </center> ---- ### ++**Combinatorial Search with Backtracking**++ - Lecture slides - https://algs4.cs.princeton.edu/lectures/keynote/67CombinatorialSearch.pdf - (FYR) https://courses.engr.illinois.edu/cs498374/fa2014/notes/07-backtracking.pdf > (Backtracking) is useful for constraint satisfaction problems that involve assigning values to variables according to a set of constraints... Backtracking reduces the number of possible value assignments that we consider, because it never considers invalid assignments... - The second sentance is so called pruning. - Selected problems: https://leetcode.com/tag/backtracking/ - **1461. Check If a String Contains All Binary Codes of Size K** https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/ - **46. Permutations** https://leetcode.com/problems/permutations/ - **47. Permutations II** https://leetcode.com/problems/permutations-ii/ - **17. Letter Combinations of a Phone Number** https://leetcode.com/problems/letter-combinations-of-a-phone-number/ - **51. N-Queens** https://leetcode.com/problems/n-queens/<img src = "https://hackmd.io/_uploads/BJ2zd9Pk2.png" height = 200px style="float:right"/> - **52. N-Queens II** https://leetcode.com/problems/n-queens-ii/ - **36. Valid Sudoku** https://leetcode.com/problems/valid-sudoku/ - **37. Sudoku Solver** https://leetcode.com/problems/sudoku-solver/ - **78. Subsets** https://leetcode.com/problems/subsets/ - **39. Combination Sum** https://leetcode.com/problems/combination-sum/ - **40. Combination Sum II** https://leetcode.com/problems/combination-sum-ii/ - **89. Gray Code** https://leetcode.com/problems/gray-code/ - **401. Binary Watch** https://leetcode.com/problems/binary-watch/ - **22. Generate Parentheses** https://leetcode.com/problems/generate-parentheses - **93. Restore IP Addresses** https://leetcode.com/problems/restore-ip-addresses/ - Supplementary materials - What is [Gray code](https://en.wikipedia.org/wiki/Gray_code) and why using it? - Error correction code - Assume that there are 64 bottles. Only one of them is poisonous. Ask how many rats, at least, we need to detect which bottle is poisonous. For simplicity, one rat could drink multiple bottles which may or may not include the poisonous one. - See also Hamming code in [Error Control](https://www.cs.princeton.edu/courses/archive/spring19/cos463/lectures/L08-error-control.pdf) from Princeton University. - Related problems: - **461. Hamming Distance** https://leetcode.com/problems/hamming-distance/ ---- ### ++**Randomized Algorithms**++ - [Randomness](https://en.wikipedia.org/wiki/Randomness) - [Pseudorandom generator](https://en.wikipedia.org/wiki/Pseudorandom_generator) (PRNG) - [Linear congruential generator](https://en.wikipedia.org/wiki/Linear_congruential_generator) (LCG) - [Mersenne Twister](https://en.wikipedia.org/wiki/Mersenne_Twister) (MT19937) - [True random number generator](https://en.wikipedia.org/wiki/Hardware_random_number_generator) (TRNG) - Lecture slides [pdf](https://wuecampus2.uni-wuerzburg.de/moodle/pluginfile.php/2023030/mod_resource/content/2/advalg-ws19-vl04-randomized-algorithms-printversion.pdf) - [Las Vegas algorithm](https://en.wikipedia.org/wiki/Las_Vegas_algorithm) > The algorithm fails with some probability, but we can tell when it fails. In particular, we can run it again until it succeeds, which means that we can eventually succeed with probability 1 (but with a potentially unbounded running time). - [Monte Carlo algorithm](https://en.wikipedia.org/wiki/Monte_Carlo_algorithm) > The algorithm fails with some probability, but we can't tell when it fails. If the algorithm produces a yes/no answer and the failure probability is significantly less than 1/2, we can reduce the probability of failure by running it many times and taking a majority of the answers. - First randomized algorithm: [closest pair of points problem](https://en.wikipedia.org/wiki/Closest_pair_of_points_problem) solved by [Michael O. Rabin](https://amturing.acm.org/award_winners/rabin_9681074.cfm) in 1976.<center><img src = "https://hackmd.io/_uploads/SJ1G2QIdt.png" height = 150px style="float:right"/></center> - Case study: [AlphaGo](https://deepmind.com/research/case-studies/alphago-the-story-so-far) - Lisy & Bosansk (2021): [Lecture 8: MCTS and AlphaGo](https://cw.fel.cvut.cz/b202/_media/courses/b4b36zui/zui_l8_handout.pdf) - Jonathan Hui (2018): [Monte Carlo Tree Search (MCTS) in AlphaGo Zero](https://jonathan-hui.medium.com/monte-carlo-tree-search-mcts-in-alphago-zero-8a403588276a) - Supplementary materials - Zero probability means impossibility? - https://math.stackexchange.com/questions/41107/zero-probability-and-impossibility - Cantor set: https://en.wikipedia.org/wiki/Cantor_set - https://en.wikipedia.org/wiki/Almost_surely - https://en.wikipedia.org/wiki/Kolmogorov%27s_zero%E2%80%93one_law > For an impossible event $A$, $P(A) = 0$. But the converse is not true. $P(A) = 0$ does not imply the impossibility of $A$. In this case, event $A$ is practically impossible. - https://en.wikipedia.org/wiki/0.999... - James Aspnes, [Notes on Randomized Algorithms](http://www.cs.yale.edu/homes/aspnes/classes/469/notes.pdf), Yale University - Selected problems https://leetcode.com/tag/randomized/ - **398. Random Pick Index** https://leetcode.com/problems/random-pick-index/ - **528. Random Pick with Weight** https://leetcode.com/problems/random-pick-with-weight/ - **710. Random Pick with Blacklist** https://leetcode.com/problems/random-pick-with-blacklist/ - **478. Generate Random Point in a Circle** https://leetcode.com/problems/generate-random-point-in-a-circle/ - **384. Shuffle an Array** https://leetcode.com/problems/shuffle-an-array/ <center> ![](https://hackmd.io/_uploads/H1lYkVIuK.png =250x) [Infinite monkey theorem](https://en.wikipedia.org/wiki/Infinite_monkey_theorem) </center> ---- ### ++**Approximation Algorithms**++ - Lecture slides: https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/11ApproximationAlgorithms.pdf - Load balancing - Center selection ### ++**Computing Theory**++ - Lecture slides<img src = "https://hackmd.io/_uploads/H1NhJHrNh.png" height = 150px style="float:right"/> - Knuth-Morris-Prat (KMP) algorithm using deterministic finite automata: https://algs4.cs.princeton.edu/lectures/keynote/53SubstringSearch.pdf - Finite state machines are everywhere in daily life: - Alex Dodge, State Machines for Everyone: [Traffic lights](https://medium.com/well-red/state-machines-for-everyone-part-1-introduction-b7ac9aaf482e) - David Khourshid, [Infinitely Better UIs with Finite Automata](https://slides.com/davidkhourshid/finite-state-machines) - Game saving in the early days, for example, [Rockman X Series](https://rmmh.blogspot.com/2019/08/password-x.html). <img src = "https://hackmd.io/_uploads/ryyXyrSV3.png" height = 100px style="float:right"/> - Turing machine https://introcs.cs.princeton.edu/java/lectures/keynote/CS.15.Turing.pdf - Google doodle https://www.google.com/doodles/alan-turings-100th-birthday - https://www.youtube.com/watch?v=7sdLeypeZE0&ab_channel=SamyZafrany - Intractability https://introcs.cs.princeton.edu/java/lectures/keynote/CS.16.Intractability.pdf - Reductions https://algs4.cs.princeton.edu/lectures/keynote/65Reductions.pdf - Supplementary materials - Computability<img src = "https://hackmd.io/_uploads/SyUwj-kfh.png" height = 100px style="float:right"/> - Halting problem https://en.wikipedia.org/wiki/Halting_problem - Church-Truing Thesis: - Turing (1936): *On computable numbers, with an application to the Entscheidungsproblem* [link](https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s2-42.1.230) - Church (1936): *An unsolvable problem of elementary number theory* - I wish I coudl have one [Wooden Turing machine](https://hackaday.com/2018/03/08/mechanical-wooden-turing-machine/) as one of my personal collections. - Millennium Prize Problems: [N =? NP](https://en.wikipedia.org/wiki/P_versus_NP_problem) - Turing Test - Alex Gendler, [The Turing test: Can a computer pass for a human?](https://www.youtube.com/watch?v=3wLqsRLvV-c) - Scientific film: [Ex Machina](https://www.imdb.com/title/tt0470752/) > A young programmer is selected to participate in a ground-breaking experiment in synthetic intelligence by evaluating the human qualities of a highly advanced humanoid A.I. - William G. Wong, [1-Hz, 8-Bit RISC Micro Built Using Minecraft Redstone](https://www.electronicdesign.com/technologies/embedded/video/21212550/electronic-design-chungus-2-a-very-powerful-1hz-minecraft-cpu), 2021 <center> ![](https://i.imgur.com/vIjB6lg.png =400x) <img src = "https://i.imgur.com/OsvWnJK.png" height = 300px/> [Alan Turing](https://en.wikipedia.org/wiki/Alan_Turing) </center> ---- ## **Take-Home Message** - Domain of Science, [Map of Computer Science](https://www.youtube.com/watch?v=SzJ46YA_RaA), 2017 <center> ![](https://i.imgur.com/6Owu9BC.jpg =500x) </center> ---- ## **References** - <a href = "https://apcs.csie.ntnu.edu.tw/index.php">大學程式設計先修檢測</a> (APCS) - Previous exams: [link](https://apcs.csie.ntnu.edu.tw/index.php/questionstypes/previousexam/) - 吳邦一 (Bangye Wu), [FB社團：APCS實作題檢測](https://www.facebook.com/groups/359446638362710) - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, [Introduction to Algorithms](https://mitpress.mit.edu/books/introduction-algorithms-fourth-edition), 4/e, 2022 NEW ![](https://hackmd.io/_uploads/SJWXzj4uq.png =100x) - You can find the Python codes for this classical textbook via this [link](https://mitp-content-server.mit.edu/books/content/sectbyfn/books_pres_0/11599/clrsPython.zip). - Steven S. Skiena, [The Algorithm Design Manual](https://www.springer.com/gp/book/9783030542559), 3/e, 2020 You could find the ebook via the link above when your IP is within NTU campus network. ![](https://i.imgur.com/UXVXb98.png =100x) - Antti Laaksonen, [Competitive Programmer's Handbook](https://cses.fi/book/index.php), 2018 ![](https://hackmd.io/_uploads/SyDfwJUFF.png =100x) - Marcello La Rocca, [Advanced Algorithms and Data Structures](https://www.manning.com/books/advanced-algorithms-and-data-structures), 2021 ![](https://hackmd.io/_uploads/HJjSb_5No.png =100x) - Michael Sipser, [Introduction to the Theory of Computation](https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295/), 3/e, 2014 You can find the lecture slides [here](https://math.mit.edu/~sipser/18404/Lectures%20Fall%202020/index.html). ![](https://images-na.ssl-images-amazon.com/images/I/61KGTdfkPAL.jpg =100x) - John L. Hennessy and David A. Patterson, [Computer Architecture: A Quantitative Approach](https://www.amazon.com/Computer-Architecture-Quantitative-Approach-Kaufmann/dp/0128119055/), 6/e, 2017 ![](https://i.imgur.com/5dWXYA3.png =100x) - Randal E. Bryant and David R. O'Hallaron, [Computer Systems: A Programmer's Perspective](https://www.amazon.com/Computer-Systems-OHallaron-Randal-Bryant/dp/1292101768), 3/e, 2016 ![](https://i.imgur.com/uLP59zv.png =100x) - [15-213/14-513/15-513: Introduction to Computer Systems (ICS)](https://www.cs.cmu.edu/~213/), School of Computer Science, Carnegie Mellon University - [CSCI 0300: Fundamentals of Computer Systems](http://cs.brown.edu/courses/csci0300/2022/), Computer Science at Brown University - Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, [Operating Systems: Three Easy Pieces](https://pages.cs.wisc.edu/~remzi/OSTEP/), University of Wisconsin-Madison, 2018 ![](https://hackmd.io/_uploads/B1-0wyIYF.png =100x) - Y.-D. Lyuu (呂育道), https://www.csie.ntu.edu.tw/~lyuu/complexity.html - Y.-N. Chen (陳縕儂), https://www.csie.ntu.edu.tw/~yvchen/f107-ada/ - [演算法筆記](http://web.ntnu.edu.tw/~algo/) - Erik Demaine and Srini Devadas, [6.006: Introduction to Algorithms](https://courses.csail.mit.edu/6.006/fall11/notes.shtml), Massachusetts Institute of Technology, 2011 - Geoffrey Challen, [Hack The Kernel](https://ops-class.org/), 2017 - Mary Wootters, [CS 161: Design and Analysis of Algorithms](http://web.stanford.edu/class/archive/cs/cs161/cs161.1182/index.html), Stanford University, 2017fa - Deeparnab Chakrabarty, [CS 31: Algorithms](https://www.cs.dartmouth.edu/~deepc/Courses/S20/CS31.html), Dartmouth College, 2020 - Jeremiah Blocki, [CS580 Algorithm Design, Analysis, And Implementation](https://www.cs.purdue.edu/homes/jblocki/courses/580_Spring19/), 2019sp - James Aspnes, [Notes on Data Structures and Programming Techniques](https://www.cs.yale.edu/homes/aspnes/classes/223/notes.html), Yale University, 2022 NEW - Jelani Nelson and James W. Demmel, [Efficient Algorithms and Intractable Problems](https://cs170.org/), UC Berkeley, 2022 - Keith Schwarz, [CS103: Mathematical Foundations of Computing](http://web.stanford.edu/class/archive/cs/cs103/cs103.1164/), Stanford University, 2016 <center> ![](https://hackmd.io/_uploads/SJtUJrmdK.png =400x) </center> - [The Algorithms](https://the-algorithms.com/) ![](https://hackmd.io/_uploads/H1_cy1UGo.png =100x) - https://introtcs.org/public/ - Jserv's enlightenment - [Linux 核心設計課程說明](https://docs.google.com/presentation/d/1GqbP_lS66CbOUKA6v-RND1BOicbklUFzbyXr4dihz4w/edit?usp=sharing), Department of Computer Science and Information Engineering, National Cheng Kung University, 2020sp - [Re: [問卦] 寫程式語言的語言是怎麼來的？](https://disp.cc/b/163-aR41), 2018.9.28 - [Re: [問卦] 作業系統學 Linux 就好?](https://disp.cc/b/163-bbnO), 2019.2.19 - [Re: [問卦] C 語言最難的部分是哪一個?](https://disp.cc/b/163-b6ux), 2019.1.17 - [Re: [問卦] 不用函數庫和亂數寫程式求pi值的方法?](https://disp.cc/b/163-bjzJ), 2019.4.19 - [Re: [問卦] C 語言編譯器用哪個才夠專業?](https://disp.cc/b/163-bjXe), 2019.4.22 ### Computer Games - [Human Resource Machine](https://store.steampowered.com/app/375820/Human_Resource_Machine/) ![](https://i.imgur.com/gqgb1IJ.png =300x) - [7 Billion Humans](https://store.steampowered.com/app/792100/7_Billion_Humans/) ![](https://i.imgur.com/6Tf8t0k.png =300x) - [Turing Complete](https://store.steampowered.com/app/1444480/Turing_Complete/) ![](https://hackmd.io/_uploads/S1x_po6LF.png =300x) - [while True: learn()](https://store.steampowered.com/app/619150/while_True_learn/) ![](https://hackmd.io/_uploads/SJfbTgjhc.png =300x) - [A=B](https://store.steampowered.com/app/1720850/AB/) ![](https://hackmd.io/_uploads/HyKahgj39.png =300x) - [Virtual Circuit Board](https://store.steampowered.com/app/1885690/Virtual_Circuit_Board/) ![](https://hackmd.io/_uploads/ryMTalj3q.png =300x) ### Online Judge Systems - LeetCode - [https://leetcode.com/explore/learn/](https://leetcode.com/explore/learn/) - [https://leetcode.com/explore/interview/card/top-interview-questions-hard/](https://leetcode.com/explore/interview/card/top-interview-questions-hard/) - Code Wars: https://www.codewars.com/ - 高中生程式解題系統：https://zerojudge.tw/ - https://onlinejudge.org/ - Codeforces: https://codeforces.com/

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.