Intro to algorithms

More hints and tips.

for the graph G, you can assume from any vertex i and to any vertex j there is a path from i to j.

alternatively you can assume there is a special expression (an empty symbol)

that expresses the emptyset.

more central to the "dynamic programming way" of thinking about this problem:

Suppose you want to talk about all paths from i to j, that pass through vertices with index **at most** 10.

There are two classes of such paths: 1. those that actually go through vertex 10.

and 2. those actually did not.

Now you should think of this second class as something you already have a grip of

from the earlier steps of your dynamic programming. (This is the key to the idea of

"dynamic programming".)

And for class 1. there is the first time that you reached 10, and you may have returned back to 10

zero or more times, and then there is a final time you said goodbye to 10 and left for j.

Now, try to express all these in terms of .... (use the idea of "dynamic programming".)

Graded Problem (Page limit: 1 sheet; 2 sides) Suppose you have been shown a new programming language that allows you to express the following: Any single symbol in the English alphabet set {A, B,, Z is expressible. These are considered strings of length 1. A special expression e also exists that denotes the empty tring. Given some two expressions that can express some two subsets S and T of strings, you can form an expression that expresses its union SUT, its concatenation S T- [ry | r E S,y E T. Finally, if S is a subset of strings already known to be expressible, there is a particularly powerful expressionery device that allows you to express the following (possibly infinite set of strings) S* = fe, 81, 8182 , . . . , s182 . . .n , . . . l si E s), where S (they are not necessarily distinct, i.e., repetitions are allowed), and s82 denotes the concatenation of s1 and s2, and similarly for s182 Now suppose we are given directed graph of n vertices, where every (directed) edge is labeled by one or more of the letters in (A, B,..., Z). Use the idea of Dynamic Programming to show that an expression can be found in this programming language that expresses the set of all string that would lead a path from vertex 1 to vertex n. Hint: First show that you can express the subset of such paths from any i to any j that does not pass through any vertex. Then consider all paths from i to j that pass through vertices among ,,k].) Graded Problem (Page limit: 1 sheet; 2 sides) Suppose you have been shown a new programming language that allows you to express the following: Any single symbol in the English alphabet set {A, B,, Z is expressible. These are considered strings of length 1. A special expression e also exists that denotes the empty tring. Given some two expressions that can express some two subsets S and T of strings, you can form an expression that expresses its union SUT, its concatenation S T- [ry | r E S,y E T. Finally, if S is a subset of strings already known to be expressible, there is a particularly powerful expressionery device that allows you to express the following (possibly infinite set of strings) S* = fe, 81, 8182 , . . . , s182 . . .n , . . . l si E s), where S (they are not necessarily distinct, i.e., repetitions are allowed), and s82 denotes the concatenation of s1 and s2, and similarly for s182 Now suppose we are given directed graph of n vertices, where every (directed) edge is labeled by one or more of the letters in (A, B,..., Z). Use the idea of Dynamic Programming to show that an expression can be found in this programming language that expresses the set of all string that would lead a path from vertex 1 to vertex n. Hint: First show that you can express the subset of such paths from any i to any j that does not pass through any vertex. Then consider all paths from i to j that pass through vertices among ,,k].)