Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

HW 9

CS/ECE 374A: Intro. Algorithms & Models of Computation, Fall 2022

17 ( 100 pts.) Shortest legible walk.

You are given a directed graph G = (V, E) with n vertices and m ≥ n edges, and a pair of vertices s and t. In addition, every edge e ∈ E, has a weight w(e) > 0, and an associated character c(e) ∈ Σ . Thus, a walk π = e1 e2 e3 . . . ek  encodes the string c(π) = c(e1 )c(e2 ) ··· c(ek ).

You are also given a DFA M = (Q,Σ,δ,q0 ,A), where N = |Q|, and |Σ| = O(1).

Describe formally an algorithm, as fast as possible (the running time depends on n,m and N), that computes the shortest walk π from s to t, such that c(π) ∈ L(M). Formally, let

Π = {c(π) ∈ L(M) | π is a walk in G from s to t } .

The task is to compute arg minπ∈Π w(π).

18 ( 100 pts.) Paths and cycles.

Let G be a directed graph with n vertices and m edges, with positive numbers as weights on the edges.

18.A.    (50  pts.)   You are given in addition to G, two vertices s,t  ∈ V(G), and a parameter k .

Describe an algorithm, as fast as possible, that computes the shortest path in G between s and t, where you are allowed to travel on k edges for free. What is the running time of your algorithm?

18.B.    (50  pts.)   The heft  of a cycle C in G, is the minimum weight edge in C .   Describe an

algorithm, as fast as possible, that computes the maximum heft cycle in G.