算法代写: EECS 340 Algorithms Homework 6

EECS 340 Algorithms 2018 Spring Semester

Homework 6

Topics: Shortest paths, minimum spanning trees, and approximation algorithms.

1. Warm-Up(a) Solve R-15.1 in the text. (⋆) (b) Solve R-18.3 in the text. (⋆)
2. Dijkstra Revisited
   Solve C-14.3 in the text. (⋆ ⋆)
3. The Struggle of Commuter StudentsGiven an undirected weighted graph G = (V, E) with non-negative edge weights, and two vertices s, t ∈ V , let G′ be G, but where every edge has its weight increased by 1. Prove that G and G′ have the same set of shortest paths from s to t, or provide a counterexample. (⋆ ⋆)
4. Unique Bonsai
   Solve C-15.3 in the text. (⋆ ⋆)
5. Bonsai No More
   1. (a)  Solve C-15.9 in the text. (⋆)
   2. (b)  In the setting of C-15.9, suppose that instead of adding 1 to the weight of every edge, we multiply the weight of every edge by 2. Are the minimum spanning trees of G and G′ still the same? Prove, or provide a counterexample. (⋆)
6. Burma ShaveYou’ve learned, much to your dismay, that the LED text display in the Glennan Student Area has been replaced. In its place is a new-fangled and expensive iLED display produced by Plum Inc. which has reduced functionality, only capable of inserting, deleting, or replacing one character per second 1. It has a very nice touch- screen interface on the back, however, which lets you easily enter a list of strings for

1But dang, do those string transitions look pretty. 1

it to cycle through in sequence. You’ve been tasked with writing a program which takes as input a set of strings and returns an order to display the strings which minimizes the total transition time between strings in each cycle. A wise elder in HackCWRU informs you that it may not be tractable to achieve the minimum to- tal transition time, but you should be able to come up with a somewhat bearable solution which is within a factor of two of the minimum.

(a) Describe an algorithm to do this which has polynomial runtime in the total length of the strings. Assume that you have access to a method TimeBetween(S1, S2) which computes the minimum number of seconds it would take to transition between the string S1 and the string S2 and runs in O(|S1| ∗ |S2|) time. (⋆ ⋆ ⋆)
Hint: If we have three strings S1, S2, S3, how do TimeBetween(S1, S2), TimeBetween(S2, S3), and TimeBetween(S1, S3) relate?

(b) Extra Finals Practice (Not Graded):
Implement TimeBetween using dynamic programming. As an example of

TimeBetween’sexpectedbehavior,ifweletS1 =”arrhythmic”andS2 =”algorithmic” 2, then one sequence of edit operations we could perform to get from S1 to S2
would be:

String
arrhythmic
alrhythmic
algrhythmic
algorhythmic (insert ”o”)

Edit Operation

(replace ”r” with ”l”) (insert ”g”)

(delete ”h”)

algorithmic
which turns out to have the minimal number of edit operations (5), so TimeBetween would return 5. (⋆ ⋆ ⋆)

7. FedUP, Regulated Federally Solve A-18.4 in the text. (⋆ ⋆)

8. The following is for EECS 454 students only.
Read Section 17.5 in the textbook and then solve the following problems:

(a) R-17.3 (b) R-17.14

2Our mixtape, ”Algorhythmic” will be dropping this summer, brought to you by the Applicative Funk- tors.

algorythmic

(replace ”y” with ”i”)

2