sandesh247 / problems Goto Github PK

The title says it all.

Given a graph with edge weights, such that every cycle in the graph has a strictly positive weight, design an algorithm to compute the number of shortest paths between two given nodes u and v of the graph.

Suppose you are given a directed graph G = (V, E) with costs on the edges c_e for e ∈ E and a sink t (costs may be negative). Assume that you also have finite values d(v) for v ∈ V . Someone claims that, for each node v ∈ V , the quantity d(v) is the cost of the minimum-cost path from node v to the sink t.

(a) Give a linear-time algorithm (time O(m) if the graph has m edges) that verifies whether this claim is correct.

(b) Assume that a distance are correct, and d(v) is finite for all v ∈ V . Now you need to compute distances to a different sink t′. Give an O(m log m) algorithm for computing distance d′(v) for all nodes v ∈ V to the sink node t′.

A vertex cover of a graph G = (V, E) is a subset of vertices S ⊆ V that includes at least one endpoint of every edge in E. Give a linear-time algorithm to find the smallest vertex cover of a given undirected tree T = (V, E).

The longest common substring of two strings X and Y is the longest string which appears as a run of consecutive letters in both strings. Give an O(|X||Y|) dynamic programming algorithm, and a non dynamic programming algorithm, for the above problem.