Solutions

  1. Answer: The circuit would be Boston, Providence, Hartford, Concord, Montpelier, Augusta, Boston. It does matter where you start. If you start in Concord, for example, your mileage will be higher.

  2. Answer:
    1. Optimal cost = 2 \sqrt 2. Phase 1 cost = 2.4 \sqrt 2. Phase 2 cost = 2.6 \sqrt 2.
    2. Optimal cost = 2.60. Phase 1 cost = 3.00. Phase 2 cost 2 \sqrt 2.
    3. A = (0.0, 0.5), B = (0.5, 0.0), C = (0.5, 1.0), D = (1.0, 0.5)

      There are 4 points; so we will divide the unit square into two strips.
      • Optimal Path: (B, A, C, D) Distance = 2 \sqrt 2
      • Phase I Path: (B, A, C, D) Distance = 2 \sqrt 2
      • Phase II Path: ( A, C, B, D) Distance = 2 + \sqrt 2

    4. A = (0, 0), B = (0.2, 0.6), C = (0.4, 0.1), D = (0.6, 0.8), E = (0.7, 0.5)

      There are 5 points; so we will divide the unit square into three strips.
      • Optimal Path: (A, B, D, E, C) Distance = 2.31
      • Phase I Path: (A, C, B, C, E) Distance = 2.57
      • Phase II Path: (A, B, D, E, C) Distance = 2.31

  3. Answer:
    1. f (c, d) = 2, f(b, d) = 2, f(d, k) = 5, f(a, g) = 1, and f (g,k) = 1.
    2. There are three possible flow-augmenting paths. s, b, d, k with flow increase of 1. s, a, d, k with flow increase of 1, and s, a, g, k with flow increase of 2.
    3. The new flow is never maximal, since another flow-augmenting path will always exist. For example, if s, b, d, k is used above, the new flow can be augmented by 2 units with s, a, g, k.

  4. Answer:
    1. Value of maximal flow = 31.
    2. Value of maximal flow = 14.
    3. Value of maximal flow = 14.

      Step

      1

      Flow-augmenting path

      Source,A, Sink

      Flow added

      2

      2

      Source,C, B, Sink

      3

      3

      Source,E, D, Sink

      4

      4

      Source,A, B, Sink

      1

      5

      Source,C, D, Sink

      2

      6

      Source,A, B, C, D, Sink

      2

  5. Hint: Count the number of comparisons of distances that must be done.

    Answer: To locate the closest neighbor among the list of k other points on the unit square requires a time proportional to k. Therefore the time required for the closest-neighbor algorithm with n points is proportional to (n − 1) + (n − 2) + · · · + 2 + 1, which is proportional to n2 . Since the strip algorithm takes a time proportional to n(log n), it is much faster for large values of n.