Repository of the Course APS-2020
- Clone Graph
- Clone LinkedList using random pointer.
- Clone a Binary Search Tree using random pointer.
- Questions based on modification of Dijikstra's algorithm - Flight Discount CSES
- Finding K shortest Routes in a graph problem - Modified Dijikstra
- Classical Problems of DP - LPS
- Longest Flight Route - DP on Graphs (Topo sort with DP)
- BFS
- DFS
- Dijkstra's Algorithm - SSSP
- Floydd Warshall - ASSP
- Bellman-Ford - Negative Edge shortest path
- Kahn's Algorithm - Topological Sorting
- Union-Find (Disjoint Set Union) - Connected Componets, Cycle detection
- Kruskal's Algorithm - MST
- Kosaraju's Algorithm - Strongly connected componets in directed graph
- Eulerian path and circuit.
- Hamiltonian path and circuit.
- Graph Coloring - Bipartite check and 4 color theorem based problems.
- Seletion problems, i.e, selecting one and leaving another. Ex - Choosing the Judge(Hackerearth), Boredom(Codeforces)
- 2D DP problems -> where state change is dependent on two variables Ex - Vacation(Codeforces)
- DP on strings - Usually we create 2D dp for such problems.
- Minimax Algorthim problems
- Bitmask dp - used in assignment problems
- DP on trees - Diameter of a tree, no of paths of lenght k in a tree
- DP on trees - Uniqe structred BST for given N (print the trees and the numbers too) - numbers can be found using catalan's number.
- DP - Maximize profit by selling stocks with at most k transtaction
- Dp - Tries and DP - Word Break II
- DP - Dungeon Game - backward iteration
- DP - Cherry Pickup - DP on grids - Find the max area square of ones - dp on grids
- Questions based on properties of XOR: eg, find missing numbers
- "Given an array of integers, every element appears k (k > 1) times except for one, which appears p times (p >= 1, p % k != 0). Find that single one."
- All nodes distance K in binary tree
- Pre-requisite: DFS on a grid
- Word Search