Develop a Dynamic-Programming Algorithm for a Summation Recurrence

Question

I'm studying for an exam, and the professor gave us a bunch of practice problems that we don't have the answer to. This is one of them, but I've been working on it forever and don't even know if I'm headed in the right direction. I'm not even asking for an answer - just someone to point me in the right direction?

I'm supposed to develop a dynamic programming algorithm (of O(n^2)) for the following function that finds the expected number of acyclic orientations in a graph using this recurrence.

I think I'm supposed to solve the recurrence using the Master Theorem or unfold-and-sum to simplify/solve the recurrence, and then develop the algorithm from there? Any hints or clues would be much appreciated. Thanks!

Answer 1

As you provide both formula you needed, then you can find what you need by following steps:

1. Use O(n^2) to precompute nCr (as large as you need for n)
2. Use repeating squaring method to precompute (1+x)^n (I suppose you know the domain of x? so it is O(n lgn) for all n
3. Calculate A_n(X) as using those precomputed values, you have at most O(n) subproblems to calculate, each using O(n) which gives O(n^2)

---

EDITED:

For point #2, which is to calculate (1+x)^i(n-i) for i in [0,n], though the largest power can be up to n^2, but indeed there is only n instances, and we do not need to calculate all power up to n^2.

Let's write down the sequence of the power for different i in [0,n]: 0, n-1, 2(n-2), 3(n-3)...(n-1)(1)

And we can precompute them in a way like

function repeat_squaring(base, power){
  //O(lg (power))
}


for(int i=0; i<=n; i++){   
    repeat_squaring(1+x, i*(n-i));
}

So now, what is the complexity to compute them in total? Just sum them up!

T = O(lg n + lg(2n) + lg(3n) + ... lg(n*n)) = O(summation(lg(i)) + nlg(n)) = O(lg(n!) + nlgn) = O(n lg n)

For the complexity of O(lg(n!)), there is two way to reason it, one is the famous Stirling's approximation, another way is this post: log(n!)

---

EDITED2: For shrinking n problem

I observe the pattern of the (1+x)^(i(N-i)) for N = n, n-1, n-2..etc

You can see that we can derive the term (1+x)^j for smaller A_n() from some already calculated (1+x)^(i(N-i))

We use O(n lg n) as described above to pre-calculate for the powers when N = n first, also we can use O(n lg n) to pre-calculate all (1+x)^i for i in [0..n]

Now as the pattern shown, the term (1+x)^(i(N-i)) for consecutive N values (n vs n-1, n-1 vs n-2 ...), you can indeed use O(1) to multiply / divided by some (1+x)^i where i in [0..n] (depends on your implementation, either bottom-up / top-down)

So I still think you only need O(n lgn) to pre-compute those powers, and use O(1) to transform them into other powers dynamically when you needed. (You can think as you are doing dynamic programming on both (1+x)^(i(N-i)) and A_i() at the same time)

TL;DR Of course, if you do not want things being too complicated, you can just use O(n^2) to do a separate DP on (1+x)^(i(N-i)) for all N in [1..n]

// High Level Psuedo Code

var nCr[][]; 
var p[]; // (1+x)^0, (1+x)^1 ... (1+x)^n
var b[]; // (1+x)^0, (1+x)^(n-1),  (1+x)^2(n-2)...
var power[n][i] // (1+x)^i(n-i), power[max_n][x] = b[] actually
var A[] // main problem! 


Precompute nCr[][];  // O(n^2)
Precompute p[];  // O(n lg n)
Precompute b[]; // O(n lg n)

Precompute power[n][i] {
  // O(n^2)
  for all x, for all i
    power[x][i] = power[x+1][i]/p[i]
}

Compute A using all those precompute arrays, O(n^2)