👋 Welcome to the notes and resources page for Getting Started with Competitive Programming, a MOOC offering on the Swayam/NPTEL platform. This course is offered jointly with Arjun Arul.
You can find the community blog for this course here. Also, you can join the Discord community for the course by following this invite link. Please email any corrections to neeldhara.m@iitgn.ac.in - thank you!
Class PlanQuick LinksGrading PolicyPrerequisites and ReferencesContributeFrequently Asked QuestionsCredits
Class Plan
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).
Class Plan & Materials
Pre-Requisites
Start Here
Discover what you need before you get started!
Ad-Hoc and Implementation
Week 01
In this week, we work through problems that don't require any specific data structures or algorithms tools to be solved. They will typically require some observations based on first principles and can be thought of as general puzzles.
Numbers Game
Will It Stop?
Reversort
Engineering 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 Sort
The Meeting Place Cannot Be Changed
Magic Ship
Simple 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 Marriage
Oversized Pancake Flipper
Islands 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 Arrays
War
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 bipartiteness
Diamond 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
Quick Links
- Link to the playlist of live sessions in this course (Coming soon.)
- List of corrections (Coming soon.)
Grading Policy
If you have taken up this course through Swayam, then you would need to be formally enrolled in the course, and register for the certification exam to get a certificate of completion for the course.
You can sign up for the exam using this link.
Please note that the last date for filling the exam registration form and paying the standard exam fees (1000 INR) is 13th September, 2021. After this, you can still register up to 17th September, 2021, but with a fee of 1500 INR (late fees included).
The grading policy is as follows.
- 12.5% of the final grade comes from the weekly quiz-based assignments. The best 8 out of 12 scores are considered.
- 12.5% of the final grade comes from the weekly programming assignments, where the weekly score is the average of the programming assignments every week. Again, only the best 8 out of 12 are considered.
- 75% of the final grade comes from the final exam, which is held at a physical location and whose format is similar to the weekly quizzes. Please note that there are no programming-based assessments in the final exam.
You will be eligible for a certificate only if average assignment score (quizzes and programming assignments combined) 10/25 and exam score 30/75. If one of the two criteria is not met, you will not get the certificate even if the final score is 40/100.
Prerequisites and References
Prerequisites:
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).
References:
Books.
- Algorithms by Jeff Erickson
- Open Data Structures by Pat Morin
- Algorithms Illuminated by Tim Roughgarden
- Algorithm Design by J. Kleinberg and E. Tardos
- Problem Solving with Algorithms and Data Structures using C++ by Brad Miller, David Ranum, and Jan Pearce
- Problem Solving with Algorithms and Data Structures using Python by Brad Miller and David Ranum
- Think Data Structures by Allen B. Downey
- Some introductory notes on Design and Analysis of Algorithms (PDF) by Venkatesh Raman
- Competitive Programming (4th Edition) by Steven Halim, Felix Halim, and Suhendry Effendy
- Competitive Programmer’s Handbook by Antti Laaksonen
Other NPTEL Courses. DSA with Python by Madhavan Mukund ⸱ DSA by Naveen Garg
Blogs. Petr Mitrichev
We've put together a quick-start C++ Primer (work in progress).
Let us know if you have any suggestions for additions here!
Contribute
Write for the community blogSubmit PRs to the lectures repositorySuggestions and CorrectionsFrequently Asked Questions
What languages will the lectures use?
Mostly C++ and Python; although sample solutions will often be made available in both.
In what languages can we submit the programming assignments?
The NPTEL platform supports C, C++, Python, and Java.
What are the prerequisites?
Please see the prerequisites section. More specific prerequisites can be found in the weekly pages. Note that you need not be familiar with the implementations of all the algorithms mentioned in the prerequisites (in particular, 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).
Will this help with interviews at “big tech” companies?
This course isn’t exactly Cracking the Coding Interview. There are more focused resources if that is your main goal and especially if you have something coming up soon 😃
Having said that, this course will develop your problem-solving abilities in general and give you some strong impetus to practice your programming skills as well. ✌️
So overall — it should be helpful! 🤞
Just remember that the course isn’t a magic bullet (and nothing is, AFAWK).
How much will my rating increase by the end of this course?
This is a hard one! The short answer is: it depends.
…on many factors, including where you were when you started the course, how much time you are able to put in, and so on.
In general, if you go through with the course you should be able to level up one or two notches from whereever you are starting out, but keep in mind that there are various factors that influcence these very specific measures of progress — so be patient and don’t judge yourself too much along the way.
Meanwhile, DO try to enjoy the process 🎉
How much time do I need to commit weekly?
Between 2.5 — 4 hours for the videos (especially if you pause and ponder as you go along, which is definitely recommended), and another 3-4 hours for the assignments (the MCQ/short answer and programming assignments combined).
The test cases ARE WRONG in the programming assignments! What should I do?
If you are having some trouble with the programming assignments (WAs or TLEs) and you are absolutely convinced that there is a technical issue, please post a request for a clarification in the Discord community or the Google Groups mailing list. Someone will get back to you ASAP.
In general, to everyone who's working through either programming assignments or contest problems: we all know the feeling when you are ABSOLUTELY SURE that THE TEST CASES ARE WRONG.
We'll just say that while there are some very rare occurrences when there are mistakes, what is a lot more common is that there has been some misunderstanding of the problem statement. You might be right in the context of the problem that you have in your mind, but please consider that that problem may not be the same as the one you are supposed to solve.
Overall, we don't want to suggest that you shouldn't have the confidence to question the questions - you absolutely should. It's even okay to rant a bit with us - but when you are getting pointers suggesting that you might need to revisit your thought process, please do take the time to read everything VERY CAREFULLY again
Once again: errors aren't impossible at all, and we promise to make our best effort to let you know swiftly if there is an issue. But if you haven't heard from us about a correction, and you're hearing from peers for whom things worked out, then please be patient and go back to the drawing board a bit. Thanks!
My VERY EFFICIENT CODE is timing out on the server! What should I do?
Please see the answer to the question above, which applies here as well.
When we use STL algorithms extensively, we generally don't remember the time complexity of all the functions available and this tends to be a problem when we code any problem and we tend to lose track of the overall complexity of our code. Can you suggest any measures to overcome this problem?
We would say that half of the problem is already solved because you've identified this issue yourself 🙂 That's a great first step.
Our recommendation is to not think of STLs as rote learning stuff. Spend some time going through the documentation when you first come across a new DS/algo, and get a feel for it. You don't need to understand every detail of how it is implemented under the hood, but you should have a general idea of what's happening. This should solve most of the issues.
If you know that set uses some kind of balanced binary search tree, then it becomes easier to remember that most operations using it would be . Similarly, if you know the difference between an ordered and an unordered map, you'll understand why their time complexities differ, and where exactly you can use each of them. So basically, we would suggest that you understand an STL (to an extent, not necessarily in detail), rather than try to remember features and complexities of it.
The next step is to get a feel for how 'heavy' an STL is. That is, the associated with a set has a pretty larger constant attached to it, as opposed to the pretty small constant attached to binary_search. These, you'll kind of learn the hard way 😃 You can also look up some references on this, but it's perhaps not worth spending too much time on it at the beginning.
Are there any tips or tricks that you can share for coming up with edge cases?
- On the Algorithmic Toolbox course on Coursera, you can find some guidelines for stress testing your solutions, which is a good way of coming up with edge cases in Week 1.
- Many problems have community-contributed tests on the site Udebug which is quite popular as well.
- Some platforms provide all their test data for practice problems. These include HackerEarth, AtCoder, and CSES.
- Sometimes you can just try literal edge cases - extreme values of input, what’s happening in the “corner” cases of your loops, and so on.
- It is also useful to create large inputs with some special structures where it’s easy for you to directly evaluate the answer (when a brute force solution is not feasible because of the largeness of the data), and compare it with what your program is doing.
What's the difference between doing this on Swayam and not being officially enrolled in the course?
Without being formally enrolled in the course, you can still have access to:
- Lecture videos as found on this webpage
- Informal access to a community of learners during any ongoing edition of the course (currently at Discord)
- Pointers to practice problems (see the "Extras" section in each week)
What you won't have access to:
- The weekly assignments and exams, which can only be accessed from within the Swayam course portal
- The opportunity to earn a certification from NPTEL/Swayam
If you are interested in the certification or accessing the assignments, then please watch out for the next edition of the course. Enrolment windows typically open during November/December and June/July every year.
Credits
Once the first edition has run its course, we will update this section with names of the learners who contributed to making the course better for everyone.
Many thanks to everyone who's pitched in already! 👍