6
$\begingroup$

The following are questions about using dynamic programming for matrix chain multiplication. Pseudocode can be found in the Wikipedia article on matrix chain multiplication.

1) Why is the time complexity for trying all bracket permutations $\mathcal{O}(2^n)$, where $n$ is the number of matrices??

2) Why are there $\frac{n^2}{2}$ unique subsequences? (This question is refering to memoization where all unique subproblems are stored. A rephrasing of this question would be: Why are there $\frac{n^2}{2}$ unique subproblems to be stored?)

3) Why does using memoization reduce the time to $O(n^3)$?

I don't have made any progress on the above questions, therefore there is no work for me to show.

  • 0
    Why the down vote? This is a legitimate question - it hasn't been answered before, it explains the lack of self work and is on-topic.2012-08-27
  • 0
    I did not downvote, but I presume it got downvoted because it seems you haven't given it much thought. E.g. for question 4) - you can't multiply matrices that don't share a dimension AT ALL - so an algorithm to compute the most efficient multiplication routine cannot work if the matrix dimensions don't match up.2012-08-27
  • 2
    @us2012 That was stupid of me. Sorry, I haven't worked with linear algebra for a while, resulting in me asking stupid questions like the one above. I removed it. Thanks for *politely* pointing it out!2012-08-27
  • 1
    It's on-topic IMO (+1)2012-08-27
  • 0
    Asking a question about a particular construction that "can be found" somewhere in a Wikipedia article which you don't even bother to link to (and which may be completely rewritten by the time a future reader attempts to make sense of your question), is close to earning this a downvote from me.2012-08-27
  • 0
    @HenningMakholm I disagree. This question is completely independent of the Wikipedia page. The question can be answered without any reference to Wikipedia. The only reason I mentioned Wikipedia is simply to help those without familiarity of the algorithm. The questions assumes that people who are attempting to answer already know the algorithm.2012-08-27
  • 0
    @FarhadYusufali: Your only specification about _which_ algorithm your question is about is by reference to the Wikipedia article (implicitly, I assume, your specification is "whichever algorithm the Wikipedia article presented at the time I wrote this").2012-08-27
  • 0
    @HenningMakholm That *isn't* my only specification. My question specifically states: "The following are questions about using dynamic programming for matrix chain multiplication. ". This informs the reader exactly *which* algorithm I am talking about.2012-08-27
  • 0
    @FarhadYusufali: "Dynamic programming" is not an algorithm, it is a vague idea that can be used for developing algorithms in general. Are you claiming claim that there is exactly one possible way to apply this general idea to the specific problem of matrix multiplication? If you understand the idea and the problem well enough to be sure of that, why do you need to ask anything about it?2012-08-28

1 Answers 1