This is a class webpage for the CMSC398L, and we will put all the resources of the class on this webpage. We will constantly update this webpage throughout the semester.

Friday 11:00 a.m - 11:50 a.m @ CSI 2120

Cheng-Yuan Lee, Spencer Lutz, Mazin Karjikar

Laxman Dhulipala

Competitive Proramming is an activity where programmers compete with each other in solving algorithmic problems with efficient code in a given number of time. CMSC398L: Introduction to Competitive Programming is a class intended to promote competitive programming on campus. The class covers most of the basic techniques and algorithms that are used in competitive programming.

- Brief Introduction about CP & Time Complexity
- C++ Standard Library & Basic Data Structures (Queue, Stack, LinkedList, Set, Map, Priority Queue)
- Enumeration & Searching (Binary Search, Ternary Search, Pruning)
- Greedy Algorithms
- Dynamic Programming
- Divide and Conquer
- Basic Number Theory (Factorization, Divisibility, Modular Congruence)
- Basic Graph Algorithms (DFS / BFS, Disjoint Set, Topological Sort)
- Shortest Paths (Dijkstra, Bellman-Ford, SPFA, Floyd-Warshall)
- Minimum Spanning Tree (Kruskal, Prim)
- Data Structures (BIT, Sparse Table, Segment Tree)
- Basic Computational Geometry (Convex Hull, Rotating Caliper)
Tree (Diameter, Centroid, LCA)

String Algorithms (KMP, Tries/Hashing, Suffix Array, Aho-Corasick Algorithm)

- Connectivity (DFS Trees, SCC, BCC)
- Square Root Decomposition
- Randomized Algorithms
- Offline Algorithms (Mo’s Algorithm, Parallel Binary Search, CDQ Divide and Conquer)
- Combinatorial Game Theory (Nim Game, Sprague Grundy Theorem, Hackenbush)
- Treap
- HLD, Centroid Decomposition
- Convolutions (FFT/NTT)
- Flow & Matching (Dinic, Kuhn’s algorithm, Hopcroft-Karp)

Week | Topic | Assignment | Class Recordings | Slides |
---|---|---|---|---|

1 (^{1}⁄_{26}) |
Brief Introduction about CP & Time Complexity | Homework 1 | None | In Class |

2 (^{2}⁄_{2}) |
C++ Standard Library & Basic Data Structures | Homework 2 | Pre-Class Recording | Pre Class / In Class |

3 (^{2}⁄_{9}) |
Enumeration & Basic Searching | TBD | Pre-Class Recording | Pre Class / In Class |

4 (^{2}⁄_{16}) |
Binary Search | TBD | Pre-Class Recording | Pre Class / In Class |

5 (^{2}⁄_{23}) |
Basic Number Theory | TBD | Pre-Class Recording | Pre Class / In Class |

6 (^{3}⁄_{1}) |
Greedy | TBD | Pre-Class Recording | Pre Class / In Class |

7 (^{3}⁄_{8}) |
Dynamic Programming | TBD | Pre-Class Recording | Pre Class / In Class |

8 (^{3}⁄_{15}) |
Basic Graphs | TBD | Pre-Class Recording | Pre Class / In Class |

9 (^{3}⁄_{22}) |
SPRING BREAK (NO CLASS) |
NONE |
NONE |
NONE |

10 (^{3}⁄_{29}) |
Shortest Paths & Minimum Spanning Tree | TBD | Pre-Class Recording | Pre Class / In Class |

11 (^{4}⁄_{5}) |
Data Structures (Probably Segment Tree) | TBD | Pre-Class Recording | Pre Class / In Class |

12 (^{4}⁄_{12}) |
Tree Algorithms | TBD | Pre-Class Recording | Pre Class / In Class |

13 (^{4}⁄_{19}) |
Network Flows | TBD | Pre-Class Recording | Pre Class / In Class |

14 (^{4}⁄_{26}) |
Square Root Decomposition | TBD | Pre-Class Recording | Pre Class / In Class |

15 (^{5}⁄_{3}) |
(Any advanced topics) | TBD | Pre-Class Recording | Pre Class / In Class |