feat: add Strassen's Matrix Multiplication (TheAlgorithms#2413)

* Feat: Add Strassen's matrix multiplication * updating DIRECTORY.md * Fix cpp lint error * updating DIRECTORY.md * clang-format and clang-tidy fixes for 02439b5 * Fix windows error * Add namespaces * updating DIRECTORY.md * Proper documentation * Reduce the matrix size. * updating DIRECTORY.md * clang-format and clang-tidy fixes for 0545555 Co-authored-by: toastedbreadandomelette <toastedbreadandomelette@gmail.com> Co-authored-by: github-actions[bot] <github-actions@users.noreply.github.com> Co-authored-by: David Leal <halfpacho@gmail.com>
ShuN6211 · Jan 24, 2023 · 5b23872 · 5b23872
1 parent a6a9d8e
commit 5b23872
Show file tree

Hide file tree

Showing 6 changed files with 764 additions and 260 deletions.
diff --git a/DIRECTORY.md b/DIRECTORY.md
@@ -82,6 +82,7 @@
 
 ## Divide And Conquer
   * [Karatsuba Algorithm For Fast Multiplication](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/divide_and_conquer/karatsuba_algorithm_for_fast_multiplication.cpp)
+  * [Strassen Matrix Multiplication](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/divide_and_conquer/strassen_matrix_multiplication.cpp)
 
 ## Dynamic Programming
   * [0 1 Knapsack](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/dynamic_programming/0_1_knapsack.cpp)
@@ -110,6 +111,7 @@
   * [Partition Problem](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/dynamic_programming/partition_problem.cpp)
   * [Searching Of Element In Dynamic Array](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/dynamic_programming/searching_of_element_in_dynamic_array.cpp)
   * [Shortest Common Supersequence](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/dynamic_programming/shortest_common_supersequence.cpp)
+  * [Subset Sum](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/dynamic_programming/subset_sum.cpp)
   * [Tree Height](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/dynamic_programming/tree_height.cpp)
   * [Word Break](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/dynamic_programming/word_break.cpp)
 
@@ -146,6 +148,7 @@
   * [Spirograph](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/graphics/spirograph.cpp)
 
 ## Greedy Algorithms
+  * [Boruvkas Minimum Spanning Tree](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/greedy_algorithms/boruvkas_minimum_spanning_tree.cpp)
   * [Dijkstra](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/greedy_algorithms/dijkstra.cpp)
   * [Huffman](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/greedy_algorithms/huffman.cpp)
   * [Jumpgame](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/greedy_algorithms/jumpgame.cpp)
@@ -171,6 +174,7 @@
   * [Vector Ops](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/machine_learning/vector_ops.hpp)
 
 ## Math
+  * [Aliquot Sum](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/aliquot_sum.cpp)
   * [Approximate Pi](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/approximate_pi.cpp)
   * [Area](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/area.cpp)
   * [Armstrong Number](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/math/armstrong_number.cpp)

diff --git a/bit_manipulation/travelling_salesman_using_bit_manipulation.cpp b/bit_manipulation/travelling_salesman_using_bit_manipulation.cpp
@@ -5,24 +5,26 @@
  * (https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/)
  *
  * @details
- * Given the distance/cost(as and adjacency matrix) between each city/node to the other city/node ,
- * the problem is to find the shortest possible route that visits every city exactly once
- * and returns to the starting point or we can say the minimum cost of whole tour.
+ * Given the distance/cost(as and adjacency matrix) between each city/node to
+ * the other city/node , the problem is to find the shortest possible route that
+ * visits every city exactly once and returns to the starting point or we can
+ * say the minimum cost of whole tour.
  *
  * Explanation:
