Getting Started with Competitive Programming

(an NPTEL course)

Week 0. Prerequisites

The major prerequisites for this course include topics from elementary data structures and algorithms — specifically, asymptotic notation, arrays, lists, stacks, queues, search trees, trees, graphs; sorting, searching, BFS/DFS, shortest path algorithms (Dijkstra and Bellman-Ford), MST algorithms (e.g, Prim's and Kruskal's algorithms) and network flows (e.g, Ford-Fulkerson).

More specific prerequisites can be found in the weekly pages. Note that you need not be completely familiar with the implementations in the context of the algorithms mentioned above, although some competence with implementing basic data structures (arrays, lists, stacks, queues, and graphs) in some programming language will be helpful.

In particular, for the topics of DSU, BFS/DFS, MST, Shortest Paths, Flows — we will learn about concrete implementations in at least one language for these as a part of this course; but what we will not cover is proofs of correctness for either the correctness or the claimed performances of said algorithms).

You can also get your own competitive programming environment setup, and prepare by creating accounts on the contest platforms that we will use frequently, by following some of the resources listed here.


Spoiler alert!

Week 0 Assignment solutions below.