Learn · NPTEL

Course10610623154 lectures

Getting Started With Competitive Programming

Prof. Neeldhara Misra · IIT Gandhinagar

Start with lecture 1 At NPTEL

About

This is a course on algorithm design with a focus on issues of modeling and implementation. Each lecture will be focused entirely on one or two problems that reveal the use of a specific algorithmic technique. The techniques themselves are chosen to be in line with those covered in existing NPTEL courses on data structures and algorithms, so that students who complete those courses can find in this course a natural follow up. This course is intended for anyone who wants to deepen their appreciation for algorithmic techniques that they have learned in a foundational course and/or would like to take a first step towards preparing for coding competitions such as the ICPC.

Intended audience: Undergraduate students who have already done a basic data structures/algorithms course.

Prerequisites: Data Structures and Algorithms, Familiarity with a programming language (ideally C++ or Python)

Lectures

Week 1

  1. Welcome and Initial Setup YouTube
  2. Reversort YouTube
  3. Engineering Reversort YouTube
  4. Number Game YouTube
  5. Will It Stop? YouTube

Week 2

  1. Trouble Sort YouTube
  2. The Meeting Place Cannot Be Changed YouTube
  3. Magic Ship YouTube
  4. Simple Skewness YouTube

Week 3

  1. Pancake Flipping YouTube
  2. Islands War YouTube
  3. Stable Marriage - I YouTube
  4. Stable Marriage - II YouTube
  5. When Greedy Does Not Work - Coin Change YouTube
  6. When Greedy Does Not Work - Guarding a Museum YouTube
  7. When Greedy Does Not Work - Traveling Salesman YouTube

Week 4

  1. DSU - Definition and Motivation YouTube
  2. DSU via Union by Rank and Path Compression YouTube
  3. DSU - Implementation YouTube
  4. Destroying Array - I (Problem Statement and Solution) YouTube
  5. Destroying Array - II (Implementation) YouTube
  6. War - I (Problem Statement) YouTube
  7. War - II (Solution) YouTube
  8. War - III (Implementation) YouTube

Week 5

  1. Graph Foundations YouTube
  2. BFS and DFS YouTube
  3. Mahmoud and Ehab and the bipartiteness YouTube
  4. Cover It! YouTube
  5. Diamond Inheritance YouTube

Week 6

  1. SSSP - Overview BFS Revisited YouTube
  2. SSSP and Dijkstra's Algorithm YouTube
  3. Sending Email YouTube
  4. SSSP and Modified Dijkstra YouTube
  5. SSSP with Negative Cycles - Bellman-Ford YouTube
  6. Wormholes YouTube
  7. APSP and Floyd-Warshall YouTube
  8. Page Hopping YouTube

Week 7

  1. Introduction to MSTs YouTube
  2. Prim's Algorithm YouTube
  3. Kruskal's Algorithm YouTube
  4. Cherries Mesh YouTube
  5. Heirarchy YouTube
  6. Island Hopping YouTube

Week 8

  1. Introduction to MaxFlow YouTube
  2. Ford-Fulkerson for MaxFlow YouTube
  3. Implementing Edmonds-Karp YouTube
  4. Maximum Matching via MaxFlow YouTube
  5. Sport Elimination via MaxFlow YouTube

Week 9

  1. Maxflow-Mincut Duality YouTube
  2. Police Chase YouTube
  3. Sam I AM and Vertex Covers YouTube

Week 10

  1. Top-Down Dynamic Programming with Frog 1_Part A YouTube
  2. Top-Down Dynamic Programming with Frog 1_Part B YouTube
  3. Bottom-Up Dynamic Programming with Dice Combinations YouTube

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Gandhinagar
Department
Computer Science and Engineering
Teacher
Prof. Neeldhara Misra
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge. Coordinated by IIT Madras.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Teens profiles and older, judged from what the source says about it. How courses are placed