Algorithm Design Techniques
-
- Brute Force
- Greedy Algorithms
- Divide-and-Conquer, Decrease-and-Conquer
- Dynamic Programming
- Reduction / Transform-and-Conquer
- Backtracking and Branch-and-Bounding
-
The brute force algorithm is an approach that comes directly to our minds after viewing a problem. This is usually a straightforward approach based on the problem statement. We could use this approach to solve problems with small-sized datasets. Let me give you an example. Let's say you want to find the shortest path from your home to your school. The brute force solution in this case would be to consider every possible combination of roads and intersections to reach your destination. However, this method is highly inefficient, especially if there are a lot of roads.
-
- Bubble-Sort
- Selection-Sort
- Sequential search in an array
- Computing pow(a, n) by multiplying a, n times
- Convex hull problem
- String matching
- Exhaustive search: Travelling salesman, Knapsack
-
Greedy algorithms are used to solve optimization problems. These problems usually involve finding the maximum or minimum of something from the given data. In a greedy algorithm, we find the solution through a sequence of steps. At each step, a choice is made that is locally optimal. What does "locally optimal" mean? First, we take a small part of the provided data, and then we find the optimal solution within that data. After that, we'll again take some data and repeat the process. Finding the optimal solution within the data we've considered is called locally optimal.
-
- Minimal spanning tree: Prim's algorithm, Kruskal's algorithm
- Dijkstra's algorithm for the single-source shortest path problem
- Greedy algorithm for the Knapsack problem
- The coin exchange problem
- Huffman trees for optimal encoding
Divide-and-Conquer Algorithms:
- First, we divide the problem into similar subproblems.
- Then, we solve each one of these subproblems individually.
- Finally, we combine the results of the subproblems to produce the desired result.
Divide-and-Conquer vs. Decrease-and-Conquer:
In divide and conquer, the size of the problem is reduced by a factor (half, one third, etc.), while in decrease and conquer, the size of the problem is reduced by a constant.
- Merge-Sort algorithm (using recursion)
- Quick Sort algorithm (using recursion)
- Computing the length of the longest path in a binary tree (using recursion)
- Computing Fibonacci numbers (using recursion)
- Quick-Hull
JavaScript is a programming language that adds interact- Computing pow(a, n) by calculating pow(a, n/2) using recursion.
- Binary search in a sorted list (using recursion)
- Searching in BST
- Insertion-Sort
- Graph traversal algorithms (DFS and BFS)
- Topological sort
- Warshall’s algorithm (using recursion)
- Permutations (Minimal change approach, Johnson-Trotter algorithm)
- Computing a median
- Topological sorting
- Fake-coin problem (Ternary search)
Divide and Conquer:
In divide and conquer, many times the recursively solved subproblems can result in the same computation being performed multiple times. This problem arises when identical problems occur repeatedly in a recursion.
Dynamic Programming:
Dynamic programming is used to avoid this issue by storing the results of subproblems in a table and referring to that table to check if we have already calculated the solution to a subproblem before computing it again.
Dynamic programming is a bottom-up technique in which the smaller subproblems are solved first, and the results of these are used to find the solution for larger subproblems.
- Fibonacci numbers computed by iteration.
- Warshall's algorithm for transitive closure implemented by iterations.
- Floyd's algorithm for all-pairs shortest paths.
These methods work as a two-step process. First, the problem is transformed into a different problem that is already known to us, i.e., a problem for which we already know the optimal solution. Then the problem is solved.
The most common type of transformation is the sorting of an array.
For example, in a given list of numbers, find the two closest numbers. In the brute-force solution, we would find the distance between each element in the array and keep track of the pair with the minimum distance. In this approach, the total time complexity is O(n^2). In the Transform and Conquer solution, we first sort the array in O(n log n) time and then find the closest numbers by scanning the array in another single pass with time complexity O(n). Thus, the total time complexity is O(n log n).
- Gaussian elimination
- Heaps and Heapsort
Have you seen the modern lock with a 3-digit password, where the numbers range from 1 to 9? If you don't have the exact password for the lock, you need to test every combination until you find the right one. You would go from something like "111" to "112" and so on until you reach "999". In this case, what you are doing is called backtracking.
Suppose the lock produces a click sound anytime you come across a correct digit. If we can listen to this sound, it will help you reach the goal much faster. These functions are called Pruning functions or Bounding functions.
Backtracking is a method in which a solution is found by searching through a large but finite number of states. With some pruning or bounding functions, we can narrow down our search.
For all problems (like NP-hard problems) for which there does not exist any other efficient algorithm, we use the backtracking algorithm.
Key Components of the Algorithm:
- Initial state
- Target/Goal state
- Intermediate states
- Path from the initial state to the target/goal state
- Operators to get from one state to another
- Pruning function (optional)
The algorithm starts with the construction of a state tree, whose nodes represent the states. The root node is the initial state, and one or more leaf nodes will be our target state. Each edge of the tree represents some operation. The solution is obtained by searching the tree until a target is found.
Three Monks and Three Demons:
There are three monks and three demons on one side of a river. You want to move all of them to the other side using a small boat. The boat can carry only two persons at a time. If, on any shore, the number of demons is more than the number of monks, the demons will eat the monks. How can we move all of these people to the other side of the river safely?
The Farmer's Dilemma:
There is a farmer who has a goat, a cabbage, and a wolf. If the farmer leaves the goat with the cabbage, the goat will eat the cabbage. If the farmer leaves the wolf alone with the goat, the wolf will kill the goat. How can the farmer move all his belongings to the other side of the river?
Jug Problem:
You are given two jugs, a 4-gallon one and a 3-gallon one. There are no measuring markers on the jugs. A tap can be used to fill the jugs with water. How can you get 2 gallons of water in the 4-gallon jug?
The branch and bound method is used when we can evaluate the cost of visiting each node using a utility function. At each step, we choose the node with the lowest cost to proceed further. Branch-and-bound algorithms are implemented using a priority queue. In branch and bound, we traverse the nodes in a breadth-first manner.
A* is an extension of the branch and bound approach. In A*, we select the path with the shortest length from the start to the goal. The total length is estimated as the length traversed so far plus a heuristic estimate of the remaining distance from the goal.
Branch-and-bound will always find an optimal solution, which is the shortest path. A* will also find an optimal solution if the heuristic is accurate. Choosing a good heuristic is the most crucial aspect of the A* algorithm.
Given N items where each item has some weight and profit associated with it and also given a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put the items into the bag such that the sum of profits associated with them is the maximum possible.
Note: The constraint here is we can either put an item completely into the bag or cannot put it at all [It is not possible to put a part of an item into the bag]./* A Naive recursive implementation of 0-1 Knapsack problem */ #include <bits/stdc++.h> using namespace std; // A utility function that returns // maximum of two integers int max(int a, int b) { return (a > b) ? a : b; } // Returns the maximum value that // can be put in a knapsack of capacity W int knapSack(int W, int wt[], int val[], int n) { // Base Case if (n == 0 || W == 0) return 0; // If weight of the nth item is more // than Knapsack capacity W, then // this item cannot be included // in the optimal solution if (wt[n - 1] > W) return knapSack(W, wt, val, n - 1); // Return the maximum of two cases: // (1) nth item included // (2) not included else return max( val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), knapSack(W, wt, val, n - 1)); } // Driver code int main() { int profit[] = { 60, 100, 120 }; int weight[] = { 10, 20, 30 }; int W = 50; int n = sizeof(profit) / sizeof(profit[0]); cout << knapSack(W, weight, profit, n); return 0; }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.
// C++ program to solve fractional Knapsack Problem #include <bits/stdc++.h> using namespace std; // Structure for an item which stores weight and // corresponding value of Item struct Item { int profit, weight; // Constructor Item(int profit, int weight) { this->profit = profit; this->weight = weight; } }; // Comparison function to sort Item // according to profit/weight ratio static bool cmp(struct Item a, struct Item b) { double r1 = (double)a.profit / (double)a.weight; double r2 = (double)b.profit / (double)b.weight; return r1 > r2; } // Main greedy function to solve problem double fractionalKnapsack(int W, struct Item arr[], int N) { // Sorting Item on basis of ratio sort(arr, arr + N, cmp); double finalvalue = 0.0; // Looping through all items for (int i = 0; i < N; i++) { // If adding Item won't overflow, // add it completely if (arr[i].weight <= W) { W -= arr[i].weight; finalvalue += arr[i].profit; } // If we can't add current Item, // add fractional part of it else { finalvalue += arr[i].profit * ((double)W / (double)arr[i].weight); break; } } // Returning final value return finalvalue; } // Driver code int main() { int W = 50; Item arr[] = { { 60, 10 }, { 100, 20 }, { 120, 30 } }; int N = sizeof(arr) / sizeof(arr[0]); // Function call cout << fractionalKnapsack(W, arr, N); return 0; }Given the dimension of a sequence of matrices in an array arr[], where the dimension of the ith matrix is (arr[i-1] * arr[i]), the task is to find the most efficient way to multiply these matrices together such that the total number of element multiplications is minimum.
#include <bits/stdc++.h> using namespace std; // Matrix Ai has dimension p[i-1] x p[i] // for i = 1 . . . n int MatrixChainOrder(int p[], int i, int j) { if (i == j) return 0; int k; int mini = INT_MAX; int count; // Place parenthesis at different places // between first and last matrix, // recursively calculate count of multiplications // for each parenthesis placement // and return the minimum count for (k = i; k < j; k++) { count = MatrixChainOrder(p, i, k) + MatrixChainOrder(p, k + 1, j) + p[i - 1] * p[k] * p[j]; mini = min(count, mini); } // Return minimum count return mini; } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 3 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call cout << "Minimum number of multiplications is " << MatrixChainOrder(arr, 1, N - 1); return 0; }A Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a data structure used for efficiently performing two primary operations on an array of values: updating a value and calculating the prefix sum (cumulative sum) of a range of values. It was developed by Peter Fenwick in 1994 and is particularly useful when you need to frequently update elements in an array and calculate cumulative sums or ranges.
// C++ code to demonstrate operations of Binary Index Tree #include <iostream> using namespace std; /* n --> No. of elements present in input array. BITree[0..n] --> Array that represents Binary Indexed Tree. arr[0..n-1] --> Input array for which prefix sum is evaluated. */ // Returns sum of arr[0..index]. This function assumes // that the array is preprocessed and partial sums of // array elements are stored in BITree[]. int getSum(int BITree[], int index) { int sum = 0; // Initialize result // index in BITree[] is 1 more than the index in arr[] index = index + 1; // Traverse ancestors of BITree[index] while (index>0) { // Add current element of BITree to sum sum += BITree[index]; // Move index to parent node in getSum View index -= index & (-index); } return sum; } // Updates a node in Binary Index Tree (BITree) at given index // in BITree. The given value 'val' is added to BITree[i] and // all of its ancestors in tree. void updateBIT(int BITree[], int n, int index, int val) { // index in BITree[] is 1 more than the index in arr[] index = index + 1; // Traverse all ancestors and add 'val' while (index <= n) { // Add 'val' to current node of BI Tree BITree[index] += val; // Update index to that of parent in update View index += index & (-index); } } // Constructs and returns a Binary Indexed Tree for given // array of size n. int *constructBITree(int arr[], int n) { // Create and initialize BITree[] as 0 int *BITree = new int[n+1]; for (int i=1; i<=n; i++) BITree[i] = 0; // Store the actual values in BITree[] using update() for (int i=0; i<n; i++) updateBIT(BITree, n, i, arr[i]); // Uncomment below lines to see contents of BITree[] //for (int i=1; i<=n; i++) // cout << BITree[i] << " "; return BITree; } // Driver program to test above functions int main() { int freq[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9}; int n = sizeof(freq)/sizeof(freq[0]); int *BITree = constructBITree(freq, n); cout << "Sum of elements in arr[0..5] is " << getSum(BITree, 5); // Let use test the update operation freq[3] += 6; updateBIT(BITree, n, 3, 6); //Update BIT for above change in arr[] cout << "\nSum of elements in arr[0..5] after update is " << getSum(BITree, 5); return 0; }The Bellman-Ford algorithm is a single-source shortest path algorithm used to find the shortest paths from a source vertex to all other vertices in a weighted, directed graph, including graphs with negative edge weights. It was developed by Richard Bellman and Lester Ford in the 1950s. This algorithm is more versatile than Dijkstra's algorithm since it can handle graphs with negative edge weights and detect the presence of negative cycles.
// A C++ program for Bellman-Ford's single source // shortest path algorithm. #include <bits/stdc++.h> using namespace std; // a structure to represent a weighted edge in graph struct Edge { int src, dest, weight; }; // a structure to represent a connected, directed and // weighted graph struct Graph { // V-> Number of vertices, E-> Number of edges int V, E; // graph is represented as an array of edges. struct Edge* edge; }; // Creates a graph with V vertices and E edges struct Graph* createGraph(int V, int E) { struct Graph* graph = new Graph; graph->V = V; graph->E = E; graph->edge = new Edge[E]; return graph; } // A utility function used to print the solution void printArr(int dist[], int n) { printf("Vertex Distance from Source\n"); for (int i = 0; i < n; ++i) printf("%d \t\t %d\n", i, dist[i]); } // The main function that finds shortest distances from src // to all other vertices using Bellman-Ford algorithm. The // function also detects negative weight cycle void BellmanFord(struct Graph* graph, int src) { int V = graph->V; int E = graph->E; int dist[V]; // Step 1: Initialize distances from src to all other // vertices as INFINITE for (int i = 0; i < V; i++) dist[i] = INT_MAX; dist[src] = 0; // Step 2: Relax all edges |V| - 1 times. A simple // shortest path from src to any other vertex can have // at-most |V| - 1 edges for (int i = 1; i <= V - 1; i++) { for (int j = 0; j < E; j++) { int u = graph->edge[j].src; int v = graph->edge[j].dest; int weight = graph->edge[j].weight; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } // Step 3: check for negative-weight cycles. The above // step guarantees shortest distances if graph doesn't // contain negative weight cycle. If we get a shorter // path, then there is a cycle. for (int i = 0; i < E; i++) { int u = graph->edge[i].src; int v = graph->edge[i].dest; int weight = graph->edge[i].weight; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) { printf("Graph contains negative weight cycle"); return; // If negative cycle is detected, simply // return } } printArr(dist, V); return; } // Driver's code int main() { /* Let us create the graph given in above example */ int V = 5; // Number of vertices in graph int E = 8; // Number of edges in graph struct Graph* graph = createGraph(V, E); // add edge 0-1 (or A-B in above figure) graph->edge[0].src = 0; graph->edge[0].dest = 1; graph->edge[0].weight = -1; // add edge 0-2 (or A-C in above figure) graph->edge[1].src = 0; graph->edge[1].dest = 2; graph->edge[1].weight = 4; // add edge 1-2 (or B-C in above figure) graph->edge[2].src = 1; graph->edge[2].dest = 2; graph->edge[2].weight = 3; // add edge 1-3 (or B-D in above figure) graph->edge[3].src = 1; graph->edge[3].dest = 3; graph->edge[3].weight = 2; // add edge 1-4 (or B-E in above figure) graph->edge[4].src = 1; graph->edge[4].dest = 4; graph->edge[4].weight = 2; // add edge 3-2 (or D-C in above figure) graph->edge[5].src = 3; graph->edge[5].dest = 2; graph->edge[5].weight = 5; // add edge 3-1 (or D-B in above figure) graph->edge[6].src = 3; graph->edge[6].dest = 1; graph->edge[6].weight = 1; // add edge 4-3 (or E-D in above figure) graph->edge[7].src = 4; graph->edge[7].dest = 3; graph->edge[7].weight = -3; // Function call BellmanFord(graph, 0); return 0; }Kruskal's algorithm is a popular greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, undirected graph. A Minimum Spanning Tree is a subset of the edges of a graph that connects all vertices together with the minimum possible total edge weight, while ensuring that no cycles are formed. Kruskal's algorithm was developed by Joseph Kruskal in the 1950s.
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // DSU data structure // path compression + rank by union class DSU { int* parent; int* rank; public: DSU(int n) { parent = new int[n]; rank = new int[n]; for (int i = 0; i < n; i++) { parent[i] = -1; rank[i] = 1; } } // Find function int find(int i) { if (parent[i] == -1) return i; return parent[i] = find(parent[i]); } // Union function void unite(int x, int y) { int s1 = find(x); int s2 = find(y); if (s1 != s2) { if (rank[s1] < rank[s2]) { parent[s1] = s2; } else if (rank[s1] > rank[s2]) { parent[s2] = s1; } else { parent[s2] = s1; rank[s1] += 1; } } } }; class Graph { vector<vector<int> > edgelist; int V; public: Graph(int V) { this->V = V; } // Function to add edge in a graph void addEdge(int x, int y, int w) { edgelist.push_back({ w, x, y }); } void kruskals_mst() { // Sort all edges sort(edgelist.begin(), edgelist.end()); // Initialize the DSU DSU s(V); int ans = 0; cout << "Following are the edges in the " "constructed MST" << endl; for (auto edge : edgelist) { int w = edge[0]; int x = edge[1]; int y = edge[2]; // Take this edge in MST if it does // not forms a cycle if (s.find(x) != s.find(y)) { s.unite(x, y); ans += w; cout << x << " -- " << y << " == " << w << endl; } } cout << "Minimum Cost Spanning Tree: " << ans; } }; // Driver code int main() { Graph g(4); g.addEdge(0, 1, 10); g.addEdge(1, 3, 15); g.addEdge(2, 3, 4); g.addEdge(2, 0, 6); g.addEdge(0, 3, 5); // Function call g.kruskals_mst(); return 0; }The Knuth-Morris-Pratt (KMP) algorithm is a string searching algorithm used to find all occurrences of a pattern string within a longer text string efficiently. It was developed by Donald Knuth, Vaughan Pratt, and James H. Morris in 1977. The KMP algorithm is known for its linear time complexity, making it highly efficient for large text and pattern strings.
// C++ program for implementation of KMP pattern searching // algorithm #include <bits/stdc++.h> void computeLPSArray(char* pat, int M, int* lps); // Prints occurrences of txt[] in pat[] void KMPSearch(char* pat, char* txt) { int M = strlen(pat); int N = strlen(txt); // create lps[] that will hold the longest prefix suffix // values for pattern int lps[M]; // Preprocess the pattern (calculate lps[] array) computeLPSArray(pat, M, lps); int i = 0; // index for txt[] int j = 0; // index for pat[] while ((N - i) >= (M - j)) { if (pat[j] == txt[i]) { j++; i++; } if (j == M) { printf("Found pattern at index %d ", i - j); j = lps[j - 1]; } // mismatch after j matches else if (i < N && pat[j] != txt[i]) { // Do not match lps[0..lps[j-1]] characters, // they will match anyway if (j != 0) j = lps[j - 1]; else i = i + 1; } } } // Fills lps[] for given pattern pat[0..M-1] void computeLPSArray(char* pat, int M, int* lps) { // length of the previous longest prefix suffix int len = 0; lps[0] = 0; // lps[0] is always 0 // the loop calculates lps[i] for i = 1 to M-1 int i = 1; while (i < M) { if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } else // (pat[i] != pat[len]) { // This is tricky. Consider the example. // AAACAAAA and i = 7. The idea is similar // to search step. if (len != 0) { len = lps[len - 1]; // Also, note that we do not increment // i here } else // if (len == 0) { lps[i] = 0; i++; } } } } // Driver code int main() { char txt[] = "ABABDABACDABABCABAB"; char pat[] = "ABABCABAB"; KMPSearch(pat, txt); return 0; }The Boyer-Moore algorithm is a powerful string searching algorithm that efficiently finds occurrences of a pattern string within a longer text string. It was developed by Robert S. Boyer and J Strother Moore in 1977. The Boyer-Moore algorithm is known for its practical speed and effectiveness in real-world applications.
/* C++ Program for Bad Character Heuristic of Boyer Moore String Matching Algorithm */ #include <bits/stdc++.h> using namespace std; # define NO_OF_CHARS 256 // The preprocessing function for Boyer Moore's // bad character heuristic void badCharHeuristic( string str, int size, int badchar[NO_OF_CHARS]) { int i; // Initialize all occurrences as -1 for (i = 0; i < NO_OF_CHARS; i++) badchar[i] = -1; // Fill the actual value of last occurrence // of a character for (i = 0; i < size; i++) badchar[(int) str[i]] = i; } /* A pattern searching function that uses Bad Character Heuristic of Boyer Moore Algorithm */ void search( string txt, string pat) { int m = pat.size(); int n = txt.size(); int badchar[NO_OF_CHARS]; /* Fill the bad character array by calling the preprocessing function badCharHeuristic() for given pattern */ badCharHeuristic(pat, m, badchar); int s = 0; // s is shift of the pattern with // respect to text while(s <= (n - m)) { int j = m - 1; /* Keep reducing index j of pattern while characters of pattern and text are matching at this shift s */ while(j >= 0 && pat[j] == txt[s + j]) j--; /* If the pattern is present at current shift, then index j will become -1 after the above loop */ if (j < 0) { cout << "pattern occurs at shift = " << s << endl; /* Shift the pattern so that the next character in text aligns with the last occurrence of it in pattern. The condition s+m < n is necessary for the case when pattern occurs at the end of text */ s += (s + m < n)? m-badchar[txt[s + m]] : 1; } else /* Shift the pattern so that the bad character in text aligns with the last occurrence of it in pattern. The max function is used to make sure that we get a positive shift. We may get a negative shift if the last occurrence of bad character in pattern is on the right side of the current character. */ s += max(1, j - badchar[txt[s + j]]); } } /* Driver code */ int main() { string txt= "ABAAABCD"; string pat = "ABC"; search(txt, pat); return 0; }It seems like you're asking about the "Least Common Subsequence" (LCS) problem. The LCS problem is a classic algorithmic problem in computer science, and it is often confused with the "Longest Common Subsequence" problem (which is more common). The Least Common Subsequence problem is slightly different.
// A Naive recursive implementation of LCS problem #include <bits/stdc++.h> using namespace std; // Returns length of LCS for X[0..m-1], Y[0..n-1] int lcs(string X, string Y, int m, int n) { if (m == 0 || n == 0) return 0; if (X[m - 1] == Y[n - 1]) return 1 + lcs(X, Y, m - 1, n - 1); else return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n)); } // Driver code int main() { string S1 = "AGGTAB"; string S2 = "GXTXAYB"; int m = S1.size(); int n = S2.size(); cout << "Length of LCS is " << lcs(S1, S2, m, n); return 0; }