Longest Common Subsequence (LCS)
Explanation Video
Posts
Optimal Binary Search Tree
Explanation Video Normal binary search tree In given set of elements how many binary search trees are possible? Tree that gives optimal/best search result based on given frequency on keys, is called Optimal BST. Generate Optimal BST Video 2 Cost of searching element in BST Greeksforgreeks link
0/1 Knapsack - Two Methods
Explanation Video Using Set method Program explanation video Greeksforgreeks link
Bellman Ford Algorithm - Single Source Shortest Path
Explanation Video Relax values of edges V-1 times. This algorithm won't work if there is -ve weight edge and form a circle. To verify if there is a circle we can run algorithm 1 additional time and see if weight is getting relaxed for any edge. Greeksforgreeks
Matrix Chain Multiplication
Explanation Video To multiply 2 matrix, the number of columns in 1st matrix and number of rows in 2nd matrix must be equals. The result matrix will be number of row in 1st matrix X number of columns in 2nd matrix When you have to multiply many matrix then first find out which one to multiply first to reduce number of multiplications. Matrix Chain Multiplication algorithm help to parenthesise different matrix so we can multiply them with optimal effort. Greeksforgreeks link
All Pairs Shortest Path
Explanation Video Java Program /* package codechef; // don't place package name! */ import java.util.*; import java.lang.*; import java.io.*; /* All Pairs Shortest Path (Floyd-Warshall) - Dynamic Programming. */ class AllPairsShortestPath { // Find shortest path private static int[][] floydWarshall() { // Get input graph int[][] graph = populateGraph(); // Size of the graph int size = graph.length; for(int k = 0; k < size; k++) { for(int i = 0; i < size; i++) { for(int j = 0; j < size; j++) { // Perform operation if it do not have INFINITE ...
Dynamic Programming introduction
Explanation Video Greedy method and Dynamic Programming both are used to solved optimisation problems. Both are different strategies but the purpose is the same. Optimisation problems are those that requires minimum or maximum results. In Greedy method we try to follow predefine procedure to get the optimal result since procedure is known to be optimal. In Dynamic Programming we try to find out all possible solutions and then pick up the best solution. Dynamic programming problems are solved using recursive formulas but it's not recursion. Dynamic programming follow the principle of optimality. Principle of optimality says that the problem can be solve by taking the sequence of decisions to get the optimal result. In Greedy method decision is taken one time and in Dynamic programming decision is taken in every stage. Tabulation-vs-Memoization Memoization follow top down approach Tabulation follow bottom up approach In Dynamic programming mostly problems are solved using tabu...
Dijkstra Algorithm
Explanation Video It works on both directed or non directed graph. Works only for +ve values of edge. This algorithm may or may not work when edges have -ve values. For example it fails in below case.
Prims and Kruskals Algorithms
Explanation Video : We can find spanning trees for connected graphs only. Prims Algorithm : Select smallest weight edge and always select connected smallest one. Kruskals Algorithms : Select all (connected or not connected) minimum cost edges that don't form a circle and form a tree. It may find minimum weight tree from the given unconnected graph but that may not be spanning tree. Find missing edge In a given graph there can be more than one spanning trees that gives optimum result but there can be only one optimum result for spanning tree in a given graph.