3
$\begingroup$

I was going through the Dynamic Programming section of Introduction to Algorithms (2nd Edition) by Cormen et. al. where I came across the following recurrence relations in the context of assembly line scheduling

(Note: Assembly line scheduling or dynamic programming is not required to answer to the question though, it is just for information so that it shall help relating the context).


$(1),(2),(3)$ are three relations as shown.

$$f_{1}[j] = \begin{cases} e_1+a_{1,1} &\quad\text{if } j=1\\ \min(f_1[j-1]+a_{1,j},f_2[j-1]+t_{2,j-1}+a_{1,j})&\quad\text{if } j\geq2\\ \end{cases}\tag 1$$

Symmetrically,

$$f_{2}[j] = \begin{cases} e_2+a_{2,1} &\quad\text{if } j=1\\ \min(f_2[j-1]+a_{2,j},f_1[j-1]+t_{1,j-1}+a_{2,j})&\quad\text{if } j\geq2\\ \end{cases}\tag 2$$

(where $e_i,a_{i,j},t_{2,j-1}$ are constants for $i=1,2$ and $j=1,2,3,...,n$)

$$f^\star=\min(f_1[n]+x_1,f_2[n]+x_2)\tag 3$$


The text tries to find the recurrence relation of the number of times $f_i[j]$ ($i=1,2$ and $j=1,2,3,...,n$) is referenced if we write a mutual recursive code for $f_1[j]$ and $f_2[j]$. Let $r_i(j)$ denote the number of times $f_i[j]$ is referenced.

They say that,

From $(3)$,

$$r_1(n)=r_2(n)=1.\tag4$$

From $(1)$ and $(2)$,

$$r_1(j)=r_2(j)=r_1(j+1)+r_2(j+1)\tag 5$$


I could not quite understand how the relations of $(4)$ and $(5)$ are obtained from the three corresponding relations. (directly without any proof, is it so trivial?)

Thought I could make out intuitively that as there is only one place where $f_1[n]$ and $f_2[n]$ are called, which is in $f^\star$, so probably in $(4)$ we get the required relation.

But as I had not encountered such concept before I do not quite know how to proceed. I would be grateful if someone guides me with the mathematical prove of the derivation as well as the intuition.

[Note: However an alternative to mathematical induction shall be more helpful as it is a mechanical cookbook method without giving much insight into the problem though (but if in case there is no other way out, then even mathematical induction is appreciated if I can get the intuition behind the proof)].

$\endgroup$
3
$\begingroup$

It looks like that you are exhausted after a long and tiring journey that you have taken to comprehend the setup of assembly-line scheduling, the step 1 on the structure of the fastest way through the factory and the step 2 on a recursive solution.

It is straightforward to understand formula (4) and (5).

When we program a recursion solution using formula (1), (2) and (3), the left-hand side of each formula is transformed to the signature of its implementing method while the right-hand side is transformed to the body of the method.

For example, (3) is transformed to pseudo-Python code

def f_star(n):
    return min(f_1(n) + x_1, f_2(n) + x_2)

So, when $f^\star$ is referenced, i.e., when f_star is called, $f_1[n]$ and $f_2[n]$ will be referenced, i.e., f_1(n) and f_2(n) will be called, where f_1(.) and f_2(.) will be explained below. Since we will call f_star(n) once, which is enough to get the value of $f^\star$, we get formula (4).

Formula (1) is transformed to pseudo-Python code

def f_1(j):
    if j == 1:
        return e[1] + a[1][1]
    else:
        return min(f_1(j - 1) + a[1][j], f_2(j - 1) + t[2][j - 1] + a[1][j])

So whenever $f_1[j]$ is referenced, i.e., when $f_1(j)$ is called, $f_1[j-1]$ will be referenced exactly one, i.e., f_1(j-1) will be called exactly once.

Similarly, whenever $f_2[j]$ is referenced, $f_1[j-1]$ will be referenced exactly once. (You can write the function f_2(j) explicitly yourself to check it out.)

Note that any reference to $f_1[j-1]$ must be brought by either a reference to $f_1[j]$ or a reference to $f_2[j]$. So we have $$r_1(j-1) = r_1(j) + r_2(j).$$

Similarly or by symmetry, we also have $$r_2(j-1) = r_1(j) + r_2(j).$$

Replacing $j$ by $j+1$, we get formula (5).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks a lot for the help. $\endgroup$ – Abhishek Ghosh Jul 1 at 5:56
  • 1
    $\begingroup$ Welcome. $\phantom{}$ $\endgroup$ – John L. Jul 1 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.