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 between~~ ~~24th January and 15th April 2022~~. ~~The exam date is~~ ~~23 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).

Pre-Requisites

Start Here

Discover what you need before you get started!

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.

Network Flows - II

Week 09

In this week, the focus will be on the minimum cut problem, which turns out to be equal to the maxflow. We study a couple of problems where we are required to find the minimum cut or related quantities, and revisit IPL elimination.

Dynamic Programming - I

Week 10

Dynamic Programming - II

Week 11

Dynamic Programming - III

Week 12

Getting Started with Competitive Programming

Getting Started with Competitive Programming

Class Plan & Materials