Algorithms Lab

"Let all things be done decently and in order."
-- 1 Corinthians 14:40

"All go to the same place;
all come from dust, and to dust all return."
-- Ecclesiastes 3:20

"For whoever has will be given more,
and they will have an abundance.
Whoever does not have,
even what they have will be taken from them."
-- Matthew 25:29

"Premature optimization is the root of all evil."
-- Donald Ervin Knuth (1938-)

"If you want to master something, teach it.
The more you teach, the better you learn.
Teaching is a powerful tool to learning."
-- Richard Feynman (1918-1988)

Goal

This short course is designed for students who plan to learn about common data structures with efficient algorithms, solve LeetCode problems, and understand state-of-the-art information techniques. The achievements of Algorithms Lab are listed below:

• 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: [e-mail]

Textbook

• Robert Sedgewick and Kevin Wayne, Algorithms, 4/e, 2011
  
  • You could also follow the course COS 226 Data Structures and Algorithms for further studies.
  • You may find the Java codes of the book here.
• M. H. Alsuwaiyel, Algorithms: Design Techniques and Analysis, 2016
  

Programming Languages

• The demo code primarily uses Java in class.
• You could also use C, C++, C#, Python 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. You are welcomed to join for this work.
  • I want to emphasize that with AI tools like ChatGPT and Claude available, differences in programming languages are no longer a valid reason to stop you.
• You can find more information on setting up your development environment here.

Syllabus

Array

• Concept check
  • The main memory 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.
  • Why is the first element of arrays starting from the array index 0?
  ​​​​    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.
    • See also Memory Management in Python.
    • See also Stack and Heap Memory in C#.
    • See also Memory Management in JavaScript.
    • See also Memory allocations in Go.
      • The Go Memory Model
    • See also Memory management in The Rust Programming Language.
  • How about the following code snippet?
  ​​​​    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, Princeton Unversity, 2020fa
  • Ulrich Drepper, What Every Programmer Should Know About Memory, 2007
  • Core Dumped, WHY IS THE HEAP SO SLOW?, 2024.2.24
  • Tech With Nikola, But, what is Virtual Memory?, 2023.10.21

---

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?
  ​​​​    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, 2005
    • Udi Boker and Nachum Dershowitz, What is the Church-Turing Thesis?
• Problem set https://leetcode.com/tag/recursion/
  • 509. Fibonacci Number https://leetcode.com/problems/fibonacci-number/
  • 1137. N-th Tribonacci Number https://leetcode.com/problems/n-th-tribonacci-number/

---

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/
    • 35. Search Insert Position https://leetcode.com/problems/search-insert-position/
    • 704. Binary Search https://leetcode.com/problems/binary-search/
    • 69. Sqrt(x) https://leetcode.com/problems/sqrtx/
    • 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/

---

Analysis of Algorithms

• Lecture slides
  • Analysis of algorithms: a quick review link
  • About log-time algorithms link
• Selected problems
  • 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, 2011
  • J. Hartmanis and R. E. Stearns, On the Computational Complexity of Algorithms, 1965
  • DeepMind: AlphaGo 2017 youtube
  • Zheng-Liang Lu, High School Math in Computer Science, 2022

---

Linked List

Source https://www.educative.io/