- *  INPUT -> You are given with a adjacency matrix A = {} which contains the distance between two cities/node.
+ *  INPUT -> You are given with a adjacency matrix A = {} which contains the
+ * distance between two cities/node.
  *
  *  OUTPUT ->  Minimum cost of whole tour from starting point
  *
  * Worst Case Time Complexity: O(n^2 * 2^n)
  * Space complexity: O(n)
  * @author [Utkarsh Yadav](https://github.com/Rytnix)
  */
-#include <algorithm>   /// for std::min
+#include <algorithm>  /// for std::min
 #include <cassert>    /// for assert
-#include <iostream>  /// for IO operations
-#include <vector>   /// for std::vector 
-#include <limits>  /// for limits of integral types
+#include <iostream>   /// for IO operations
+#include <limits>     /// for limits of integral types
+#include <vector>     /// for std::vector
 
 /**
  * @namespace bit_manipulation
@@ -42,40 +44,53 @@ namespace travelling_salesman_using_bit_manipulation {
  * @param setOfCitites represents the city in bit form.\
  * @param city is taken to track the current city movement.
  * @param n is the no of citys .
- * @param dp vector is used to keep a record of state to avoid the recomputation.
- * @returns minimum cost of traversing whole nodes/cities from starting point back to starting point
+ * @param dp vector is used to keep a record of state to avoid the
+ * recomputation.
+ * @returns minimum cost of traversing whole nodes/cities from starting point
+ * back to starting point
  */
-std::uint64_t travelling_salesman_using_bit_manipulation(std::vector<std::vector<uint32_t>> dist,  // dist is the adjacency matrix containing the distance.
-        // setOfCities as a bit represent the cities/nodes. Ex: if setOfCities = 2 => 0010(in binary)
-        // means representing the city/node B if city/nodes are represented as D->C->B->A.
-        std::uint64_t setOfCities,
-        std::uint64_t city, // city is taken to track our current city/node movement,where we are currently.
-        std::uint64_t n, // n is the no of cities we have.
-        std::vector<std::vector<uint32_t>> &dp) //dp is taken to memorize the state to avoid recomputition
+std::uint64_t travelling_salesman_using_bit_manipulation(
+    std::vector<std::vector<uint32_t>>
+        dist,  // dist is the adjacency matrix containing the distance.
+               // setOfCities as a bit represent the cities/nodes. Ex: if
+               // setOfCities = 2 => 0010(in binary) means representing the
+               // city/node B if city/nodes are represented as D->C->B->A.
+    std::uint64_t setOfCities,
+    std::uint64_t city,  // city is taken to track our current city/node
+                         // movement,where we are currently.
+    std::uint64_t n,     // n is the no of cities we have.
+    std::vector<std::vector<uint32_t>>
+        &dp)  // dp is taken to memorize the state to avoid recomputition
 {
-    //base case;
-    if (setOfCities == (1 << n) - 1) // we have covered all the cities
-        return dist[city][0]; //return the cost from the current city to the original city.
+    // base case;
+    if (setOfCities == (1 << n) - 1) {  // we have covered all the cities
+        return dist[city][0];  // return the cost from the current city to the
+                               // original city.
+    }
 
-    if (dp[setOfCities][city] != -1)
+    if (dp[setOfCities][city] != -1) {
         return dp[setOfCities][city];
-    //otherwise try all possible options
-    uint64_t ans = 2147483647 ;
+    }
+    // otherwise try all possible options
+    uint64_t ans = 2147483647;
     for (int choice = 0; choice < n; choice++) {
-        //check if the city is visited or not.
-        if ((setOfCities & (1 << choice)) == 0 ) { // this means that this perticular city is not visited.
-            std::uint64_t subProb = dist[city][choice] + travelling_salesman_using_bit_manipulation(dist, setOfCities | (1 << choice), choice, n, dp);
-            // Here we are doing a recursive call to tsp with the updated set of city/node
-            // and choice which tells that where we are currently.
+        // check if the city is visited or not.
+        if ((setOfCities & (1 << choice)) ==
+            0) {  // this means that this perticular city is not visited.
+            std::uint64_t subProb =
+                dist[city][choice] +
+                travelling_salesman_using_bit_manipulation(
+                    dist, setOfCities | (1 << choice), choice, n, dp);
+            // Here we are doing a recursive call to tsp with the updated set of
+            // city/node and choice which tells that where we are currently.
             ans = std::min(ans, subProb);
         }
-
     }
     dp[setOfCities][city] = ans;
     return ans;
 }
-} // namespace travelling_salesman_using_bit_manipulation
-} // namespace bit_manipulation
+}  // namespace travelling_salesman_using_bit_manipulation
+}  // namespace bit_manipulation
 
 /**
  * @brief Self-test implementations
@@ -84,29 +99,36 @@ std::uint64_t travelling_salesman_using_bit_manipulation(std::vector<std::vector
 static void test() {
     // 1st test-case
     std::vector<std::vector<uint32_t>> dist = {
-        {0, 20, 42, 35}, {20, 0, 30, 34}, {42, 30, 0, 12}, {35, 34, 12, 0}
-    };
+        {0, 20, 42, 35}, {20, 0, 30, 34}, {42, 30, 0, 12}, {35, 34, 12, 0}};
     uint32_t V = dist.size();
     std::vector<std::vector<uint32_t>> dp(1 << V, std::vector<uint32_t>(V, -1));
-    assert(bit_manipulation::travelling_salesman_using_bit_manipulation::travelling_salesman_using_bit_manipulation(dist, 1, 0, V, dp) == 97);
-    std::cout << "1st test-case: passed!" << "\n";
+    assert(bit_manipulation::travelling_salesman_using_bit_manipulation::
+               travelling_salesman_using_bit_manipulation(dist, 1, 0, V, dp) ==
+           97);
+    std::cout << "1st test-case: passed!"
+              << "\n";
 
     // 2nd test-case
     dist = {{0, 5, 10, 15}, {5, 0, 20, 30}, {10, 20, 0, 35}, {15, 30, 35, 0}};
     V = dist.size();
-    std::vector<std::vector<uint32_t>> dp1(1 << V, std::vector<uint32_t>(V, -1));
-    assert(bit_manipulation::travelling_salesman_using_bit_manipulation::travelling_salesman_using_bit_manipulation(dist, 1, 0, V, dp1) == 75);
-    std::cout << "2nd test-case: passed!" << "\n";
+    std::vector<std::vector<uint32_t>> dp1(1 << V,
+                                           std::vector<uint32_t>(V, -1));
+    assert(bit_manipulation::travelling_salesman_using_bit_manipulation::
+               travelling_salesman_using_bit_manipulation(dist, 1, 0, V, dp1) ==
+           75);
+    std::cout << "2nd test-case: passed!"
+              << "\n";
     // 3rd test-case
-    dist = {
-        {0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}
-    };
+    dist = {{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}};
     V = dist.size();
-    std::vector<std::vector<uint32_t>> dp2(1 << V, std::vector<uint32_t>(V, -1));
-    assert(bit_manipulation::travelling_salesman_using_bit_manipulation::travelling_salesman_using_bit_manipulation(dist, 1, 0, V, dp2) == 80);
-
-    std::cout << "3rd test-case: passed!" << "\n";
+    std::vector<std::vector<uint32_t>> dp2(1 << V,
+                                           std::vector<uint32_t>(V, -1));
+    assert(bit_manipulation::travelling_salesman_using_bit_manipulation::
+               travelling_salesman_using_bit_manipulation(dist, 1, 0, V, dp2) ==
+           80);
 
+    std::cout << "3rd test-case: passed!"
+              << "\n";
 }
 
 /**