Solutions to Problem Set #4, CS 255, April 24, 2006

Grading scale: 36 A, 34 A-, 32 B+, 28 B, 26 B-, 24 C+, 20 C
    1. The sequences obtained at each iteration are: 
      [0]
[0, 37]
[0, 31, 37, 68]
[0, 29, 31, 37, 60, 66, 68]
[0, 23, 29, 31, 37, 52, 54, 60, 66, 68, 83, 89]
[0, 19, 23, 29, 31, 37, 42, 48, 50, 52, 54, 56, 60, 66, 68, 
71, 79, 83, 87]
[0, 17, 19, 23, 29, 31, 36, 40, 42, 46, 48, 50, 52, 54, 56, 
59, 65, 67, 71, 77, 83, 87]
      The final approximate solution is thus 87.

    2. The sequences obtained at each iteration are: 
      [0]
[0, 37]
[0, 31, 37, 68]
[0, 29, 31, 37, 60, 66, 68]
[0, 23, 29, 31, 37, 52, 54, 60, 66, 68, 83, 89, 91]
[0, 19, 23, 29, 31, 37, 42, 48, 50, 52, 54, 56, 60, 66, 68,
 71, 73, 79, 83, 85, 87, 89, 91]
[0, 17, 19, 23, 29, 31, 36, 37, 40, 42, 46, 48, 50, 52, 54,
 56, 59, 65, 67, 69, 71, 73, 77, 79, 83, 85, 87, 89, 91]
      The final approximate solution is thus 91.
     

     

  2. The trace below shows the requested data at the beginning of each of the 5 iterations, and at termination. In each case, the nodes are shown in level order. The last 3 fields for each node give the destinations of its A link, B link, and C link. The numeric component of each field refers to the destination node by level order, except that a numeric component of 0 represents a null link. 
     1  a   A= 1  B= 0  C=-1    bA cA 0A 
 2  b   A= 1  B= 0  C=-1    dA eA aB 
 3  c   A= 1  B= 0  C=-1    cB cC aC 
 4  d   A= 1  B= 0  C=-1    fA dC bB 
 5  e   A= 1  B= 0  C=-1    eB gA bC 
 6  f   A= 1  B= 0  C=-1    fB fC dB 
 7  g   A= 1  B= 0  C=-1    hA iA eC 
 8  h   A= 1  B= 0  C=-1    hB hC gB 
 9  i   A= 1  B= 0  C=-1    jA iC gC 
10  j   A= 1  B= 0  C=-1    jB jC iB 

 1  a   A= 1  B=-1  C=-2    dA cB 0A 
 2  b   A= 2  B=-1  C=-2    fA eB cA 
 3  c   A= 1  B= 1  C=-1    cC aC 0A 
 4  d   A= 2  B=-1  C=-1    fB bB eA 
 5  e   A= 1  B= 1  C=-2    gA hA aB 
 6  f   A= 2  B= 1  C=-1    fC dB dC 
 7  g   A= 1  B=-1  C=-2    hB jA bC 
 8  h   A= 2  B= 1  C=-1    hC gB iA 
 9  i   A= 1  B=-1  C=-1    jB gC eC 
10  j   A= 2  B= 1  C=-1    jC iB iC 

 1  a   A= 1  B=-3  C=-1    fB aC 0A 
 2  b   A= 2  B=-2  C=-4    fC hA cC 
 3  c   A=-1  B= 0  C= 0    0A 0A 0A 
 4  d   A= 3  B= 0  C=-2    dB eB gA 
 5  e   A= 0  B= 0  C=-3    hB hC cB 
 6  f   A= 4  B= 3  C= 1    dC bB eA 
 7  g   A= 2  B= 0  C=-3    gB jC cA 
 8  h   A= 3  B= 2  C= 1    iA jA jB 
 9  i   A= 0  B= 0  C=-2    iB bC aB 
10  j   A= 1  B= 2  C= 1    iC gC eC 

 1  a   A= 1  B=-5  C=-4    bB 0A 0A 
 2  b   A= 2  B= 1  C=-4    eA iA 0A 
 3  c   A=-4  B=-3  C=-4    0A 0A 0A 
 4  d   A= 3  B= 3  C= 2    eB hC gB 
 5  e   A= 1  B= 0  C=-2    jA jB 0A 
 6  f   A= 4  B= 4  C= 3    gA hA hB 
 7  g   A= 0  B= 2  C=-1    jC eC 0A 
 8  h   A= 1  B= 2  C= 1    iB iC gC 
 9  i   A= 3  B= 0  C=-1    bC cC aC 
10  j   A= 3  B= 3  C= 1    aB cA cB 

 1  a   A= 1  B=-2  C=-5    iA 0A 0A 
 2  b   A= 2  B= 2  C=-1    jA bC 0A 
 3  c   A=-1  B=-2  C=-4    0A 0A 0A 
 4  d   A= 3  B= 3  C= 2    jB gC eC 
 5  e   A= 3  B= 3  C= 0    aB cA 0A 
 6  f   A= 4  B= 4  C= 3    jC iB iC 
 7  g   A= 4  B= 4  C= 0    cB 0A 0A 
 8  h   A= 5  B= 5  C= 4    cC aC 0A 
 9  i   A= 4  B= 1  C= 1    0A 0A 0A 
10  j   A= 4  B= 3  C= 1    0A 0A 0A 

 1  a   A= 1  B= 1  C= 0    0A 0A 0A 
 2  b   A= 2  B= 2  C= 1    0A 0A 0A 
 3  c   A= 2  B= 2  C= 1    0A 0A 0A 
 4  d   A= 3  B= 3  C= 2    0A 0A 0A 
 5  e   A= 3  B= 3  C= 2    0A 0A 0A 
 6  f   A= 4  B= 4  C= 3    0A 0A 0A 
 7  g   A= 4  B= 4  C= 3    0A 0A 0A 
 8  h   A= 5  B= 5  C= 4    0A 0A 0A 
 9  i   A= 5  B= 5  C= 4    0A 0A 0A 
10  j   A= 6  B= 6  C= 5    0A 0A 0A