Solutions to Problem Set #4

CS 155 -- November 22, 1999

  1. The first table below represents the state space tree with each node labeled with its weight so far, profit so far, upper bound, and lower bound, in that order. Bounds are not shown for nodes for which they are not computed. The second table gives the search order of each node, for each of the four given strategies.

    0
    0
    58.71
    53
    10
    27
    58.71
    53
    0
    0
    57.3
    57
    19
    51
    58.71
    53
    10
    27
    57.8
    47
    9
    24
    57.3
    57
    0
    0
    56
    56
    19
    51
    58.67
    53
    17
    45
    57.8
    47
    10
    27
    57.5
    52
    16
    42
    57.3
    57
    9
    24
    57
    49
    7
    18
    -
    -
    0
    0
    -
    -
    19
    51
    58.5
    53
    17
    45
    57.5
    47
    19
    50
    57.5
    52
    10
    27
    44
    44
    16
    42
    57
    57
    18
    47
    -
    -
    9
    24
    -
    -
    16
    41
    -
    -
    7
    18
    -
    -
    9
    23
    -
    -
    0
    0
    -
    -
    19
    51
    53
    53
    17
    45
    47
    47
    19
    50
    52
    52
    16
    42
    -
    -
    10
    27
    -
    -
    22
    57
    57
    57
    16
    42
    44
    44
    18
    47
    -
    -
    15
    39
    -
    -
    9
    24
    -
    -
    22
    56
    -
    -
    16
    41
    -
    -
    13
    33
    -
    -
    7
    18
    -
    -
    15
    38
    -
    -
    9
    23
    -
    -
    6
    15
    -
    -
    0
    0
    -
    -
    20
    53
    19
    51
    18
    47
    17
    45
    20
    52
    19
    50
    17
    44
    16
    42
    11
    29
    10
    27
    22
    57
    17
    44
    16
    42
    19
    49
    18
    47
    16
    41
    15
    39
    10
    26
    9
    24
    22
    56
    17
    43
    16
    41
    14
    35
    13
    33
    8
    20
    7
    18
    16
    40
    15
    38
    10
    25
    9
    23
    7
    17
    6
    15
    1
    2
    0
    0

    1
    1
    1
    1
    2
    2
    2
    2
    17
    12
    11
    11
    3
    3
    3
    3
    7
    7
    6
    6
    18
    13
    12
    12
    29
    -
    -
    -
    4
    4
    4
    4
    8
    8
    7
    7
    11
    10
    9
    9
    19
    14
    13
    13
    23
    -
    -
    -
    30
    -
    -
    -
    37
    -
    -
    -
    5
    5
    5
    5
    9
    9
    8
    8
    12
    11
    10
    10
    14
    -
    -
    -
    20
    15
    14
    14
    24
    -
    -
    -
    26
    -
    -
    -
    31
    -
    -
    -
    34
    -
    -
    -
    38
    -
    -
    -
    41
    -
    -
    -
    6
    6
    -
    -
    10
    -
    -
    -
    13
    -
    -
    -
    15
    -
    -
    -
    16
    -
    -
    -
    21
    16
    15
    15
    22
    -
    -
    -
    25
    -
    -
    -
    27
    -
    -
    -
    28
    -
    -
    -
    32
    -
    -
    -
    33
    -
    -
    -
    35
    -
    -
    -
    36
    -
    -
    -
    39
    -
    -
    -
    40
    -
    -
    -
    42
    -
    -
    -
    43
    -
    -
    -
    20
    53
    19
    51
    18
    47
    17
    45
    20
    52
    19
    50
    17
    44
    16
    42
    11
    29
    10
    27
    22
    57
    17
    44
    16
    42
    19
    49
    18
    47
    16
    40
    15
    38
    10
    26
    9
    24
    22
    56
    17
    43
    16
    41
    14
    35
    13
    33
    8
    20
    7
    18
    16
    40
    15
    38
    10
    25
    9
    23
    7
    17
    6
    15
    1
    2
    0
    0

    The four search strategies expand respectively 43, 16, 15, and 15 nodes. The optimal solution includes items 2, 3, and 5 for a total weight of 22 and a total profit (or value) of 57.

  2. Below are given the trees of remainders for the two factors 2x3 + x2 + 2x - 1 and 3x2 - 2x + 1, the resulting sequences of values, the pointwise product of these sequences, and the tree of remainders for the polynomial corresponding to this pointwise product.

    2x3 + x2 + 2x - 1
    2x3 + x2 + 2x - 1
    2x3 + x2 + 2x - 1
    4x
    -2
    (2 + 2i)x + (-1 + i)
    (2 - 2i)x + (-1 - i)
    4
    -4
    -2
    -2
    -1 + (1 + 2·2½)i
    -1 + (1 - 2·2½)i
    -1 + (-1 + 2·2½)i
    -1 + (-1 - 2·2½)i

    3x2 -2x + 1
    3x2 - 2x + 1
    3x2 - 2x + 1
    -2x + 4
    -2x - 2
    -2x + (1 + 3i)
    -2x + (1 - 3i)
    2
    6
    -2-2i
    -2+2i
    (1 - 2½) + (3 - 2½)i
    (1 + 2½) + (3 + 2½)i
    (1 + 2½) + (-3 - 2½)i
    (1 - 2½) + (-3 + 2½)i

    4
    -1 + (1 + 2·2½)i
    -2
    -1 + (-1 + 2·2½)i
    -4
    -1 + (1 - 2·2½)i
    -2
    -1 + (-1 - 2·2½)i
    2
    (1 - 2½) + (3 - 2½)i
    -2-2i
    (1 + 2½) + (-3 - 2½)i
    6
    (1 + 2½) + (3 + 2½)i
    -2+2i
    (1 - 2½) + (-3 + 2½)i
    8
    (-4·2½) + (-6 + 2·2½)i
    4+4i
    (4·2½) + (6 + 2·2½)i
    -24
    (4·2½) + (-6 - 2·2½)i
    4-4i
    (-4·2½) + (6 - 2·2½)i

    [(-4·2½) + (6 - 2·2½)i]x7 + [4-4i]x6 [(4·2½) + (-6 - 2·2½)i]x5 - 24x4 [(4·2½) + (6 + 2·2½)i]x3 + [4+4i]x2 [(-4·2½) + (-6 + 2·2½)i]x + 8
    12ix3 + 8x2 - 12ix - 16
    (8·2½ + 4·2½i)x3 + 8ix2 + (-8·2½ + 4·2½i)x + 32
    -8
    -24ix - 24
    (-12·2½ + 12·2½i)x + 24
    (-4·2½ - 4·2½i)x + 40
    -8
    -8
    0
    -48
    0
    48
    48
    32

    The appropriate reordering the elements of the last row gives the sequence
    (-8 32 -48 48 -8 48 0 0), corresponding to n times the coefficients of the product polynomial 6x5 - x4 + 6x3 -6x2 + 4x - 1.