Competitive Programming

👋 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 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

Quick Links

  1. Invitation to the Discord Community
  2. GitHub repository of solutions to the problems discussed in the lectures
  3. Link to YouTube Playlist for the course
  4. Link to the playlist of live sessions in this course (Coming soon.)
  5. Quick start (the first set of prerequisites)
  6. Community Blog
  7. 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.

🗓️

The last date for enrolling in the course is 9th August, 2021.

🎯

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.

  1. Algorithms by Jeff Erickson
  2. Open Data Structures by Pat Morin
  3. Algorithms Illuminated by Tim Roughgarden
  4. Algorithm Design by J. Kleinberg and E. Tardos
  5. Problem Solving with Algorithms and Data Structures using C++ by Brad Miller, David Ranum, and Jan Pearce
  6. Problem Solving with Algorithms and Data Structures using Python by Brad Miller and David Ranum
  7. Think Data Structures by Allen B. Downey
  8. Some introductory notes on Design and Analysis of Algorithms (PDF) by Venkatesh Raman
  9. Competitive Programming (4th Edition) by Steven Halim, Felix Halim, and Suhendry Effendy
  10. Competitive Programmer’s Handbook by Antti Laaksonen

Other NPTEL Courses. DSA with Python by Madhavan Mukund ⸱ DSA by Naveen Garg

YouTube Channels. CodechefErrichtoWilliam LinWilliam Fiset

Visualizations. VisualgoOpenDSA

📘

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 blog
⌨️
Submit PRs to the lectures repository
📝
Suggestions and Corrections

Frequently 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! 👍