Sadanand Vishwas - OpenGenus IQ: Learn Algorithms, DL, System Design

Shortest Path with k edges using Dynamic Programming

Given a weighted directed graph, we need to find the shortest path from source u to the destination v having exactly k edges. Brute force approach takes O(V^k) time complexity which we reduce to O(V^3 * k) using dynamic programming

Algorithms

Number of paths with k edges using Dynamic programming and Divide and Conquer

Given a directed graph, we need to find the number of paths with exactly k edges from source u to the destination v. A brute force approach has time complexity which we improve to O(V^3 * k) using dynamic programming which we improved further to O(V^3 * log k) using a divide and conquer technique.

Algorithms

Shortest Common SuperSequence 【O(M*N) time complexity】

Given two strings X and Y, the supersequence of string X and Y is such a string Z that both X and Y is subsequence of Z.

Algorithms

All Valid Word Breaks of a Sentence 【O(2^N) time complexity】

We are given with a valid sentence without any spaces and we are given with a dictionary of words. We need to print all the possible ways to break the sentence so that all the breaked words belongs to the dictionary.

Algorithms

Word Break Problem 【O(n * s) time complexity】

In this problem we are given with a string and a dictionary of words, we need to find if the string can be segmented to words so that all the segmented words are present in the dictionary.

Algorithms

Algorithm to find cliques of a given size k【O(n^k) time complexity】

We can find all the 2-cliques by simply enumerating all the edges. To find k+1-cliques, we can use the previous results. Compare all the pairs of k-cliques. If the two subgraphs have k-1 vertices in common and graph contains the missing edge, we can form a k+1-clique.

Algorithms

Greedy approach to find a single maximal clique in O(V^2) time complexity

There can be more than one single maximal clique in a non-complete graph (since complete graph is a maximal clique itself). To find a single maximal clique in a graph we use a straightforward greedy algorithm in O(V^2) time complexity

Algorithms

Using Bron Kerbosch algorithm to find maximal cliques in O(3^(N/3))

Bron–Kerbosch algorithm is an enumeration algorithm for finding maximal cliques in an undirected graph. Any n-vertex graph has at most 3^n⁄3 maximal cliques, and the worst-case running time of the Bron–Kerbosch algorithm (with a pivot strategy) is O(3^n⁄3).

Algorithms

Centroid Decomposition of Tree

Centroid Decomposition is a divide and conquer technique which is used on trees. Given a tree with N nodes, a centroid is a node whose removal splits the given tree into a forest of trees, where each of the resulting tree contains no more than N/2 nodes.

Algorithms

Clique in Graphs

A clique is a subset of vertices of an undirected graph G such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs.

Algorithms

Solving Vertex Cover Problem from O(2^n) to O(n^2)

Vertex Cover Problem is a known NP Complete problem. We will see Naive approach and Dynamic programming approach to solve the vertex cover problem for a binary tree graph and reduce the complexity from O(2^n) to O(n^2).

Algorithms

Understanding pairing nodes in Graphs (Maximum Matching)

A maximal matching is a matching M of a graph G with the property that if any edge not in M is added to M, it is no longer a matching, that is, M is maximal if it is not a subset of any other matching in graph G. We cover Blossom, Hungarian and Hopcroft Karp algorithm

Algorithms

Blossom Maximum Matching Algorithm

The blossom algorithm, sometimes called the Edmonds' matching algorithm, can be used on any graph to construct a maximum matching. The blossom algorithm improves upon the Hungarian algorithm by shrinking cycles in the graph to reveal augmenting paths. The blossom algorithm will work on any graph.

Algorithms

Hungarian Maximum Matching Algorithm

The Hungarian maximum matching algorithm, also called the Kuhn-Munkres algorithm, is a O(V3) algorithm that can be used to find maximum-weight matchings in bipartite graphs, which is sometimes called the assignment problem. A bipartite graph can easily be represented by an adjacency matrix

Algorithms

Hopcroft Karp algorithm

The Hopcroft–Karp algorithm is an algorithm that takes as input a bipartite graph and produces as output a maximum cardinality matching, it runs in O(E√V) time in worst case.

Algorithms

Tile Stacking Problem

We demonstrate how we will reduce the time complexity from O((k+1)^(m+1)) to O(N * M * K) to O(N * M). We have infinite number of tiles of sizes 1 to m. The task is calculate the number of different stable tower of height n with restriction that you can use at most k tiles of each size in the tower

Data Structures

Binomial Heap

Binomial Heap is an extension of Binary Heap that provides faster union or merge operation together with other operations provided by Binary Heap. A Binomial Heap is a collection of Binomial trees. Binomial Heap is used to implement priority queues.

Data Structures

Priority Queue

Priority queue is an abstract data type which is like a queue or stack data structure with each element having a priority assigned to it. In priority queue, an element with highest priority assigned is served first, if two elements have same priority then they are served according to enqueue order

Data Structures

Union Find (Disjoint Set)

A Union Find data structure (also called disjoint-set) is a data structure that keeps track of elements partitioned into a number of disjoint subsets. It provides near-constant-time operations to add new sets, to merge existing sets, and to determine whether elements are in the same set.