Introduction
This course aims to prepare students in competitive problem solving.
It will benefit students who want to compete in ICPC, invited high school students who want to compete in IOI, and students in general who aspire to excel in technical interviews of top IT companies.
It covers techniques for attacking and solving challenging computational problems. Fundamental algorithmic solving techniques covered include complete search, divide/reduce/transform and conquer, greedy, dynamic programming. Domain specific techniques like graph, mathematics-related, string processing, and computational geometry will also be covered.
Programming language libraries that are commonly used in problem solving will also be taught.
Prerequisites
- INTRODUCTION TO PROGRAMMING IN C++
- COMPETITIVE PROGRAMMING I
Syllabus
- Union-Find Disjoint Sets & MST
- SSSP (Dijkstra & Bellman)
- Floyd–Warshall
- Iterative Dynamic Programming
- Recursive Dynamic Programming
- Dynamic Programming, Memory Reduction Trick
- Hashing & Rabin-Karp
- Z Algorithms & KMP
- Trie, Dynamic Programming & KMP
- Sparse Table
- Lowest Common Ancestor
- Binary Indexed Tree
- Segment Tree
- Segment Tree with Lazy Propagation
- Square Root Decomposition & MO's algorithm
You will be tested at the end of the training. If you do not pass the test, you will repeat the same training for free.
Duration
- 8 Weeks
- 2 Lectures per week
- 3 Hours for each lecture
- 2 Practice sessions per week (Optional)
- 4 Hours for each session