1. Give and verify a linear time algorithm that takes two sequences of events (say encoded as lists of binary integers), and determines whether the first sequence of events is a subsequence of the second.
Problem formulation:
Two sequences: and , with length of and , respectively.
Test whether is a subsequence of.
Idea:
Use two pointers, for sequence , for sequence . Compare with
If move both pointers forward, which is
If , only move forward, which is .
In this way, traverses once, and traverses once.
The time complexity is
Algorithm:
Verification:
This is a greedy algorithm. We claim that greedy algorithm always findsthe feasible solution if there is any.
We prove this by contradiction. For the example below, greedy algorithm selects a set of jobs from sequence B to match sequence A, which is (g1, g2,..., gr, g(r+1), …). The solution is denoted as (s1, s2, …,sr, s(r+1) , …). g1=s1, g2=s2, …, gr=sr for largest possible value of r. Since g(r+1) and s(r+1) match the same job. Why do not replace s(r+1) with g(r+1)? After replacement, the solution is still feasible. We get, s(r+1) =g(r+1). There is another job in common, which contradicts with the largest possible value is r.
Inductively, we can always replace the choice of solution with the choice of greedy algorithm. And such replacements will not jeopardize the feasibility of the solution. In another word, greedy algorithm always returns a feasible solution if there is any.
2. In lecture 3 we discussed the greedy cashier’s algorithm for making change of x units using the smallest number of coins. The cashier’s algorithm gives the customer one unit of the highest denomination coin of at most x units, say d units. Now repeat to make change of the remaining x-d units. For each of the following nation’s coinage, establish whether or not this greedy algorithm always minimizes the number of coins returned in change. If so, prove it, if not give a counter example.
(a) MiddleEarth coinage, which includes coins for 1, 4, 5, 10, and 20.
No.
X=8
Optimal solution: 8=4+4, two coins
Greedy Algorithm: 8=5+1+1+1, four coins
So, greedy algorithm does not always minimize the number of coins.
(b) English coinage before the decimalization, which consisted of half-crowns (30 pence), orins (24 pence), shillings (12 pence), sixpence (6 pence), threepence (3 pence), pennies (1 pence).
No.
X=48;
Optimal solution: 48=24+24, two coins
Greedy Algorithm: 48=30+12+6, three coins
So, greedy algorithm does not always minimize the number of coins returned.
(c) Martian coinage, where the available denominations are powers of some integer p>1, i.e., 1, p, p^2, p^3,…,p^k.
Yes, greedy algorithm always minimizes the number of coins returned.
Let arbitrary satisfy:
For greedy algorithm, the solution contains coin k. Suppose greedy algorithm is not an optimal solution. In another word, the optimal solution does not contain coin k. Thus, there exists a set of coefficients that satisfies that:
This is impossible for any optimal solution, which can be seen from the table below.
k / Ck / All optimal solutions must satisfy / Max value of coins 0,1,….,k-1 in any OPT0 / / / -
1 / / /
2 / / /
… / … / … / …
k / / /
Therefore, we refuse the hypothesis that the optimal solution does not contain coin k.
Then, problem reduces to coin-changing , which, by induction, is also optimally solved by greedy algorithm.
3. The single-destination shortest path problem for a weighted directed graph is to find the shortest path from every vertex to a specified vertex v. Give and verify an efficient algorithm to solve the single-destination shortest paths problem.
Idea:
First, reverse all edges; second, use the Dijkstra’s Algorithm to find the shortest paths.
Algorithm:
Reverse the direction of all edges. Thus, the destination vertex becomes the source.
Maintain a set of explored nodes for which we have determined the shortest path distance from to vertex . And a set of unexplored nodes .
Initialize
while () do
{
select the node, which subjects to , and has the smallest among all nodes in
add to S
delete from P
for node , , do
{
, is the weight of edge from to
If do
}
}
Verification:
Claim: is the shortest path from to
We prove this by induction on.
, is obviously the shortest path from to , if is selected to be added to next.
, let be the next node to be added to . And we need to prove is still the shortest path from to .
There are two possibilities for the path from to :
1, the path only contains the nodesin . In this situation, is the shortest path since we update every time we add a new node to
2, the path contains nodes in both and , as shown in the figure below.
Suppose there is a node on path . Let be the first edge in that leaves , and let be the subpath to . Due to nonnegative property of weights, we ignore the weights from to , thus
Due to the hypothesis that is the shortest path from to for all in
From the definition of , we have
is the next node to be added to , so
To sum up, any path from to will have a greater weight than
Due to the reversibility of path, we conclude that is the shortest path from to.
The time complexity for this algorithm is , where is the maximal value of out-going degree among all vertices in the reversed graph, is the number of vertices. (Implemented with binary heap)
4. Let G = (V,E) be an undirected weighted graph, and let T be the shortest-path spanning tree rooted at a vertex v.
(a) Consider the graph G* obtained by modifying all the edge weights in G by multiplying the weight by a constant factor c >0. Is T still the shortest-path spanning tree in G* from v? Justify your answer.
Yes, T is still the shortest-path spanning tree in G* from .
First of all, we should clarify that shortest-path spanning tree is defined as a tree, in which the path weight from root node to any other node is minimized.
In G, for an arbitrary vertex , the path from to defined by is denoted as , any other path from to is denoted as . We have for any .
In G*, all edges have been multiplied by a constant factor . Hence, the path weight between any two vertices is times of the weight in the original graph .
Thus for G*, .
So, , which means path still has the lowest weight in graph G*. Since vertex and path are selected arbitrarily. We are safe to conclude that T is still the shortest-path spanning tree in G* from .
(b) Consider the graph G+ obtained by modifying all the edge weights in G by adding to the weight by a constant d >0. Is T still the shortest-path spanning tree in G+ from v? Justify your answer.
No, T is notnecessarily the shortest-path spanning tree in G+ from .
Similar to question (a), for an arbitrary vertex, the path defined by is denoted as , and another arbitrary path is denoted as.
We have,
In G+, , where and are the number of edges on path and, respectively.
Since the relationship between and is not determined (I mean could be much larger than ), the relationship between and can not be determined. It could be .
Following is a counter example. The shortest-path spanning tree is shown in red.
We can see that the shortest-path spanning tree in two graphs are not the same.
5. Suppose that you run both depth-first search and breadth-first search on a connected graph G, and they both return the same tree T. Prove that G=T, i.e., there are no additional edges in the graph.
Suppose .
First of all, T will not have edges that are not in G, since T has the minimal number of edges to construct a connected graph.
Second, assume there is an edge in G but not in T.
Then, there will be a cycle in G. Nodes in this cycle is denoted as: . is connected to and . Let is the first accessed node in this cycle.
Breadth-first search: both and are one depth deeper than node .
Depth-first search: at most one of the two neighboring nodes (and ) will be explored at the next level.
This contradicts with “both depth-first search and breadth-first search return the same tree”.
Therefore, there is no additional edges in G. Thus, G=T.