Longest common subsequence: This algorithm finds the longest subsequence that is common to two strings. It is used in many applications, such as text comparison and DNA sequence analysis.
Edit distance: Given two strings str1 and str2 of length M and N respectively and below operations that can be performed on str1. Find the minimum number of edits (operations) to convert ‘str1‘ into ‘str2‘. It is used in many applications, such as text comparison and spell checking.
Longest common prefix: The longest common prefix for an array of strings is the common prefix between 2 most dissimilar strings. For example, in the given array {“apple”, “ape”, “zebra”}, there is no common prefix because the 2 most dissimilar strings of the array “ape” and “zebra” do not share any starting characters.
Sequence Alignment: Algorithms that align two or more sequences in order to find similarities and differences between them. The Needleman-Wunsch algorithm is a dynamic programming algorithm that finds the global alignment of two sequences. It works by building a matrix of all possible alignments of the two sequences, and then choosing the alignment with the highest score.
Z algorithm: This algorithm finds all occurrences of a pattern in a text in linear time. Let length of text be n and of pattern be m, then total time taken is O(m + n) with linear space complexity. Now we can see that both time and space complexity is same as KMP algorithm but this algorithm is simpler to understand.
Knapsack problem: The Knapsack problem is an example of the combinatorial optimization problem. This problem is also commonly known as the “Rucksack Problem''. The name of the problem is defined from the maximization problem as mentioned below:
Example: Given a bag with maximum weight capacity of W and a set of items, each having a weight and a value associated with it. Decide the number of each item to take in a collection such that the total weight is less than the capacity and the total value is maximized.
Fractional Knapsack Problem: Given the weights and profits of N items, in the form of {profit, weight} put these items in a knapsack of capacity W to get the maximum total profit in the knapsack. In Fractional Knapsack, we can break items for maximizing the total value of the knapsack.
0/1 Knapsack Problem: We are given N items where each item has some weight (wi) and value (vi) associated with it. We are also given a bag with capacity W. The target is to put the items into the bag such that the sum of values associated with them is the maximum possible. Note that here we can either put an item completely into the bag or cannot put it at all.
Rod cutting: This algorithm finds the optimal way to cut a rod of length n into smaller rods, such that the total profit is maximized. It is a classic dynamic programming problem that has many applications in inventory management and manufacturing.
Bin packing: Given n items of different weights and bins each of capacity c, assign each item to a bin such that number of total used bins is minimized. It may be assumed that all items have weights smaller than bin capacity.
Subset sum: Given a set of non-negative integers and a value sum, the task is to check if there is a subset of the given set whose sum is equal to the given sum.
Minimum coin change problem: This algorithm finds the minimum number of coins needed to make a given amount of change. It is a classic dynamic programming problem that has many applications in finance and economics.
Word wrap: Given a sequence of words, and a limit on the number of characters that can be put in one line (line width). Put line breaks in the given sequence such that the lines are printed neatly. Assume that the length of each word is smaller than the line width. Word processors like MS Word do the task of placing line breaks. The idea is to have balanced lines. In other words, do not have a few lines with lots of extra space and some lines with a small amount of extra space.
Traveling salesman problem (TSP): This algorithm finds the shortest tour that visits each city in a set of cities exactly once. It is a classic NP-hard problem that has many applications in transportation and logistics.
Ford-Fulkerson algorithm: The max flow problem is a classic optimization problem in graph theory that involves finding the maximum amount of flow that can be sent through a network of pipes, channels, or other pathways, subject to capacity constraints. The Ford-Fulkerson algorithm is a greedy algorithm for computing the maximum flow in a flow network. The problem can be used to model a wide variety of real-world situations, such as transportation systems, communication networks, and resource allocation.
Edmonds-Karp algorithm: The Edmonds-Karp algorithm is an efficient implementation of the Ford-Fulkerson method for finding the maximum flow in a flow network. It is primarily used to solve the maximum flow problem, which is a fundamental problem in network flow theory.
Optimal binary search tree (OBST): This algorithm constructs a binary search tree for a given set of keys, such that the expected search time is minimized. It is used in many applications, such as database systems and search engines.
Maximum subarray sum: This algorithm finds the maximum sum of a contiguous subarray of an array. It is used in many applications, such as finding the maximum profit in a stock market chart or the minimum cost of a path between two nodes in a graph.
Palindrome partitioning: This algorithm finds the minimum number of partitions needed to divide a string into palindromes. It is used in many applications, such as text processing and natural language processing.
Assembly line scheduling: Assembly line scheduling is a problem in operations management that involves determining the optimal sequence of tasks or operations on an assembly line to minimize production costs or maximize efficiency. This problem can be solved using various data structures and algorithms. One common approach is dynamic programming, which involves breaking the problem down into smaller sub-problems and solving them recursively.
A* Search Algorithm: The A* search algorithm is a graph search algorithm that finds the shortest path between a start node and a goal node. It is a heuristic algorithm, which means that it uses a heuristic function to guide its search. The heuristic function estimates the cost of moving from a node to the goal node. The A* search algorithm works by iteratively expanding the nodes in the graph that are closest to the goal node, based on the heuristic function.
Longest path in a directed acyclic graph: Given a directed graph G with N vertices and M edges. The task is to find the length of the longest directed path in Graph. Note: Length of a directed path is the number of edges in it.
Dijkstra's algorithm: Dijkstra's algorithm is a graph algorithm that finds the shortest path between a single source node and all other nodes in the graph. It is a greedy algorithm, meaning that it makes the locally optimal choice at each step in the hope of finding the globally optimal solution.
Bellman-Ford algorithm: The Bellman-Ford algorithm is a similar algorithm to Dijkstra's algorithm, but it can handle graphs with negative edge weights. It works by repeatedly relaxing edges in the graph, which means that it updates the distances of nodes based on the shortest known path to them.
Prim's algorithm: Prim's algorithm is a greedy algorithm that finds a minimum spanning tree (MST) for a weighted undirected graph. An MST is a subset of the edges of the graph that connects all of the vertices in the graph with a minimal total weight.
Kruskal's algorithm: Kruskal's algorithm is a greedy algorithm for finding the minimum spanning tree of a connected weighted graph. Kruskal's algorithm works by iteratively adding edges to the minimum spanning tree, starting with the edge with the lowest weight.
Floyd-Warshall algorithm: The Floyd Warshall Algorithm is for solving all pairs of shortest-path problems. The problem is to find the shortest distances between every pair of vertices in a given edge-weighted directed Graph. This algorithm follows the dynamic programming approach to find the shortest path.
Huffman coding: Huffman coding is a lossless data compression algorithm. The idea is to assign variable-length codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters.
Activity selection problem: The activity selection problem is a combinatorial optimization problem. Given a set of activities with their start and finish times, the goal is to find a maximum-sized subset of activities that can be scheduled without conflicting with each other.
Topological sort algorithms: Topological sort algorithms order the vertices of a directed acyclic graph (DAG) in a way such that all edges point from earlier vertices to later vertices in the ordering. Types: Kahn's algorithm, Tarjan's algorithm
Sorting Algorithms: Sorting algorithms rearrange a given list of elements according to a comparison operator on the elements. Types: Insertion sort, selection sort, bubble sort, merge sort, quick sort, heap sort
Hashing and Hash Tables: Two Sum Problem, Four Sum Problem, Subarray Sum Equals K, Longest Subarray with Sum K: Given an array of integers and a target sum, various problems can be solved using hashing and hash tables.
Priority Queue: A Priority Queue is a data structure in computer science that stores a collection of elements, each associated with a priority. Elements in a Priority Queue are typically ordered based on their priority, and elements with higher priorities are dequeued or processed before elements with lower priorities.
AVL Tree (Adelson-Velsky and Landis Tree): An AVL tree is defined as a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees for any node cannot be more than one. The difference between the heights of the left subtree and the right subtree for any node is known as the balance factor of the node.
Suffix Tree: A suffix tree for a given text is a compressed trie for all suffixes of the given text. Suffix trees are primarily employed for solving problems related to pattern matching, substring search, and other string-related tasks.
Suffix Array: A suffix array is a sorted array of all suffixes of a given string. A suffix array can be constructed from Suffix tree by doing a DFS traversal of the suffix tree. In fact Suffix array and suffix tree both can be constructed from each other in linear time.
Matrix Chain Multiplication: This algorithm finds the most efficient way to multiply a chain of matrices. It is a classic dynamic programming problem that has many applications in computer science.
Maximum Independent Set: Given an undirected graph defined by the number of vertex V and the edges E[], the task is to find Maximal Independent Vertex Set in an undirected graph. Independent Set: An independent set in a graph is a set of vertices which are not directly connected to each other. Note: It is a given that there is at least one way to traverse from any vertex in the graph to another, i.e. the graph has one connected component.
Maximum Weight Clique: Given a small graph with N nodes and E edges, the task is to find the maximum clique in the given graph. A clique is a complete subgraph of a given graph. This means that all nodes in the said subgraph are directly connected to each other, or there is an edge between any two nodes in the subgraph. The maximal clique is the complete subgraph of a given graph which contains the maximum number of nodes.
Job Sequencing: The job sequencing problem is a combinatorial optimization problem of finding the optimal order to sequence a set of jobs on a machine, such that the total time to complete all the jobs is minimized. The problem is NP-hard, which means that there is no known polynomial-time algorithm to solve it. However, there are a number of approximation algorithms that can be used to find good solutions to the problem in polynomial time.
N-Queens: The n-queens problem is a classic combinatorial optimization problem of placing n unattacking queens on an n×n chessboard such that none of the queens can capture another queen.
Kosaraju's Algorithm: Kosaraju's algorithm is a widely used algorithm for finding strongly connected components (SCCs) in a directed graph. Strongly connected components are subgraphs within a directed graph in which every vertex is reachable from every other vertex.
Flood Fill Algorithm: Given a 2D screen arr[][] where each arr[i][j] is an integer representing the color of that pixel, also given the location of a pixel (X, Y) and a color C, the task is to replace the color of the given pixel and all the adjacent same-colored pixels with the given color.
Hamiltonian Circuit Problem: The Hamiltonian Circuit problem is a decision problem in graph theory that asks whether there exists a Hamiltonian circuit in a given graph. A Hamiltonian circuit is a cycle that visits each vertex in the graph exactly once.
Aho-Corasick Algorithm: The Aho-Corasick algorithm is a string searching algorithm that efficiently finds all occurrences of multiple keywords (also known as "patterns") in a given input text.
Boyer Moore Algorithm: Pattern searching is an important problem in computer science. When we do search for a string in a notepad/word file, browser, or database, pattern searching algorithms are used to show the search results.
Krauss Wildcard Matching Algorithm: Given a text and a wildcard pattern, implement a wildcard pattern matching algorithm that finds if the wildcard pattern is matched with text. The matching should cover the entire text (not partial text). The wildcard pattern can include the characters ‘?’ and ‘*’.
List of Algorithms