My homework task is: Let a linear, binary, array A and two positives real numbers a and b, with a < b. Give a dynamic programming algorithm using bottom-up approach, that splits table A to the minimum numbers of continuous sub-arrays, so that the percentage of units (1s) <= a, OR percentage of units (1s) >= b.. Analyze the run time of the algorithm. For example, with input A = [1; 0; 1; 1; 1; 0; 0; 1; 0; 0; 0; 1; 1], a = 23, and b = 64, the Array b can break into the three subsets [1; 0; 1; 1; 1], [0; 0; 1; 0; 0], and [0; 1; 1] with unit rates 80%, 20%, and 66.6%, respectively
My thought: Instead of counting the units (1s) of the sub-array, we can calculate the sum of its elements and divide it with the total numbers of its elements (0s and 1s).I have studied about DP and I know that I have to define a function, a recurrence and a table for storing data, but I find difficulties putting them all together writing the algorithm
IDEA:
There is a famous dynamic programming problem called matrix multiplication.There we will make a 2 dimensional table and fill the values in that table in bottom up approach to finally achieve the required answer.Even in the given problem,we need to make a 2 dimensional matrix(M) such that M(i,j) = answer for the sub array A[ i to j ].
Eg: 1.M(0,0)= A[0] which is equal to 1 since only one element is left
2.M(1,4)={0,1,1,1} and it is equal to 1 since on the whole it satisfies the required condition.
3.M(0,6)={1,0,1,1,1,0,0} and it is equal to 2 as it should be divided into {1,0,1,1,1,0} and {0}.
ALGORITHM:
In this way, we can use the below code in dynamic programming approach to find the value of M(i,j):
if( satisfy(A[ i to j ]) )M(i,j)=1;
else{
M[i][j] = INT_MAX;
for (k=i; k<=j-1; k++)
{
q = M[i][k] + M[k+1][j];
if (q < M[i][j])
M[i][j] = q;
}
}
So,in the bottom up approach by filling the table we can find the required value.The algorithm of the entire code is :
int Array_Division(int A[], int n,int a, int b)
{
int M[n][n];
int i, j, k, L, q;
for (i=1; i<n; i++)
M[i][i] = 1; //Since only 1 element is there its value is 1
for (L=2; L<n; L++) //Size of sub array
{
for (i=1; i<n-L+1; i++)
{
j = i+L-1;
if( satisfy(A[ i to j ]) )M(i,j)=1;
else{
M[i][j] = INT_MAX;
for (k=i; k<=j-1; k++)
{
q = M[i][k] + M[k+1][j];
if (q < M[i][j])
M[i][j] = q;
}
}
}
}
return M[0][n-1];
}
My homework task is: Let a linear, binary, array A and two positives real numbers a and b, with a < b. Give a dynamic...
Please give a output Linux/Ubuntu and how to run it (compile) this program ,my assigment is below : : Merge Sort algorithm using 2 processes a.) Define an integer array of 100 integers. Populate this array with random numbers. You can use int rand(void); function. Do not forget to initialize this function. You will sort the numbers in the array using merge-sort algorithm. In merge sort algorithm the half of the array will be sorted by one process and second...
Suppose you have an array S indexed from 1 to n which contains n numbers, not in any particular order, and you wish to count how many times a given number x occurs in S. Consider the recursive algorithm below for this which finds the number of occurrences of x in the index range i...j in S. Of course, solving the problem would involve an initial call to the algorithm for the range 1.n: int CountOccur (int i,j) { int...
this is advance java
Monster ARray Summary: Write a program that shows the path of an imaginary monster moving through a two dimensional array trying to "eat" the highest values in the array. As the monster goes, it leaves a trail behind it. Imagine a 40x40 array, displayed like this, where Os are printed as periods (dots), and non-zero valués are printed as normal. Then, place the values 2 through 9 randomly on the array. The rest of the document...