This repository contains a collection of slides for various topics related to competitive programming. The slides were created by Sam in several competitive programming courses, and are intended to be used as a reference or teaching material for competitive programming enthusiasts.
The slides are created using LaTeX and Beamer, and cover a range of topics including algorithms, data structures, and problem-solving techniques.
These slides are made back in Fall of 2021 for the Informatics Club I founded. The length of a single course is 50 minutes. Some of them are on slides.com.
| Date | Class | Topics Included |
|---|---|---|
| September 6, 2021 | Intro to Competitive Programming (競賽導論) | Introductions |
| September 9, 2021 | Time Complexity Analysis (時間複雜度分析) | Big O Notation, Amortized Time |
| September 14, 2021 | C++ STL and Basic Data Structures (基礎資結) | C++ vector, deque, queue, stack, map |
| September 28, 2021 | Enumeration and Searching (枚舉與搜尋) | Binary Search, Ternary Search, Backtracking, Pruning, Bitwise Operators |
| October 19, 2021 | Greedy Algorithms (貪心演算法) | Interval Scheduling, Fractional Knapsack Problem, Maximum Continuous Subarray, and more |
| October 25, 2021 | Basic Dynamic Programming (基礎動態規劃) | Classic Problems, Knapsack Problem, 2D DP, Range DP, Bitmask DP |
| October 28, 2021 | Basic Mathematics (基礎數學) | Number Theory (Euclidean Algorithm, Modular Congruence), Matrices (Linear Recurrence, Gauss-Jordan Elimination) |
| November 2, 2021 | Basic Computational Geometry (基礎計算幾何) | 2D Vectors, Segment intersection, Convex Hull |
| November 10, 2021 | Basic Graph Theory (基礎圖論) | Graphs, DFS/BFS, Adjacency Matrix/List, Eulerian Path, Hamiltonian Path, Topological Sorting, Bipartite Coloring |
| November 10, 2021 | Disjoint Set Union (並查集) | DSU, Time Complexity, Applications |
| November 15, 2021 | Divide and Conquer (分治) | Master Theorem, Merge Sort, Counting Inversions, Closest Pair of Points |
| November 16, 2021 | Shortest Path （最短路徑） | BFS, Dijkstra, 0-1 BFS, Bellman-Ford, Floyd-Warshall, Graph Girth |
| November 30, 2021 | Minimum Spanning Tree (最小生成樹) | Cycle/Cut Property, Prim's Algorithm, Kruskal's Algorithm |
| December 1, 2021 | Range Queries Data Structures (區間問題合輯) | Prefix Sum, Sparse Table, Binary Indexed Tree (Fenwick Tree), Segment Tree, Lazy Propagation, Offline Algorithm |
| December 14, 2021 | Tree Algorithms (樹論) | Diameter, Centroid, Lowest Common Ancestor, Binary Lifting, Euler Tour, Heavy-Light Decomposition, Tree DP, Rerooting DP, Centroid Decomposition |
| February 14, 2022 | Binary Search Review (二分搜複習) | Different Implementations, Binary Lifting, Binary Search on Answer, Fractional Programming |
| March 1, 2022 | DP Review (動態規劃複習) | Some DP Problems |
| March 15, 2022 | Basic Randomized Algorithm (隨機演算法) | How to generate random in C++, Hashing |
| March 30, 2022 | Graph Connectivity (圖的連通性) | DFS Tree, Articulation Point/Bridge, Bridge Tree, Biconnected Components, Strongly Connected Components, 2-SAT |
| April 11, 2022 | Offline Algorithms (離線演算法) | Mo's Algorithm, Rollback Mo, Parallel Binary Search, CDQ Divide and Conquer (3D partial order) |
| April 27, 2022 | DP Optimizations (DP 優化) | Matrix Exponentiation, Monotonic Stack/Queue Optimization, Convex Hull Trick, Li Chao Segment Tree |
| November 21, 2022 | Combinatorial Game Theory (組合賽局) | Game DP, Game Graphs, Nim Game, Sprague Grundy's Theorem |
This summer camp is organized by me and four of my friends. The four schools involved are
- National Hsin Hua Senior High School (HHSH 國立新化高級中學)
- National Chiayi Senior High School (CYSH 國立嘉義高級中學)
- Taipei Wego Private Senior High School (WGHS 臺北市私立薇閣高級中學)
- The Affiliated Senior High School of National Taiwan Normal University (HSNU 國立臺灣師範大學附屬高級中學)
This is the schedule of the camp
Here are the recordings of the summer camp.
I taught four courses in this summer camp.
| Date | Class | Topics Included |
|---|---|---|
| July 6, 2022 | Greedy Algorithm and Basic Proof (貪心/基礎證明方法) | Greedy Problems, Prove by Contradition, Mathematical Induction |
| July 7, 2022 | Mathematics (數學) | Number Theory, Prime Factorization, Modular Congruence, Chinese Remainder Theorem, Combinatorics, Matrices, Gauss-Jordan Elimination |
| July 11, 2022 | Dynamic Programming II (動態規劃 II) | O(n log n) LIS, Knapsack, Range DP, Bitmask DP, Monotonic Queue Optimization, Matrix Exponentiation |
| July 15, 2022 | Computational Geometry (計算幾何) | 2D Vector, IEEE-754, Float Precisions, Convex Hull, Rotating Caliper, Polar Sort, Scanning Line Algorithm |
I was invited by one of my best friends Zhu to lecture in the study group.
I taught a total of 4 courses in the study group before the group is dismissed, and collaborated on 3 other slides.
| Date | Class | Topics Included |
|---|---|---|
| August 25, 2022 | Basic Graph Algorithms (基礎圖論 Co-authored with zhu) | Adjacency Matrix/List, Graph Traversal, Eulerian/Hamiltonian Circuit, Topological Sort, Shortest Path, Tree Algorithms, Disjoint Set Union, Lowest Common Ancestors, Minimum Spanning Tree |
| September 2022 | Basic Algorithms III (基礎演算法（三）) | Greedy, Scanning Line, Prefix Sum & Difference Array, Monotonic Stack, Modular Congruence |
| September 2022 | Dynamic Programming I (動態規劃（一）Co-authored with zhu) | Classical DP Problems, Knapsack DP |
| October 2022 | Dynamic Programming II (動態規劃（二）Co-authored with zhu) | Bitmask DP, Range DP, Construct answer, Prefix Sum Optimization, Monotonic Queue Optimization |
| November 2022 | Mathematics I (數學（一）) | Binary Exponentiation, Prime Sieve, Euclidean Algorithm, Modular Congruence, Euler Phi Function, Chinese Remainder |
| November 2022 | Mathematics II (數學（二）) | Matrices, Linear Recurrence, Gaussian Elimination, Vector Space & XOR Basis, Combinatorics, Principle of Inclusion and Exclusion |
| February 2023 | Advanced Data Structures (進階資料結構) | Coordinate Compression, Offline Method, Binary Search on Segment Tree/Fenwick Tree, Dynamic Segment Tree/Fenwick Tree, Persistent Segment Tree/Fenwick Tree |
I founded the Competitive Programming Club at UMD, and held four meetings since April 2023.
| Date | Class | Topics Included |
|---|---|---|
| April 13, 2023 | UMD CP Club - First Club Meeting | Introductions |
| April 27, 2023 | UMD CP Club - Math + Greedy | Prime Factorization, Prime Sieve, Modular Congruence, Binary Exponentiation, Fermat's Little Theorem, Chinese Remainder Theorem, Linear Recurrence, Greedy |
| May 4, 2023 | UMD CP Club - Dynamic Programming | Classic DP Problems, Knapsack Problem, Range DP, Bitmask DP |
In Summer 2023, I started a summer plan for club members to learn CP. Starting from the basic techniques.
| Date | Class | Topics Included | Some Resources |
|---|---|---|---|
| July 1, 2023 | UMD Summer CP - Introduction & Basics | Introductions, C++ Syntax, C++ STL & Basic Data Structures | Video (Password: .dfte8V.) Problem List |
| July 8, 2023 | UMD Summer CP - Enumeration & Searching | Searching techniques, Two pointers, Binary Search, Ternary Search | Video (Password:frcUg9K=) Problem List |