CMSC398L: Introduction to Competitive Programing (Spring 2024)

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.

Time and Locations

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

Course Facilitators:

Cheng-Yuan Lee, Spencer Lutz, Mazin Karjikar

Faculty Advisor:

Laxman Dhulipala

Course Description

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.

Topics that could be covered:

• 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)

Advanced topics (For voting):

• 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)

Class Schedule (Could possibly change at any time)