• 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 (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, 分析「快慢指標」, 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 快慢指標篇
    • 雙指標技巧總彙
  • 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://www.data-structures-in-practice.com/intrusive-linked-lists/
  • If you are interested in design patterns, you may refer to the booklist here.

---

Tree

Source https://www.educative.io/

• Lecture slides
  • Binary search tree https://algs4.cs.princeton.edu/lectures/keynote/32BinarySearchTrees.pdf
  • Selected problems
    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-心得-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
    • 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 核心的紅黑樹
    • 紅黑樹 (附完整 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#紅黑樹的移除
  • 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.

---

Hashing

Source https://miro.medium.com/max/3856/1*SCHCrY-GeCGjSbVk7P8kaQ.png

• 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's_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://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/
  • Python Hash Tables: Understanding Dictionaries link
  • Cuckoo Hashing wiki
  • Daniel Jslin, List, HList, and Hash Table (in C), 2016-11-20
  • Checksum https://en.wikipedia.org/wiki/Checksum
  • Jserv, 現代處理器設計: Cache 原理和實際影響
  • https://courses.grainger.illinois.edu/cs473/fa2024/notes/05-hashing.pdf

Source link

---

Graph

• 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.
      • 886. Possible Bipartition https://leetcode.com/problems/possible-bipartition/
        
  • 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
      • Take the stock market as an example for transition matrices or Markov chains: https://en.wikipedia.org/wiki/Examples_of_Markov_chains#Stock_market
      • Allen B. Downey, PageRank, 2021
      • Brain, PageRank：最大的SEO排名因素，５分鐘弄懂SEO的核心演算法知識, 2021-05-18
      • Chonyy, PageRank: Link Analysis Explanation and Python Implementation from Scratch, 2021-01-08
      • iLeafy11, Desktop Search and PageRank Parallelization, 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
      • 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, 2007
        • 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, 2016
      • William Fiset, Bellman Ford Algorithm | Shortest path & Negative cycles | Graph Theory, 2018
• Supplementary materials
  • Maximum flow https://algs4.cs.princeton.edu/lectures/keynote/64MaxFlow.pdf
  • More problems on graphs link
    • Packing: independent set, clique
    • Covering: vertex cover, edge covering, set covering
  • Microsoft, Influence Maximization, KDD-2012
  • Ju Fan, Influence Maximization on Big Social Graphs, Renmin University of China, 2017
  • Andrea Marino, Graph Clustering Algorithms, 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 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 演算法筆記.
  • Kun-Mao Chao, Special topics on graph algorithms, 2021
  • Journal of Graph Algorithms and Applications
  • You can find Python implementation for graphs below:
    • https://networkx.org/

Source https://xkcd.com/399/

---

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, Python, grep 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
    • 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
  • 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/

---

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/

---

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/
  • 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 and why using it?
    • Application: 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 from Princeton University.
    • Related problems:
      • 461. Hamming Distance https://leetcode.com/problems/hamming-distance/

---

Randomized Algorithms

• Randomness
  • Pseudorandom generator (PRNG)
    • Linear congruential generator (LCG)
    • Mersenne Twister (MT19937)
    • Statistics Crystallized, Random Number Generators (Mersenne Twister vs. Middle Square), 2023.12.14
  • True random number generator (TRNG)
• Lecture slides pdf pdf'
  • 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

    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 solved by Michael O. Rabin in 1976.
• Case studies
  • AlphaGo
    • Lisy & Bosansk (2021): Lecture 8: MCTS and AlphaGo
    • Jonathan Hui (2018): Monte Carlo Tree Search (MCTS) in AlphaGo Zero
  • Treap (binray search tree + heap): a randomized data structure
    • Seidel & Aragon (1989)
    • https://jeffe.cs.illinois.edu/teaching/algorithms/notes/03-treaps.pdf
  • Skip list
    • https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/skiplists.pdf
    • https://courses.csail.mit.edu/6.046/spring04/handouts/skiplists.pdf
• 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's_zero–one_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, Yale University
  • https://cse.iitkgp.ac.in/~palash/Courses/2019RandomizedAlgoDesign/Files/2019RandomizedAlgorithmDesignLectureNotes.pdf
• 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/

Infinite monkey theorem

---

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
    • David Khourshid, Infinitely Better UIs with Finite Automata
    • Game saving in the early days, for example, Rockman X Series.
      • 三、四十年前的遊戲到底是怎麼存檔的呢？
        
  • 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值的方法?, 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
    • Halting problem https://en.wikipedia.org/wiki/Halting_problem
    • Church-Turing Thesis:
      • Turing (1936): On computable numbers, with an application to the Entscheidungsproblem link
      • Church (1936): An unsolvable problem of elementary number theory
    • I wish I coudl have one Wooden Turing machine as one of my personal collections.
  • Millennium Prize Problems: N =? NP
  • Turing Test
    • Alex Gendler, The Turing test: Can a computer pass for a human?
    • https://copyleaks.com/ai-content-detector
    • Scientific film: Ex Machina

      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, 2021

Alan Turing

Quantum Computing & Algorithms

• Lecture slides
  • Heather M. Gray, Introduction to Quantum Computing: Fundamentals, 2021
• Supplementary materials
  • Domain of Science, The Map of Quantum Computing | Quantum Computers Explained, 2021
  • Domain of Science, Who Has The Best Quantum Computer?, 2021
  • You may need basic knowledge of linear algebra.
    • Dan Margalit and Joseph Rabinoff, Interactive Linear Algebra, 2019
  • 台北市政府高中職量子計算教課書：https://sites.google.com/ycsh.tp.edu.tw/2023qbit/首頁
  • https://qutip.org/
  • https://quantum-computing.ibm.com/
    • 鄭經斅，IBM quantum composer 的簡單使用說明，2022

---

MISC

Take a look at Algorithms Lab 2.

---

Take-Home Message

• Domain of Science, Map of Computer Science, 2017

• More courses for programming languages
  • Java Programming
  • C# Programming
  • C++ Programming
  • Python 101

• More courses for applications
  • Python Programming in Finance
    • Financial Computing Labs: Futures & Options new
  • Introduction to Data Science
  • Introduction to MATLAB Programming with Applications

To be good, you have to start; to start, you don't have to be good.

Math is essential to Computer Science, even to Finance.

TODO

• Multiset
• Byzantine generals problem
  • Chor and Coan (1985): A Simple and Efficient Randomized Byzantine Agreement Algorithm
• 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

---

References

Books

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4/e, 2022 NEW
  
  • You can find the Python codes for this classical textbook via this link.
• Jon Kleinberg and Éva Tardos, Algorithm Design, 2005
  
• Steven S. Skiena, The Algorithm Design Manual, 3/e, 2020 You could find the ebook via the link above when your IP is within NTU campus network.
  
• Antti Laaksonen, Competitive Programmer's Handbook, 2018
  
• Marcello La Rocca, Advanced Algorithms and Data Structures, 2021
  
• Md. Saidur Rahman, Basic Graph Theory, 2017
  
• Dieter Jungnickel, Graphs, Networks and Algorithms, 2013
  
• Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, 1995
  
• Michael Mitzenmacher and Eli Upfal, Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, 2/e, 2017
  
• Vijay V. Vazirani, Approximation Algorithms, 2003
  
• Michael Sipser, Introduction to the Theory of Computation, 3/e, 2014 You can find the lecture slides here.
  
• John L. Hennessy and David A. Patterson, Computer Architecture: A Quantitative Approach, 6/e, 2017
  
• Randal E. Bryant and David R. O'Hallaron, Computer Systems: A Programmer's Perspective, 3/e, 2016
  
  • 15-213/14-513/15-513: Introduction to Computer Systems (ICS), School of Computer Science, Carnegie Mellon University
  • CSCI 0300: Fundamentals of Computer Systems, Computer Science at Brown University
• Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, University of Wisconsin-Madison, 2018
  
• John MacCormick, Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers, 2012
  

Courses

• Y.-D. Lyuu (呂育道), Computing Theory, 2022
• Y.-N. Chen (陳縕儂), Algorithm Design and Analysis, 2018
• 演算法筆記, NTNU
• Erik Demaine and Srini Devadas, Introduction to Algorithms, Massachusetts Institute of Technology, 2011
• Erik Demaine, Advanced Data Structures, Massachusetts Institute of Technology, 2012
• Erik Demaine, Srini Devadas and Nancy Lynch, Design And Analysis Of Algorithms, Massachusetts Institute of Technology, 2013
• Mary Wootters, CS 161: Design and Analysis of Algorithms, Stanford University, 2017fa
• TBD, CS166: Data Structures, Stanford University, 2023sp
• Deeparnab Chakrabarty, CS 31: Algorithms, Dartmouth College, 2020
• Jeremiah Blocki, CS580 Algorithm Design, Analysis, And Implementation, Purdue University, 2019sp
• James Aspnes, Notes on Data Structures and Programming Techniques, Yale University, 2022
• Christian Borgs and James W. Demmel, Efficient Algorithms and Intractable Problems, UC Berkeley, 2024
• Boaz Barak, Introduction to Theoretical Computer Science
• Keith Schwarz, CS103: Mathematical Foundations of Computing, Stanford University, 2016

Quantum Computing & Algorithms

• Heike Riel, Quantum computing: prospects and challenges, 2022-06-03
• Abdulah Amer, Introduction to Quantum Computing using Python, 2021
• https://www.dwavesys.com/
• Victor S. Batista, Introduction to Machine Learning and Quantum Computing, Yale University
• John Watrous, CPSC 519/619: Quantum Computation, University of Calgary, 2006
• The Building Blocks of a Quantum Computer: Part 1, Technische Universiteit Delft
• Learn Quantum Computation using Qiskit, IBM
• John Preskill, Ph219/CS219 Quantum Computation, Caltech, Fall 2021

Linux

• Geoffrey Challen, Hack The Kernel, 2017

Computer Games

• Human Resource Machine
  
• 7 Billion Humans
  
• Turing Complete
  
• while True: learn()
  
• A=B
  
• Virtual Circuit Board
  

Online Judge Systems

• LeetCode
  • https://leetcode.com/explore/learn/
  • 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/

Misc

• 大學程式設計先修檢測 (APCS)
  • Previous exams: link
  • 吳邦一 (Bangye Wu), FB社團：APCS實作題檢測
• 黃敬群老師的開示
  • Linux 核心設計課程說明, Department of Computer Science and Information Engineering, National Cheng Kung University, 2020sp
  • Re: [問卦] 寫程式語言的語言是怎麼來的？, 2018.9.28
  • Re: [問卦] 作業系統學 Linux 就好?, 2019.2.19
  • Re: [問卦] C 語言最難的部分是哪一個?, 2019.1.17
  • Re: [問卦] 不用函數庫和亂數 寫程式求pi值的方法?, 2019.4.19
  • Re: [問卦] C 語言編譯器用哪個才夠專業?, 2019.4.22
• 让水烧开, 編程語言到底是如何演化至今的，你知道嗎？【編程語言發展史】, 2024.1.2
• 3Blue1Brown
  

---

Gradebook