×
Home Discussions Write at Opengenus IQ
×
  • About
  • Track your progress
  • Deep Learning Projects
  • Python Projects
  • Join our Internship 🎓
  • RANDOM
  • 100+ Graph Algorithms
  • 100+ DP Problems
  • 50+ Linked List Problems
  • 50+ Array Problems
  • One Liner
  • 50+ Binary Tree problems
  • Home
  • Rust Projects
Sadanand Vishwas

Sadanand Vishwas

Engineer at Samsung R&D Institute Bangalore | Intern at OpenGenus | Bachelor of Technology (2016 to 2020) in Computer Science at National Institute of Technology Raipur

Raipur, Chattisgarh, India •
19 posts •
Algorithms

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

Sadanand Vishwas Sadanand Vishwas
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.

Sadanand Vishwas Sadanand Vishwas
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.

Sadanand Vishwas Sadanand Vishwas
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.

Sadanand Vishwas Sadanand Vishwas
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.

Sadanand Vishwas Sadanand Vishwas
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.

Sadanand Vishwas Sadanand Vishwas
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

Sadanand Vishwas Sadanand Vishwas
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).

Sadanand Vishwas Sadanand Vishwas
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.

Sadanand Vishwas Sadanand Vishwas
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.

Sadanand Vishwas Sadanand Vishwas
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).

Sadanand Vishwas Sadanand Vishwas
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

Sadanand Vishwas Sadanand Vishwas
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.

Sadanand Vishwas Sadanand Vishwas
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

Sadanand Vishwas Sadanand Vishwas
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.

Sadanand Vishwas Sadanand Vishwas
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

Sadanand Vishwas Sadanand Vishwas
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.

Sadanand Vishwas Sadanand Vishwas
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

Sadanand Vishwas Sadanand Vishwas
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.

Sadanand Vishwas Sadanand Vishwas
OpenGenus IQ © 2023 All rights reserved ™ [email: team@opengenus.org]
Top Posts LinkedIn Twitter