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