Written 2 - Greedy

Problem 1:
Problem Description: To maximize the distance covered during a trip by minimizing stops along the way.
Inputs: Distance L, which stands for the total distance to be covered during
the trip. A set of stopping points (x1, x2, x3..., xn).
Outputs: In order to track the distance covered per day and whether the sum of
the distances traveled is less than or equal to L, let the daily distance traveled
be denoted by Gi
, where i stands for the day of the trip, i ≥ 1. Then the total
distance covered would be:
Gtotal =
Pn
i=1
Gi - Gi−1
Where G0 = 0 miles.
Assumptions: Units are assumed to be in miles. All distances between any two
successive points (x1, x2, x3..., xn) are positive and less than or equal to d. The
most one can travel in a day is d miles and one is able to determine arrival time
to the next stopping point perfectly.
Strategy: A greedy algorithm that drives the maximum distance possible (d)
per day.
Description: Since the most one can drive a total distance of d miles per day,
the greedy algorithm makes sure to come as close as possible to that distance.
The algorithm goes through the following steps:
-The algorithm verifies whether the first distance traveled, from x1 to x2
is less than or equal to d.
-If the distance from x1 to x2 < d, the distance is added to Gtotal and
checks if Gtotal = L. If that’s true, the algorithm stops completely. If
it’s false, the algorithm checks the next distance from x2 to x3 since it
hasn’t met it’s daily limit of d miles.
-If the sum of x1 to x2 and x2 to x3 = d. The the distance is added to
Gtotal. Then the algorithm checks to see if Gtotal = L. If that’s true, it
stops. If it’s false, the algorithm continues.
-If the sum of x1 to x2 and x2 to x3 < d, it computes the next distance.
In this case from x3 to x4 in order to see whether the new sum is strictly
≤ d. Then again checks to see if Gtotal = L.
1
-But if the sum of x1 to x2 and x2 to x3 d, we consider x2 the first
stopping point since we cannot drive over d miles. -The algorithm repeats the previous steps unless the total distance is met. Note that it’s
been constructed to check whether the sum is equal to L, in order to not
go over the overall required distance to be traveled. The algorithm also
verifies whether the daily distance covered is ≤ d
-This greedy approach continues to try to cover as much distance as possible, without going over d miles per day, and checking if Gtotal = L each
time a new distance is added.
Problem 2:
LOGIC OF T HE F OLLOW ING P ROOF: Let G represent the output of
the algorithm while O be the optimal solution to the problem. By way of contradiction, assume that G and O are not the same, such that O(L) returns a
smaller number, thus less stops and therefore more efficient. Similarly, let O[xi
]
and G[xi
] represent the set of stops along the way of each. At O[1], meaning
the first stop, the optimal algorithm certainly returns the optimal solution. Assuming 1 represents having traveled at most d without going over. Well G[1],
by construction also returns the most efficient solution of attaining d, but not
going over, and so currently the size of both lists is the same for G[1]=O[1].
Then assume that O[xn − 1] represents the set of all optimal solutions for the
given problem for the remaining number of necessary stops n. Since G[1]=O[1],
we can substitute that by saying O[n] − G[0]. By way of contradiction, assume
that there exists a C[n] which has less elements than O[n] such that C[n]+G[0]
< O, meaning C has less stops and is the best solution for the problem. But by
definition the set O has the minimum number of stops, for which the greedy algorithm attains the same number of values, thus the required contradiction. As
for if the value G[xi
] is not optimal, and xj is, then the algorithm then chooses
xj distance before stop, assuming it doesn’t break the rule of going over d. So
the number of stops G and O have have to be the same. Having s
Proof: Let O = {o1, o2, ..., on} be the set of optimal stops selected by the optimal solution. Let G = {g1, g2, ..., gm} be the set of stop selected by the greedy
algorithm developed. Since the optimal solution contains the least amount of
stops in order to reach destination L, n ≤ m. This results in the following lemma:
∀ 1≤mgi ≤ oi
Meaning that for any given value, letting that value be the i the any arbitrary
stopping point, the greedy algorithm finds less stops.
By way of induction let the base case be when i = 1. This means that gi
≤ oi
. Meaning the stop for the greedy algorithm came closer to a distance d
than the optimal solution. By way of contradiction, assume that gi oi
, but
this goes against the construction of the greedy algorithm since it was designed
to come as close to the distance d and not stop until it was either equal to it
or just under it. If gi oi
, then that would mean that the algorithm chose not
2
to keep going, which would be a contradiction to what was set to do. So the
greedy stoping point should be the same as o1.
Inductive Hypothesis: Assume ∀ 1≤k−1gi ≤ oi
Inductive Step: Show that gk ≤ ok
By way of contradiction, assume that gk ok. Then by the hypothesis, one
can say that gk−1 ≤ ok−1 → gk−1 ≤ f(ok). Meaning the optimal solution came
closer to the distance d in order to cover more distance and make less stops but
our greedy solution stopped and chose not to keep going. Thus the required
contradiction.
Since m = n by the previous lemma, then it is then only necessary to show
that the set of stops for the greedy algorithm contains the same number of elements such as the optimal algorithm; such that |G| = |O|.
Assume that |G| 6= |O|
Problem 3:
Problem Description: Find the best path from the starting node (C-Vile) s to
the end node (Montreal) t.
Inputs: Start nodes u and end nodes v within the graph G. Starting time, so
that the function f(u, v, t) returns the time it takes to travel from node u to v.
Outputs: Time t in milliseconds.
Assumptions: Nodes represents roads, such that from when referring to going
from one node to another it logically means taking a road in order to arrive
to another road. Time t is always positive and linear, such that if t1t2 then
f(u, v, t1) ≥ f(u, v, t2). Graph G represents the various path one can take from
s to t. Assume also that u and v are valid nodes and there exists a path within
the graph G that connects the nodes u and v.
Strategy: Apply Dijkstra’s Algorithm in order to find the shortest path from
the starting node s to the target node t.
Description: Apply Djikstra’s Algorithm in order to find the fastest path from
the starting node to the target node.
Description: Using Djikstra’s Algorithm, one can apply the same logic in order
to solve this problem. In this case, the weight between the nodes is time rather
than distance. Since the graph G contains the various paths from the C-Ville
node s to the target node t, Montreal, the algorithm can begin by assessing the
efficiency of the nodes in between the start node and end node. In order to do
that, the algorithm follows the following steps until it attains the most efficient
path:
- The algorithm begins only knowing node s, the starting vertex. From
the this node, the algorithm starts to asses the efficiency of all of the
neighboring nodes, i.e. the algorithm sees which roads are faster and
which ones are slower in order to arrive at node t. For the algorithm
to do that, every unknown node is set an upper bound of t = ∞. For
3
example, let s1 denote the following node such that f(s, s1, t) = k, for
some millisecond value of k. Since we know that s1 6= s, then k ≥ 0.
Similarly, since know that the distance from one road to another cannot
be infinate, k < ∞. Thus k must be in between such that 0 ≤ k < ∞.
Setting this bound allows us to then store the time it takes from the
starting point s to the following node s1 into an array, so that we keep
track of the effeciency of each road.
- Repeating the previous step for all of the neighboring nodes, storing all
of these time values in an array of times, the algorithm can then start
to evaluate which is the fastest path. In order to do that, the algorithm
calculates the times from node s to node si
.
- In the case in which we know a previous time ti from node s, our starting node to another node si
, since our algorithm is greedy in nature and
wishes to find the fastest way to s1, we must update our path so that
only the fastest times are considered. In order to do so, we go through
the array which contains the times for all of the known nodes (roads) and
we compare the times tracked with any new times recorded as new nodes
are discovered. At each edge, the algorithm compares the previous time
and see whether the new path returns a shorter path, such that if tprev
tcurrent, both computed by f(s, si
, t), except tcurrent is shorter due to
having taken another road which is faster, then we update the time in
our array. In order to update it, we simply find the spot in our array
which returns the time from s to si and change t = tcurrent. Deleting
also the slower time.
- The algorithm continues to do this for every unknown node until we
check whether the next node is the end node t. If so, we stop and calculate the fastest time in order to reach t by simply seeing which nodes,
meaning roads, had the smallest weighted edges (times).
When using an array in order to keep the weighted edges and their
values, the total run time of Dijkstra’s algorithm is O(v
2
), where v stands
for the number of edges.
Problem 4:
Proof: Let set S = {s0, s1, s2, ..., sn−1} contain all of the nodes that the algorithm finds in order to reach node t. The time it takes on that node (road)
is given by f(s, si
, t), where si
is an element with S. By way of induction, we
prove that f(s, si
, t) returns the smallest time from s to si such that all of the
fastest roads are taken, and so the algorithm’s solution is equal to the optimal
solution of this given problem.
Base Case: The time it takes from node s to s0 is optimal is s0 is the starting
road in C-Ville for our algorithm. Thus the time from where we are to where
we are is 0 milliseconds.
Inductive Hypothesis: ∀ i ≤ k − 1, function f() is minimal.
Inductive Step: Assume that function f() returns a minimal time for sk such
that f(s, sk, t) is the minimal solution to the road sk from s, and so the fastest
route. By definition, the time to sk is given by: f(s, sk, t) = f(s, si
, t) + cost(e).
4
Since we assumed that the algorithm returns the fastest time in up to the road
i, ∀ i ≤ k − 1, then by way of contradiction, assume that the time from si to k
is not optimal, in order to prove it is.
Assume that the time to sk is not optimal, meaning for f(s, sk, t), ∃ sk0 for
which the route is faster. Such that, the following is also true: f(s, sj , tj ) +
cost(e
0
) + δ < f(s, si
, ti)+cost(e), implting that j ¡ i, meaning the times for the
first one is faster than the second one. But since δ ≤ 0, the best δ can be is 0.
So if δ = 0, then f(s, sj , tj ) + cost(e
0
) < f(s, si
, ti)+cost(e), thus the required
contradiction. Since Dijkstra’s algorithm selects the most efficient path, in this
case based on time from one node to another node, it the above statement
cannot be strictly less than. So the algorithm is in fact optimal.
Problem 5:
1. Yes, every MST of G is an Elite T ree by definition. A bottleneck edge is
the the most expensive edge on a spanning tree T. Given that T represents
any arbitrary spanning tree in G, T could very well be a minimum spanning
tree of G. Assuming that it is, let T = {t0, t1, t2, ..., tn − 1} where ti was the
most expensive edge of of that tree. Then ∀ t values in T, T contains only the
smallest edges connecting two nodes. Then T is indeed an Elite T ree since
T contains the minimum value possible bottleneck edge, which by construction
used to be ti but since reducing that edge, T is a minnimum spanning tree.
2. No, not every Elite T ree of G is an MST. An Elite T ree by definition
just contains the minimum bottleneck edge of an arbitrary spanning tree T.
Since T could contain other non optimal edges, it is not an MST. For example,
let T = {5, 9 , 5}, three edges that connect 4 nodes within G. If we let the
MST of G equal {5, 4, 2}, such that there are two edges more optimal than the
ones in T. The Elite T ree would be a tree that reduces the bottleneck edge of
T, meaning the edge 9, which is the most expensive edge. Then the Elite T ree
= {5, 4, 5}, satisfying the criteria that an Elite T ree contains the minimum
bottleneck edge of a given spanning tree T within G.
5