Schedule
Topics
- Introduction
- Complete Search
- Divide and Conquer
- Game Theory
- Graph Theory
Introduction
-
Topics
- What is competitive programming?
- Topics of the course
- Virtual Judges
- Problem structure
- Veredicts information
- Environment setup
-
Topics:
- Motivation
- Sampling an extrapolation
- Big Oh notation
- Asymptotic Analysis
- Space and Time Complexity
-
Topics
- Standard Template Library (STL)
- Numeric data types and its operations
- String
- Vector
- Set
- Map
- Struct
Complete Search
-
Topics
- Problem solving paradigms
- Pythagorean triples
- Primality Test
- Sieve of Eratosthenes
- Finding the number of divisors of a number
- \(\sigma_{0}(n) = O(\sqrt[3]{n})\)
- Competitive Programming 3, section 3.2 y 5.5.1
- Codeforces - How to come up with the solutions: techniques
- Codeforces - Amount of divisors of N
- Codeforces - Counting Divisors of a Number in \(O(\sqrt[3]{n})\) - Tutorial
-
Topics
- Fixing variables
- Simulation with brute force
- Weak constraints
- Case analysis
- Extra: Prefix sums
-
Topics
- Two pointers
- Recursion
- Modular arithmetic
- Binary exponenciation
- Concrete Mathematics - Knuth. Chapter 1
- Modular Arithmetic for Beginners
- Competitive Programmer’s Handbook, chapters 5, 8 y 21
- Principles of Algorithmic Problem Solving, sections 15.6 y 15.7
- Learn Data Structures and Algorithms, section Basic Recursion
- E-maxx Binary Exponentiation
-
Topics
- Contribution technique
- Seaching over all the permutations
- Binary representation
- Bitwise operations
- Brute force on bitmasks
- Competitive Programming 3, section 2.1 and 2.2.
- Competitive Programmer’s Handbook, chapter 10
- GPC-UNI Clase 4
- GPC-UNI Clase 5
- PCUNI-2019 Clase 7
- Principles of Algorithmic Problem Solving, chapter 7
-
Topics
- Power set
- 0-1 Knapsack problem
- Permutations
- Sudoku
- N-queen problem
- HackerEarth - Recursion and Backtracking
- Competitive Programming 3, section 3.2.2, 8.2.1 and 8.2.2.
- GeekForGeeks - Backtracking Algorithms
Divide and Conquer
-
Topics
- The divide and conquer paradigm
- Binary search
- Lower bound
- Upper bound
- Binary search on the answer
-
Topics
- Generalized binary search
- Ternary search
- Merge sort
- Inductive constructions
Game Theory
-
Topics
- Introduction
- WL states
- The game of Nim
- Grundy numbers
- Sprague-Grundy theorem
-
Topics
- Grundy’s games
- Staircase Nim
- Misère games
- Minimax
- Alpha-Beta prunning
Readings
Graph Theory
-
Topics
- Introduction
- Graph representation
- Distance in graphs
- Graph isomorphism
- Graph score
- Trees
- BFS
- DFS
- Diameter of a tree
- Isomorphism of trees