Skip to main content
  1. Sipping Go/

Competitive Programming Essentials, Master Algorithms 2022

·6 mins

Competitive programming, is a lot of fun, competition like sports, but using what you know in the DSA world, this course will take you from not knowing anything at all, to actually compete.

Course Syllabus #

Introduction #

  • Introduction
  • Course Structure
  • Exercise Solutions (C++/Java)
  • Doubt Support
  • IDE Environment Setup
  • FAQ’s

Setting Up Sublime [Optional] #

  • Sublime Setup
  • Adding Master Header File
  • Escaping Online Judges
  • Common Code Snippets
  • Using Macros
  • Example Code Explained

Time / Space Complexity Analysis #

  • Space Time Complexity Introduction
  • Experimental Analysis
  • Big O Notation
  • Nested Loops
  • Note : Edit in Nested Loops - II
  • Nested Loops - II
  • Analysis of Bubble Sort
  • Analayis of BInary Search
  • Analysis of Merge Sort
  • Avoiding TLE Errors
  • Complexities for Worst Case AC

Data Structures & STL Containers #

  • Data Structures & STL Containers Revisited
  • Arrays in C++
  • Array STL
  • Vector STL
  • Deque STL
  • Stack STL
  • Queue STL
  • Priority Queue STL
  • [Webinar] Hashing STL
  • [Webinar] More on STL

Bitmanipulation Basics #

  • Bitwise Operators
  • Left Shift & Right Shift
  • Odd Even
  • Get ith Bit
  • Clear ith Bit
  • Set ith Bit
  • Update ith Bit
  • Clear Last i Bits
  • Clear Range of Bits
  • Replace Bits
  • Two Power
  • Count Bits
  • Count Bits Hack
  • Make it Binary

Bitmanipulation Problems #

  • Unique Number - I
  • Unique Number - I Code
  • Unique Number - II
  • Unique Number - II Code
  • Unique Number - III
  • Unique Number - III Code
  • Finding Subsets
  • Finding Subsets Code
  • Travelling Salesman Problem
  • Travelling Salesman Intution
  • Travelling Salesman Code
  • Travelling Salesman - DP Optimisation

Big Integers #

  • Welcome!
  • Introduction to Big Integers
  • Big Addition Concept
  • Big Addition Code
  • Array & Integer Multiplication
  • Large Factorials
  • Java Big Integer Class
  • BigInteger Example
  • Big Integers in Python
  • Python’s Handling of Big Integers
  • Big Integer Challenge - Julka
  • Big Integer Challenge Solution

Linear Recurrences & Matrix Exponentiation #

  • Binary Exponentiation
  • Modular Binary Exponentiation
  • Fast Mutiplication
  • Matrix Exponentiation Introduction
  • Matrix Exponentiation Code
  • Fibosum (spoj)
  • Fibosum(second approach)

Pigeonhole Principle #

  • Pigeonhole Principle
  • Problem DIVSUB
  • Applying Pigeonhole Principle
  • Gray Similar Code
  • Holiday
  • Holiday Code

Mathematical Expectation #

  • Expectation
  • Linearity of Expectation
  • Problem - Linearity of Expectation
  • Expected Throws - One Head
  • Expected Throws - Two Consecutive Heads
  • Expected Throws - N Consecutive Heads
  • Bernaulli’s Trial
  • Choose Number
  • Bernoulli’s Trial
  • Coupon Collector

Inclusion Exclusion Principle #

  • Inclusion Exclusion
  • Generalised Function
  • Problems
  • Total Number of Divisors Till N code

Prime Numbers & Factorisation #

  • Introduction
  • Prime Sieve
  • Sieve of Eratosthenes Code
  • Prime Queries
  • Prime Factorisation
  • Prime Factorisation Code O(N)
  • Prime Factorisation Code O(Sqrt(N))
  • Prime Factorisation using Sieve O(LogN)
  • Segmented Sieve
  • Segmented Sieve Algorithm
  • Segmented Sieve Code

Extended Euclidean’s Algorithm & Applications #

  • GCD
  • Euclid’s Algorithm Code
  • GCD Complexity
  • Extended Euclideans
  • Extended Euclidean Example
  • Extended Euclidean Code
  • GCD using Extended Euclidean Algorithm
  • Multiplicative Modulo Inverse
  • Computing Multiplicative Modulo Inverse
  • MMI Code
  • Linear Diophantine Equations
  • Linear Diophantine Equation - Family of Solutions

Theorems in Number Theory #

  • Modulo Airthmetic
  • Modulo Arithmetic Code
  • Fermat’s Theorem
  • Factorial % P
  • nCr % P
  • Chinese Remainder Theorem
  • Totient Function
  • Totient Function code using Seive

Combinatorics #

  • Combinatorics Introduction
  • Binomial Coefficients
  • P & C Formulas
  • Computing Binomial Coefficients
  • Birthday Paradox
  • Birthday Paradox Code
  • Catalan Numbers
  • Catalan Numbers Code - Recursive
  • Catalan Numbers Code - Iterative / DP
  • OEIS
  • Introduction to Algorithms

Recursion #

  • Recursion Basics
  • Factorial
  • Fibonacci Series
  • Sorted Array Check
  • Understanding Recursion DIrections
  • Power Function
  • Fast Power
  • Tiling Problem
  • Count Strings
  • Friend’s Pairing Problem
  • Tower Of Hanoi
  • Tower Of Hanoi (code)

Backtracking #

  • Backtracking Problems
  • Finding Subsets
  • Finding Subsets Code
  • Permuations
  • Brackets
  • Brackets Code
  • N-Queen
  • N-Queen Code
  • N-Queen Ways
  • Sudoku Solver
  • Sudoku Solver Code
  • Binary Search
  • Binary Search Code
  • Lower Bound and Upper Bound
  • Lower Bound Code
  • Angry Birds
  • Angry Bird Code
  • Game of Greed
  • Game of Greed Code

