Algorithms Lab

--- title: Algorithms Lab tags: computer science, algorithm, data structure, leetcode --- # **Algorithms Lab** <div> "Let all things be done decently and in order." -- First Corinthians 14:40 "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 understand 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 could also follow the course [COS 226 Data Structures and Algorithms](https://www.cs.princeton.edu/courses/archive/fall23/cos226/syllabus.php) for further studies. - You may find the Java codes of the book [here](https://github.com/kevin-wayne/algs4). - M. H. Alsuwaiyel, [Algorithms: Design Techniques and Analysis](https://www.worldscientific.com/worldscibooks/10.1142/9804#t=aboutBook), 2016 ![image](https://hackmd.io/_uploads/HJecvsxEa.png =100x) ### Programming Languages - The demo code primarily uses [Java](https://www.csie.ntu.edu.tw/~d00922011/java.html) in class. - 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 create a reference table to compare similarities and differences across multiple mainstream languages. You may take a look at it on this [page](https://docs.google.com/spreadsheets/d/e/2PACX-1vSK9NZyZJIH-pU2Ta6m1sbHNb1OYpyRk113JctcEonKYSIRvUOEM8VM7J-b0haYfRNGgE2VYaya-wA7/pubhtml?gid=0&single=true). You are welcomed to join for this work. - You can find more information on setting up your development environment [here](https://hackmd.io/@arthurzllu/ry-PIcBlO). ## **Syllabus** ### ++**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/ - Supplementary materials - https://leetcode.com/explore/learn/card/fun-with-arrays/ - https://leetcode.com/explore/learn/card/array-and-string/ - https://leetcode.com/explore/learn/card/queue-stack/ - 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 - Core Dumped, [WHY IS THE HEAP SO SLOW?](https://www.youtube.com/watch?v=ioJkA7Mw2-U), 2024.2.24 - Tech With Nikola, [But, what is Virtual Memory?](https://www.youtube.com/watch?v=A9WLYbE0p-I), 2023.10.21 <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; */ } ``` - Supplementary materials - https://leetcode.com/explore/learn/card/recursion-i/ - https://leetcode.com/explore/learn/card/recursion-ii/ - 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 - Supplementary materials - https://leetcode.com/explore/learn/card/binary-search/ - 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/ ---- ### ++**Analysis of Algorithms**++ - Lecture slides - Analysis of algorithms: a quick review [link](https://www.csie.ntu.edu.tw/~d00922011/java/big_O.pdf) - About log-time algorithms [link](https://www.csie.ntu.edu.tw/~d00922011/java/log-time_algorithm.pdf) - Selected problems - **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> ---- ### ++**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). - Problem set https://leetcode.com/tag/linked-list/ - **876. Middle of the Linked List** https://leetcode.com/problems/middle-of-the-linked-list/ - Jserv, [分析「快慢指標」](https://hackmd.io/@sysprog/ry8NwAMvT), 2024 - **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 - https://leetcode.com/explore/learn/card/linked-list/ - 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/ - **257. Binary Tree Paths** https://leetcode.com/problems/binary-tree-paths/ - **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/ - **589. N-ary Tree Preorder Traversal** https://leetcode.com/problems/n-ary-tree-preorder-traversal/ - **590. N-ary Tree Postorder Traversal** https://leetcode.com/problems/n-ary-tree-postorder-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/ - **100. Same Tree** https://leetcode.com/problems/same-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 - **108. Convert Sorted Array to Binary Search Tree** https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/ - **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 - https://leetcode.com/explore/learn/card/data-structure-tree/ - https://leetcode.com/explore/learn/card/n-ary-tree/ - https://leetcode.com/explore/learn/card/introduction-to-data-structure-binary-search-tree/ - You can find more tree problems [here](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/ - **137. Single Number II** https://leetcode.com/problems/single-number-ii/ - 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 - Jserv, [現代處理器設計: Cache 原理和實際影響](https://hackmd.io/@sysprog/HkW3Dr1Rb) - https://courses.grainger.illinois.edu/cs473/fa2024/notes/05-hashing.pdf <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 - **323. Number of Connected Components in an Undirected Graph** https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/ - **200. Number of Islands** https://leetcode.com/problems/number-of-islands/ - **547. Number of Provinces** https://leetcode.com/problems/number-of-provinces/ - **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/ - **1971. Find if Path Exists in Graph** https://leetcode.com/problems/find-if-path-exists-in-graph/ - ++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). - Kun-Mao Chao, [Special topics on graph algorithms](https://www.csie.ntu.edu.tw/~kmchao/tree21spr/), 2021 - [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 - **912. Sort an Array** https://leetcode.com/problems/sort-an-array/description/ - 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 - (TODO) Segment tree https://cp.wiwiho.me/segment-tree/ - (TODO) Suffix arrays with applications. - (TODO) Why $O(L + \ln N)$ time for search hit in TST? ---- ### ++**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/ - [0/1 Knapsack Problem and Dynamic Programming](https://leetcode.com/discuss/study-guide/1152328/01-Knapsack-Problem-and-Dynamic-Programming) - Linear programming https://algs4.cs.princeton.edu/lectures/keynote/99LinearProgramming.pdf - https://courses.grainger.illinois.edu/cs473/fa2024/notes/03-dynprog.pdf - Selected problems - **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 - **698. Partition to K Equal Sum Subsets** https://leetcode.com/problems/partition-to-k-equal-sum-subsets/ - **322. Coin Changing** https://leetcode.com/problems/coin-change/ <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/ - **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 - **2664. The Knight’s Tour** https://leetcode.com/problems/the-knights-tour/ - Supplementary materials - What is [Gray code](https://en.wikipedia.org/wiki/Gray_code) and why using it? - Application: [Rotary encoder](https://en.wikipedia.org/wiki/Rotary_encoder) - 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) - Statistics Crystallized, [Random Number Generators (Mersenne Twister vs. Middle Square)](https://www.youtube.com/watch?v=QTk2AxzZYfc), 2023.12.14 - [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/ - KFY shuffle algorithm: https://blog.codinghorror.com/the-danger-of-naivete/ <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 ---- ### ++**Parallel Computing & Algorithms**++ - https://hackmd.io/@arthurzllu/S1FeT_Xwo ---- ### ++**Computing Theory**++ - Lecture slides - 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) <img src = "https://hackmd.io/_uploads/H1NhJHrNh.png" height = 150px/> - 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). - [三、四十年前的遊戲到底是怎麼存檔的呢？](https://www.youtube.com/watch?v=0yBlauG_z8o) <img src = "https://hackmd.io/_uploads/ryyXyrSV3.png" height = 100px/> - 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 - jserv, [Re: [問卦] 不用函數庫和亂數寫程式求pi值的方法?](https://disp.cc/b/Gossiping/bjzJ), 2019 - 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-Turing 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) - https://copyleaks.com/ai-content-detector - 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> ### ++**Quantum Computing & Algorithms**++ - Lecture slides<img src = "https://hackmd.io/_uploads/ByTnMBrEh.png" height = 100px style="float:right"/> - Heather M. Gray, [Introduction to Quantum Computing: Fundamentals](https://indico.cern.ch/event/870515/attachments/2217802/3755127/HGrayQCLecture1.pdf), 2021 - Supplementary materials - You may need basic knowledge of linear algebra. - Dan Margalit and Joseph Rabinoff, [Interactive Linear Algebra](https://textbooks.math.gatech.edu/ila/), 2019 - [重要趨勢！量子跟你想的不一樣！量子電腦將掀起超級運算大革命！將如何引領科技發展？ft.台灣量子電腦協會理事長張慶瑞教授！](https://www.youtube.com/watch?v=Hb2q9EzzCPQ) 2023 - 台北市政府高中職量子計算教課書：https://sites.google.com/ycsh.tp.edu.tw/2023qbit/%E9%A6%96%E9%A0%81 - https://qutip.org/ - https://quantum-computing.ibm.com/ - 鄭經斅，[IBM quantum composer 的簡單使用說明](https://www.youtube.com/watch?v=3VBh86MKo7M&ab_channel=Ching-hsiaoCheng)，2022 - Heike Riel, [Quantum computing: prospects and challenges](https://www.spiedigitallibrary.org/conference-proceedings-of-spie/PC12133/PC1213301/Quantum-computing-prospects-and-challenges/10.1117/12.2636962.short), 2022-06-03 - Abdulah Amer, [Introduction to Quantum Computing using Python](https://towardsdatascience.com/what-is-quantum-entanglement-anyway-4ea97df4bb0e), 2021 - https://www.dwavesys.com/ - Victor S. Batista, [Introduction to Machine Learning and Quantum Computing](http://ursula.chem.yale.edu/~batista/classes/CHEM584/v584.pdf), Yale University - John Watrous, [CPSC 519/619: Quantum Computation](https://cs.uwaterloo.ca/~watrous/QC-notes/QC-notes.pdf), University of Calgary, 2006 - [The Building Blocks of a Quantum Computer: Part 1](https://ocw.tudelft.nl/courses/building-blocks-quantum-computer-part-1/), Technische Universiteit Delft - [Learn Quantum Computation using Qiskit](https://qiskit.org/textbook/preface.html), IBM - John Preskill, [Ph219/CS219 Quantum Computation](http://theory.caltech.edu/~preskill/ph219/ph219_2021-22.html), Caltech, Fall 2021 - Domain of Science, [The Map of Quantum Computing | Quantum Computers Explained](https://www.youtube.com/watch?app=desktop&v=-UlxHPIEVqA), 2021 - Domain of Science, [Who Has The Best Quantum Computer?](https://youtu.be/gcbMKt079l8), 2021 <center> ![](https://hackmd.io/_uploads/SyIUQzJmj.png =600x) ![](https://hackmd.io/_uploads/SJGRDMtd5.png =600x) </center> ---- ### ++**MISC**++ Take a look at [Algorithms Lab 2](https://hackmd.io/@arthurzllu/SJ97jg--C). ---- ## **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> - More courses for programming languages - [Java Programming](https://www.csie.ntu.edu.tw/~d00922011/java.html) - [C# Programming](https://www.csie.ntu.edu.tw/~d00922011/csharp.html) - [C++ Programming](https://www.csie.ntu.edu.tw/~d00922011/cpp.html) - [Python 101](https://hackmd.io/@arthurzllu/HJNXq84SO)  - More courses for applications - [Python Programming in Finance](https://www.csie.ntu.edu.tw/~d00922011/python.html) - [Financial Computing Labs: Futures & Options](https://hackmd.io/@arthurzllu/SJLG2r8U5) new - [Introduction to Data Science](https://hackmd.io/@arthurzllu/ByC0nhVkr) - [Introduction to MATLAB Programming with Applications](https://www.csie.ntu.edu.tw/~d00922011/matlab.html)  :::info To be good, you have to start; to start, you don't have to be good. ::: :::warning Math is essential to Computer Science, even to Finance. ::: <img src = "https://www.freeiconspng.com/uploads/brain-gears-icon-png-8.png" height = 200px style="float:right"/> ### TODO - [Skip list](https://brilliant.org/wiki/skip-lists) and [multiset](https://en.wikipedia.org/wiki/Multiset) - [Byzantine generals problem](https://en.wikipedia.org/wiki/Byzantine_fault) - Chor and Coan (1985): [A Simple and Efficient Randomized Byzantine Agreement Algorithm](https://groups.csail.mit.edu/tds/papers/Coan/IEEETransactions85.pdf) - More NP-complete problems in graph theory - https://en.wikipedia.org/wiki/Segment_tree - https://yuihuang.com/binary-indexed-tree/ - https://hackmd.io/@wiwiho/cp-note/ - https://www.geeksforgeeks.org/top-algorithms-and-data-structures-for-competitive-programming/ - **295. Find Median from Data Stream** https://leetcode.com/problems/find-median-from-data-stream/ - More interesting algorithms can be found here: [Algorithms Lab 2](https://hackmd.io/@arthurzllu/SJ97jg--C) ---- ## **References** - 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). - Jon Kleinberg and Éva Tardos, [Algorithm Design](https://www.cs.princeton.edu/~wayne/kleinberg-tardos/), 2005 ![](https://hackmd.io/_uploads/Byu1vyUKF.png =110x) - 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) - Md. Saidur Rahman, [Basic Graph Theory](https://link.springer.com/book/10.1007/978-3-319-49475-3), 2017 ![image](https://hackmd.io/_uploads/SyszNvdtT.png =100x) - Dieter Jungnickel, [Graphs, Networks and Algorithms](https://doc.lagout.org/science/0_Computer%20Science/2_Algorithms/Graphs%2C%20Networks%20and%20Algorithms%20%284th%20ed.%29%20%5BJungnickel%202012-11-09%5D.pdf), 2013 ![image](https://hackmd.io/_uploads/ByG8PzuKT.png =100x) - Rajeev Motwani and Prabhakar Raghavan, [Randomized Algorithms](https://a.co/d/0FE0fAn), 1995 ![image](https://hackmd.io/_uploads/S1FhFDLYT.png =100x) - Vijay V. Vazirani, [Approximation Algorithms](https://link.springer.com/book/10.1007/978-3-662-04565-7), 2003 ![image](https://hackmd.io/_uploads/HJQ1xf_FT.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) - John MacCormick, [Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers](https://press.princeton.edu/books/paperback/9780691209067/nine-algorithms-that-changed-the-future), 2012 ![](https://hackmd.io/_uploads/BkzpLI6IT.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/), NTNU - 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 - Erik Demaine, Srini Devadas and Nancy Lynch, [Design And Analysis Of Algorithms](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/), Massachusetts Institute of Technology, 2013 - 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 - Christian Borgs and James W. Demmel, [Efficient Algorithms and Intractable Problems](https://cs170.org/), UC Berkeley, 2024 - 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/ - <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) - 黃敬群老師的開示 - [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 - 让水烧开, [編程語言到底是如何演化至今的，你知道嗎？【編程語言發展史】](https://www.youtube.com/watch?v=A4gelx7IHlY), 2024.1.2 - [3Blue1Brown](https://www.youtube.com/c/3blue1brown) ![image](https://hackmd.io/_uploads/HJ04s_4QA.png =100x) ### 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/ ---- ## **Gradebook** <center> <iframe src="https://docs.google.com/spreadsheets/d/1CTrIPVzrdWJO5EmDqZ1RpKuNUrCjivl-URTp6JqKI5E/pubhtml?gid=1786421611&single=true&widget=true&headers=false" width = "700px" height = "500px"></iframe> </center>