I’ll start with what I do not mean by this question. I know you need to know programming and data structures, but what I am asking about is specific algorithms and theorems.
The ones I can enumerate now (edited after some answers):
- BFS
- DFS
- Dijkstra’s algorithm
- Chinese Reminder Theorem
- Dynamic Programming with memoisation or tabularisation
- operations on linked lists
- binary search
- Interval arithmetic
- GCD and LCM
- bitwise operations
- Topological sorting
- Shoelace formula
- mod inverse
- Linear algebra
- Priority queues
- Parsing algos
- Spectral decomposition
- A* algorithm
- honestly a lot of other graph algorithms, just be aware of them, and be able to find algorithms you didn’t know before
- OEIS
- SMT solvers
- set operations on intervals