Old Paper Virtual University CS-702 Advanced Algorithms Mid Term 2015
1. Consider
the problem of a chain < A1, A2, A3> of three matrices. Suppose the
dimensions of the matrices are 10×100, 100×5 and 5×50. For the sequence of
matrices, given above, compute the order of the product, A1.A2.A3,
in such a way that minimizes the total number of scalar multiplications.
2. Write
the pseudo code of n-line assembly: dynamic programming algorithm for print
stations.
3.
Show
that the sum of cubes of any three consecutive positive integers is divisible
by 9.
That
is, for any integer n, n3 + (n + 1)3 + (n + 2)3
is divisible by 9.
The
sum of the cubes of 1, 2, 3 is 1+8+27=36 which is divisible by 9.
Now suppose that for some k: C(k)=k^3+(k+1)^3+(k+2)^3 is divisible by 9.
Then:
C(k+1)=C(k) - k^3 + (k+3)^3 = C(k) + 3 (k^2*3) + 3 (k*3^2) + 3^3
..............=C(k) + 9 [k^2 + 3k + 3]
hence as by assumption C(k) is divisible by 9 so is C(k+1), and as we have
established that C(1) is divisible by 9, we have established by mathematical
induction that C(n) is divisible by 9 for all positive integers n.
This proves (as it is the same thing in different words) that the sum of the
cubes of three consecutive positive integers is divisible by 9.
Now suppose that for some k: C(k)=k^3+(k+1)^3+(k+2)^3 is divisible by 9.
Then:
C(k+1)=C(k) - k^3 + (k+3)^3 = C(k) + 3 (k^2*3) + 3 (k*3^2) + 3^3
..............=C(k) + 9 [k^2 + 3k + 3]
hence as by assumption C(k) is divisible by 9 so is C(k+1), and as we have
established that C(1) is divisible by 9, we have established by mathematical
induction that C(n) is divisible by 9 for all positive integers n.
This proves (as it is the same thing in different words) that the sum of the
cubes of three consecutive positive integers is divisible by 9.
Verify S(1): .1³ + 2³ + 3³ .= .36 . . . divisible by 9.
Assume S(k): .k³ + (k+1)³ + (k+2)³ .= .9a . for some integer a.
Add (k+3)³ - k³ to both sides:
. . k³ + (k+1)³ + (k+2)³ + (k+3)³ - k³ .= . 9a + (k+3)³ - k³
. . (k+1)³ + (k+2)³ + (k+3)³ .= .9a + k³ - 9k² + 27k - 27 - k³
. . (k+1)³ + (k+2)³ + (k+3)³ .= .9a - 9k² + 27k - 27
. . (k+1)³ + (k+2)³ + (k+3)³ .= .9(a - k² + 3k - 3)
The left side is the left side of S(k+1); the right side is a multiple of 9.
. . The inductive proof is complete.
Assume S(k): .k³ + (k+1)³ + (k+2)³ .= .9a . for some integer a.
Add (k+3)³ - k³ to both sides:
. . k³ + (k+1)³ + (k+2)³ + (k+3)³ - k³ .= . 9a + (k+3)³ - k³
. . (k+1)³ + (k+2)³ + (k+3)³ .= .9a + k³ - 9k² + 27k - 27 - k³
. . (k+1)³ + (k+2)³ + (k+3)³ .= .9a - 9k² + 27k - 27
. . (k+1)³ + (k+2)³ + (k+3)³ .= .9(a - k² + 3k - 3)
The left side is the left side of S(k+1); the right side is a multiple of 9.
. . The inductive proof is complete.
4. Solve
the recurrence relation given below
5.
We have to
compute the set of maximal points from following points, using Brute Force
Approach,
(2, 8), (6,
16), (8, 8), (10, 20), (12, 6), (16, 14), (18, 18), (20, 2), (24, 8)
6. Write
the pseudo code of assembly line scheduling algorithm using dynamic programming.
7. Write
the pseudo code of complete knapsack dynamic programming algorithm for 0-1
knapsack problem.
