Homework 8
(Maximum 50 points)
Due 11:59 pm of the class Friday April 6, 2018
Show the steps of deriving your answers. Points will be deducted for answers without adequate
steps discussed. Submit your homework via Blackboard as one PDF or Word document.
1. (25) [Algorithm design: independent set on a path (or chain)] Textbook Exercise 1 in
Chapter 6. For the exercises (a) and (b), give your counterexample. (Figure 6.28 is a
counterexample of the algorithm in the exercise b, so show a different counterexample.) For the
exercise (c), build an optimal substructure (with an explanation), give a bottom-up dynamic
programming algorithm, and show the running-time analysis. Hint: think backward from the last
node in a path.
2. (25) [Bellman-Ford shortest paths: algorithm tracing] Consider the directed graph shown
below. Run the Bellman-Ford shortest path algorithm we studied in class to find the shortest path
from each node to the node d, and fill in the two-dimensional memorization array M[0..n, V]
(provided below, where n = 5 is the number of nodes and V = a, b, c, d, e is the set of nodes in
the graph). Each array entry should have the shortest path length and the immediate successor
node (e.g., “8/e”). Your answers should include the completed memorization table and for each
node the shortest path and its path length in the following format: “Shortest path from x to d: x –
y – z – d (path length = 8)”. (Note path length is the sum of the weights of edges in the path.)
You are encouraged to show the intermediate steps of computing the shortest path length for
partial credit in case your answer is incorrect.
Memoization table:
| a | b | c | d | e |
| 0 | ||||
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 |
Last modified: March 30, 2018
The post deducted for answers without adequate steps appeared first on My Assignment Online.