HW9

Submit a single .pdf for the written problems and .java codes for the coding problems to me via email by the date of the deadline (11:59 pm)

(1) Please show ALL of your work (Step by Step).

(2) Provide as many details as possible for the designed algorithms (exact pseudocode) from now on. 

1. [Written 10pt] What is the time efficiency class of the greedy algorithm (presented in class) for the knapsack problem?

2. [Written 20pt] Consider the greedy algorithm for the bin-packing problem, which is called the first-fit (FF) algorithm: place each of the items in the order given into the first bin the item fits in; when there are no such bins, place the item in a new bin and add this bin to the end of the bin list.

    a. Apply FF to the instance s1 =0.4, s2 =0.7, s3 =0.2, s4 =0.1, s5 =0.5 and determine whether the solution obtained is optimal.

    b. Determine the worst-case time efficiency of FF. Show an example to explain why. 

3. [Written 20pt] The first-fit decreasing (FFD) approximation algorithm for the bin-packing problem starts by sorting the items in nonincreasing order of their sizes and then acts as the first-fit algorithm.

    a. Apply FFD to the instance s1 =0.4, s2 =0.7, s3 =0.2, s4 =0.1, s5 =0.5 and determine whether the solution obtained is optimal.

    b. Does FFD always yield an optimal solution? Justify your answer.

4. [Written 20pt] (a) Design a polynomial-time greedy algorithm for the graph-coloring problem. (b) Show that the performance ratio of your approximation algorithm is infinitely large.

5. [Written 20pt] (a) Apply the nearest-neighbor algorithm to the instance defined by the inter-city distance matrix below. Start the algorithm at the first city, assuming that the cities are numbered from 1 to 5. (b) Compute the accuracy ratio of this approximate solution.

6. [Written 20pt] Apply the twice-around-the-tree algorithm to the graph in Figure 12.11a with a walk around the minimum spanning tree that starts at the same vertex a but differs from the walk in Figure 12.11b (Hint: counter-clockwise walk). Is the length of the obtained tour the same as the length of the tour in Figure 12.11b?. (Show all of your steps)