Competitive Programming Essentials, Master Algorithms 2022

Table of Contents

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 #

Length: 56H
Original: https://www.udemy.com/course/competitive-programming-algorithms-coding-minutes/
Price: $12
Author: Coding minutes

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