4) Which is a more efficient way to determine the optimal number of multiplications in a matrix-chain multiplication problem: en
umerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running RECURSIVE-MATRIX-CHAIN? Justify your answer
1 answer:
Answer:
Running RECURSIVE-MATRIX-CHAIN is asymptotically more efficient than enumerating all the ways of parenthesizing the product and computing the number of multiplications of each.
the running time complexity of enumerating all the ways of parenthesizing the product is n*P(n) while in case of RECURSIVE-MATRIX-CHAIN, all the internal nodes are run on all the internal nodes of the tree and it will also create overhead.
Explanation:
You might be interested in
Using the knowledge in computational language in C++ it is possible to write a code that cryptarithm is a mathematical puzzle where the goal is to find the correspondence between letters and digits
<h3>Writting the code:</h3><em>#include <bits/stdc++.h></em>
<em>using namespace std;</em>
<em>// chracter to digit mapping, and the inverse</em>
<em>// (if you want better performance: use array instead of unordered_map)</em>
<em>unordered_map<char, int> c2i;</em>
<em>unordered_map<int, char> i2c;</em>
<em>int ans = 0;</em>
<em>// limit: length of result</em>
<em>int limit = 0;</em>
<em>// digit: index of digit in a word, widx: index of a word in word list, sum: summation of all word[digit] </em>
<em>bool helper(vector<string>& words, string& result, int digit, int widx, int sum) { </em>
<em> if (digit == limit) {</em>
<em> ans += (sum == 0);</em>
<em> return sum == 0;</em>
<em> }</em>
<em> // if summation at digit position complete, validate it with result[digit].</em>
<em> if (widx == words.size()) {</em>
<em> if (c2i.count(result[digit]) == 0 && i2c.count(sum%10) == 0) {</em>
<em> if (sum%10 == 0 && digit+1 == limit) // Avoid leading zero in result</em>
<em> return false;</em>
<em> c2i[result[digit]] = sum % 10;</em>
<em> i2c[sum%10] = result[digit];</em>
<em> bool tmp = helper(words, result, digit+1, 0, sum/10);</em>
<em> c2i.erase(result[digit]);</em>
<em> i2c.erase(sum%10);</em>
<em> ans += tmp;</em>
<em> return tmp;</em>
<em> } else if (c2i.count(result[digit]) && c2i[result[digit]] == sum % 10){</em>
<em> if (digit + 1 == limit && 0 == c2i[result[digit]]) {</em>
<em> return false;</em>
<em> }</em>
<em> return helper(words, result, digit+1, 0, sum/10);</em>
<em> } else {</em>
<em> return false;</em>
<em> }</em>
<em> }</em>
<em> // if word[widx] length less than digit, ignore and go to next word</em>
<em> if (digit >= words[widx].length()) {</em>
<em> return helper(words, result, digit, widx+1, sum);</em>
<em> }</em>
<em> // if word[widx][digit] already mapped to a value</em>
<em> if (c2i.count(words[widx][digit])) {</em>
<em> if (digit+1 == words[widx].length() && words[widx].length() > 1 && c2i[words[widx][digit]] == 0) </em>
<em> return false;</em>
<em> return helper(words, result, digit, widx+1, sum+c2i[words[widx][digit]]);</em>
<em> }</em>
<em> // if word[widx][digit] not mapped to a value yet</em>
<em> for (int i = 0; i < 10; i++) {</em>
<em> if (digit+1 == words[widx].length() && i == 0 && words[widx].length() > 1) continue;</em>
<em> if (i2c.count(i)) continue;</em>
<em> c2i[words[widx][digit]] = i;</em>
<em> i2c[i] = words[widx][digit];</em>
<em> bool tmp = helper(words, result, digit, widx+1, sum+i);</em>
<em> c2i.erase(words[widx][digit]);</em>
<em> i2c.erase(i);</em>
<em> }</em>
<em> return false;</em>
<em>}</em>
<em>void isSolvable(vector<string>& words, string result) {</em>
<em> limit = result.length();</em>
<em> for (auto &w: words) </em>
<em> if (w.length() > limit) </em>
<em> return;</em>
<em> for (auto&w:words) </em>
<em> reverse(w.begin(), w.end());</em>
<em> reverse(result.begin(), result.end());</em>
<em> int aa = helper(words, result, 0, 0, 0);</em>
<em>}</em>
<em />
<em>int main()</em>
<em>{</em>
<em> ans = 0;</em>
<em> vector<string> words={"GREEN" , "BLUE"} ;</em>
<em> string result = "BLACK";</em>
<em> isSolvable(words, result);</em>
<em> cout << ans << "\n";</em>
<em> return 0;</em>
<em>}</em>
See more about C++ code at brainly.com/question/19705654
#SPJ1
