# Topic 8 Exercises
## Problem 1
Given: A,B,C (strings)

**Algorithm**
* First, if A.length() + B.length() != C.length() then return false
* For this problem, we will need a matrix/table which has dimensions A.length()+1 x B.length()+1 which we will call Table
* we loop through Table starting with Table[0][0] and each spot, Table[i][j], is set to True if A[0,i] and B[0,j] can interleave to make C[i+j], and False otherwise
* This is done using the following process:
* Loop through the first row of Table, and set each spot to True if A[0,j]==C[0,j], and similartly loop through the first column, setting to True if B[0,i]==C[0,i]
* then, starting at spot (1,1), begin looping through the whole table setting each spot (i,j) to:
* Table[i][j-1] if A[j]==C[i+j]
* Table[i-1][j] if B[i]==C[i+j]
* False: otherwise

* The lower right corner of the matrix (ie. Table[A.length()+1, B.length()+1]) will hold the final answer of whether A and B can interleave to form C

* By working from the bottom up, checking whether the smallest substrings of A&B can interleave the smallest substrings of C, and then as we step through the table, building up solutions, we need only to check whether the new character in C matches the new one from A and B, and then check if the subproblem before the addition of the new letter was true.

**Complexity**
Time: O(A.len * B.len) because you run through a nested loop based on the lengths of the input strings A and B
Space: A.len * B.len because you use a 2d array with those dimensions

## Problem 2
## Problem 3
This problem requires a dynamic programming Array of Arrays where each successive Array contains information about which strings to concatenate first. In the first Array, the program will start by looking at the first three strings of the $m$ strings and see if it is more optimal to concatenate the left two strings first and then the right or to concatenate the two right strings first and then concatenate the left string. This decision will be stored in the first entry in the first Array. The second entry in this array will be the same decision about the second set of three of the m strings (i.e. the second,third and fourth strings). Then the third entry will be the same decision about the third set of three strings (i.e. the third, fourth and fifth strings). This will continue until the program has looked at all sets of three adjacent strings. The second array will do a very similar thing instead for all sets of four adjacent strings. It will decide for all of these sets, using the information stored in the first array, whether it is more efficient to concatenate the three left strings first and then the right one or the three right ones and then the left one. The next array will do the same thing but for all sets of five adjacent strings, then six adjacent strings, and then finally $m-1$ adjacent strings in the final array. Then the program will have all the information is needs to see the optimized order of string concatenations. It will start by looking at the last array which decides whether to concatenate the left most or right most $m-1$ strings and then it will know which string to concatenate last based on the information stored in this entry. Then looking at those $m-1$ strings, the second to last Array will know whether or not to concatenate the left or right $m-2$ strings first. Then the third to last Array will know of those $m-2$ strings whether to concatenate the left or right $m-3$ strings first. When the program reaches the first array, it will know exactly the order for which to concatenate the strings.