DP: What's a subproblem space? Why have varying indices for a subproblem?

  • Thread starter Thread starter CGandC
  • Start date Start date
  • Tags Tags
    Indices Space
AI Thread Summary
In dynamic programming, the space of subproblems refers to the set of smaller problems that can be solved to address a larger problem, often defined mathematically by the indices that represent the problem's boundaries. Varying indices for subproblems is crucial because it allows for flexibility in defining the range of elements being considered, which is essential for problems like matrix-chain multiplication. The distinction between subproblem forms, such as A_1 A_2 ... A_j and A_{k+1} A_{k+2} ... A_j, highlights that the latter requires two indices to define its range, while the former only needs one, emphasizing the need for both left and right indices in certain algorithms. This difference is significant in computer science, where memory and processing costs can arise from how subproblems are structured and accessed. Understanding these distinctions is key to effectively applying dynamic programming techniques.
CGandC
Messages
326
Reaction score
34
In dynamic programming:
1. what is the definition of the space of subproblems? does it have a mathematical definition?

2. why is it necessary to have an arbitrary index for the subproblem to vary?

To elaborate on question 2, I've taken the following paragraph from chapter 15.3 in CLRS:Conversely, suppose that we had tried to constrain our subproblem space for
matrix-chain multiplication to matrix products of the form ## A_1A_2... A_j ## . As before,
an optimal parenthesization must split this product between ## A_k ## and ## A_{k+1} ## for some
## 1 \leq k < j ##. Unless we could guarantee that ## k ## always equals ## j - 1 ##, we would find that we had subproblems of the form ## A_1 A_2 ... A_k ## and ## A_{k+1} A_{k+2} ... A_j ##, and that the latter subproblem is not of the form ## A_1 A_2 ... A_j ## . For this problem, we needed to allow our subproblems to vary at “both ends,” that is, to allow both ##i## and ##j## to
vary in the subproblem ## A_i A_{i+1} ... A_j ## .
2.a. I don't understand why the subproblem ## A_{k+1} A_{k+2} ... A_j ## is not of the form ## A_1 A_2 ... A_j ## ( ## k+1 ## is considered to be the first index in the problem of finding the optimal parenthization for ## A_{k+1} A_{k+2} ... A_j ## ) whilst ## A_1 A_2 ... A_k ## is considered a correct form ?
2.b. is there some sort of universal instantiation I'm missing in-terms of logic? what do variable indexes have to do with the issue In question 2.a. ?
( I'm think the issue relates to the fact that when we prove a problem has a substructure, we need to prove it for arbitrary indexes, but I'm unable to see the relation between this proof and why ## A_{k+1} A_{k+2} ... A_j ## is not of the form ## A_1 A_2 ... A_j ## if we consider ##k+1## as the first index in the subproblem ## A_{k+1} A_{k+2} ... A_j ## )
 
Technology news on Phys.org
I think there is a distinction between "apply this algorithm to the first k elements of this list" and "apply this algorithm to elements k+1 to j of this list". The first only requires passing and tracking one index (the right index) but the second requires passing and tracking both left and right indices.

I think you aren't allowed to conflate these by creating a new list consisting only of elements k+1 to j of the original list and applying the algorithm to the first j-k elements of this new list. The exact semantics of "create a new list" will vary, and may have costs (in terms of memory and processor cycles) associated with them which are real in computer science but non-existent in abstract mathematics.
 
So "## A_1 A_2 \cdots A_j ##" stands for a contiguous sequence of elements in the matrix chain that start from ##A_1##, a fixed element, which implies that it is enough for one number, the value of ## j##, to completely specify those elements given the matrix chain?
and in this sense, "## A_{k+1} A_{k+2} \cdots A_j ##" is not of the form of "## A_1 A_2 \cdots A_j ##", since two numbers are needed to specify them?
 
CGandC said:
So "## A_1 A_2 \cdots A_j ##" stands for a contiguous sequence of elements in the matrix chain that start from ##A_1##, a fixed element, which implies that it is enough for one number, the value of ## j##, to completely specify those elements given the matrix chain?
and in this sense, "## A_{k+1} A_{k+2} \cdots A_j ##" is not of the form of "## A_1 A_2 \cdots A_j ##", since two numbers are needed to specify them?
Right
 
Ok, I understand now, thanks for the help!
 
Thread 'Is this public key encryption?'
I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
I tried a web search "the loss of programming ", and found an article saying that all aspects of writing, developing, and testing software programs will one day all be handled through artificial intelligence. One must wonder then, who is responsible. WHO is responsible for any problems, bugs, deficiencies, or whatever malfunctions which the programs make their users endure? Things may work wrong however the "wrong" happens. AI needs to fix the problems for the users. Any way to...
Back
Top