Getting Started with Competitive Programming
(an NPTEL course)
Home ⸱ Quick Links ⸱ Grading Policy ⸱ References ⸱ FAQ ⸱ Feedback ⸱ Connect ⸱ Credits
Announcements
- The next edition of this course will be back in August. Feel free to explore the materials here until then! If you want to learn alongside a cohort and have access to assignments, make sure to register for the NPTEL version of the course.
The current edition of the course will run between24th January and 15th April 2022.The exam date is23 Apr 2022.- Check out the call for TAs and volunteers for the August edition of the course!
- You can join the Discord community for the course by following this invite link.
👋 Welcome to the notes and resources page for Getting Started with Competitive Programming, a MOOC offering on the Swayam/NPTEL platform. The first edition of this course was launched in August 2021, and it was co-taught by Arjun Arul from Codechef.
You can find pointers to prerequisite materials and optional practice problems on the weekly pages below. If you are enrolled in the course through Swayam then you will also have access to weekly assignments (MCQs and programming assignments).
Ad-Hoc and Implementation
Week 01
In this week, we explore some puzzle-based problems in competitive programming. These don’t require any specific algorithmic background, but instead rely on ad-hoc observations and often simple implementations.
Numbers GameWill It Stop?ReversortEngineering Reversort
Searching and Sorting
Week 02
In this week, we explore applications of searching and sorting. Our emphasis will be on how to identify that these techniques are applicable - and in particular, we will not be implementing sorting algorithms from scratch.
Trouble SortThe Meeting Place Cannot Be ChangedMagic ShipSimple Skewness
Greedy Algorithms
Week 03
In this week, we explore a very popular paradigm of algorithms design - the greedy strategy. Greedy algorithms are very natural and usually simple, but also often wrong! We will learn about examples when the strategy works, but also when it doesn't.
Stable MarriageOversized Pancake FlipperIslands War
Disjoint Set Union
Week 04
In this week, we introduce a popular data structure that's variously known as Union Find, Disjoint Set Union, or simply Disjoint Sets. We implement this data structure with a couple of useful heuristics and encounter a variety of applications.
Destroying ArraysWar
BFS and DFS
Week 05
In this week, we look at two fundamental graph traversals - BFS and DFS. After understanding how to implement these traversals, we consider three different applications.
Cover It!Mahmoud and Ehab and the bipartitenessDiamond Inheritance
Shortest Path
Week 06
In this week, we look at shortest path algorithms in various scenarios - for unweighted graphs (BFS), graphs with positive edge weights (Dijkstra), graphs with positive and negative edge weights but no negative cycles (modified Dijkstra), and finally the most general case (Bellman-Ford). We also look at the all-pairs shortest path problem (APSP; Floyd-Warshall).
Minimum Spanning Trees
Week 07
In this week, we study two popular algorithms for finding Minimum Spanning Trees (namely Prim's algorithm and Kruskal's algorithm), and also look at one variant in the context of an application.
Network Flows - I
Week 08
In this week, we introduce the maxflow problem, study the approach of Ford-Fulkerson and Edmonds-Karp, and round off by modelling a couple of problems as flow networks - specifically, maximum matching and IPL elimination.