The Floyd-Warshall algorithm (also known as Warshall’s algorithm) is an algorithm used to find the shortest paths in a weighted graph with positive or negative edge weights. The algorithm was developed by Robert Floyd and Stephen Warshall in 1962. Here’s how the algorithm works: The floydWarshall function takes a 2D array graph representing the adjacency … Read more
Dijkstra’s algorithm is a popular algorithm used in computer science to find the shortest path between two nodes in a weighted graph. The algorithm was invented by Edsger W. Dijkstra in 1956. Here’s how the algorithm works: Dijkstra’s algorithm is commonly used in applications such as routing protocols in computer networks, finding shortest paths in … Read more
Huffman tree, also known as Huffman coding, is a data compression algorithm used to encode data in a way that reduces the amount of space required to store it. The algorithm was developed by David A. Huffman in 1952. The idea behind Huffman coding is to use variable-length codes for different characters, with shorter codes … Read more
Fractional Knapsack is a type of knapsack problem where an algorithm is designed to find the maximum possible value that can be obtained by filling a knapsack of a given capacity with a set of items that have individual weights and values. The key difference between the Fractional Knapsack problem and the 0/1 Knapsack problem … Read more
A spiral matrix is a matrix of m rows and n columns with each cell containing an integer value. The traversal of a spiral matrix is a way of visiting every cell in the matrix in a spiral order, starting from the top-left corner and moving in a clockwise direction. To traverse a spiral matrix, … Read more
The rope cutting problem is a classic problem in mathematics and computer science that involves cutting a rope into pieces of a certain length. The problem is usually stated as follows: Given a rope of length L, and a set of integers representing the desired lengths of the pieces, what is the minimum number of … Read more
The Josephus problem is a classic puzzle that involves a group of n people arranged in a circle. The problem is named after the Jewish historian Flavius Josephus, who according to legend, had to use this strategy to avoid being captured and killed by the Romans during the Jewish-Roman War. The problem statement is as … Read more
The Knuth-Morris-Pratt (KMP) algorithm is a string-matching algorithm that efficiently finds occurrences of a pattern string within a larger text string. It was developed by Donald Knuth, Vaughan Pratt, and James Morris in 1977 and is considered to be one of the most efficient string-matching algorithms. The basic idea behind the KMP algorithm is to … Read more
The Rabin-Karp algorithm is a string searching algorithm that finds the occurrence of a pattern string P in a text string T with a time complexity of O(n+m), where n is the length of T and m is the length of P. The algorithm uses hashing to efficiently compare the pattern with substrings of the … Read more
Kosaraju’s algorithm is a linear time algorithm for finding all strongly connected components (SCCs) in a directed graph. The algorithm was developed by S. Rao Kosaraju in 1978, and it is widely used due to its simplicity and efficiency. The algorithm works by performing two depth-first searches (DFS) on the graph. First, it performs a … Read more