Divide & Conquer #

  • Merge Sort
  • Merge Sort Code
  • Quick Sort
  • Quick Sort Code
  • Quick Select
  • Quick Select Code
  • Inversion Count
  • Inversion Count Code
  • Ternary Search
  • Ternary Search - Finding maxima/minima of a parabola (Code)

Greedy Algorithms #

  • Greedy Introduction
  • Indian Coin Change
  • Greedy vs DP
  • Activity Selection / Busyman
  • Baised Standings
  • Kingdom Defense

Meet In The Middle #

  • Introduction
  • Subsums Code

Segment Trees #

  • Introduction to Range Queries
  • Introduction and Structure
  • Building
  • Query
  • Update
  • Facts and Properties
  • Code

Lazy Propagation #

  • Introduction
  • Algorithm
  • Code
  • Bug and Code Continued

Fenwick Trees #

  • Structure
  • Query
  • Update
  • Code
  • Inversion Count (Multiple Ways of solving it)
  • Inversion Count Using Fenwick Tree
  • Inversion Count Using Fenwick Tree Code

Sqrt Decomposition #

  • Sqrt Decomposition Introduction
  • Range queries (Code)
  • DQUERY SPOJ using Mo’s Algorithm
  • Sorting the queries according to MO’s comparator
  • 4 Pointers Technique
  • Code and Complexity of MO’s Algorithm
  • DQUERY using Fenwick Tree

Combinatorial Games #

  • Game Theory Introduction
  • Combinatorial Games
  • Take Away Games
  • N and P positions

The Game Of NIM #

  • Game of Nim
  • Nim Sum
  • Applications of Nim Sum
  • Examples of Nim Games

Graph Traversals #

  • Graphs Introduction
  • Introduction
  • Graph Key Concepts
  • Adjacency List
  • Adjacency List
  • BFS Concept
  • BFS
  • DFS
  • DFS Code
  • Shortest Path
  • Shortest Path Code
  • Board Game
  • Board Game Code

Graphs as Trees #

  • Trees
  • DFS on Trees
  • DFS Trees and Backedges
  • DFS Tree and Backedges Code

Lowest Common Ancestors #

  • LCA introduction
  • LCA Brute Force
  • LCA using Binary Lifting

Directed Graphs & SCC’s #

  • Intro
  • Topological Sort
  • SCC Theory
  • Condensed Component Graph
  • Kosaraju Algorithm for Strongly Connected Component
  • Kosaraju Algorithm Code

Disjoint Set Union Data Structure #

  • DSU Introduction
  • DSU Data Structure
  • Union & Find Ops
  • DSU Implementation
  • Union By Rank
  • Path Compression

Spanning Trees #

  • Dry Run
  • Prim’s Algorithm
  • Prim’s Code
  • Kruskal’s Algorithm
  • Kruskal’s Code

Shortest Paths Algorithms #

  • Shortest Path Introduction
  • Dijkstra’s Algorithm
  • Dijkstra’s Algorithm Code
  • Bellman Ford Algorithm
  • Bellman Ford Code
  • Floyd Warshall Algorithm
  • Floyd Warshall Code

Classical Dynamic Programming #

  • Introduction to Dynamic Programming
  • A Note About DP
  • N-K Ladders
  • N-K Ladders Top Down
  • N-K Ladders Bottom Up
  • Minimum Jums
  • Minimum Jumps Code
  • Longest Increasing Subsequence
  • Longest Increasing Subsequence Code
  • Box Stacking Problem
  • Box Stacking Code

Advance Dynamic Programming Problems #

  • Terms and Definitions
  • Tabulation vs Memoisation
  • Frogs - 1
  • Frogs - 2
  • Vacation
  • Knapsack 1
  • Knapsack 2
  • LCS
  • LCS (code)
  • Longest Path
  • Longest Path (code)
  • Grid 1
  • Grid 1 (code)
  • Coins
  • Coins (code)
  • Sushi
  • Sushi (code)
  • Stones
  • Deque (first solution)
  • Deque (second solution)
  • Candies
  • Candies (code)
  • Slimes
  • Slimes (code)
  • Matching
  • Matching continued…
  • Matching (code)
  • Independent Set
  • Independent Set (code)
  • Flowers
  • Flowers using segment tree
  • Flowers (code)
  • Walk
  • Walk (code)
  • Digit Sum
  • Digit Sum (code)
  • Permutation
  • Permutation (Brute Force)
  • Permutation (code)

Pattern / String Matching #

  • Introduction to Advanced Module!
  • Brute Force Pattern Matching using STL
  • Trie
  • Pattern Matching using Trie
  • String Hashing - Polynomial Hash Function
  • Polynomial Hash Code
  • Rolling Hash / Rabin Karp Algorithm
  • Rabin Karp algorithm Code

Geometric Algorithms - Convex Hull #

  • Introduction
  • Orientation of Points
  • Graham’s Scan algorithm
  • Graham’s Scan Algorithm Code
  • Problem - Polygon (Codeforces)

Interactive Problems #

  • Introduction
  • Codeforces - Guess the Number
  • Guess the Number - code
  • Lost Numbers
  • Lost Numbers (code)
  • Xor Guessing
  • Xor Guessing (code)

Random Randomisation #

  • Randomised Random Function
  • Run Code for a Particular Time

Policy Based Data Structures #

  • Introduction & Applications
  • Structure and Working
  • Using Coding Minutes IDE
  • Inversion Count using PBDS

CP Guidance #

  • Getting started with Codeforces / Spoj
  • Where to practice?