Greedy: Slate the greedy selection criterion for the Event Scheduling Problem th
ID: 3816869 • Letter: G
Question
Greedy: Slate the greedy selection criterion for the Event Scheduling Problem that we studied in the course (i.e., compute a max cardinality subset C of a given set S of intervals so that two intervals in C overlap). Dynamic Programming: State the DP recurrence formula for the Matrix Chain Multiplication Problem that we studied in the course. c) Let G be a graph in which all edge weights are positive integers. Let G' be the same as G where the only change made is that edge weights are squared i. (6%) Let T be an MST of G. Is T also an MST of G'? Prove or give a counter-example. Let P be a shortest path between nodes s and t in G. Is P also a shortest path between nodes s and t in G'? Prove or give a counter-example.Explanation / Answer
a) Event scheduling problem
Any event has two time stamps, start timestamp and end timestamp. When number of events have to be scheduled on to particular resource, we need to take care that no two events are no overlapping, that is to say second event cannot be scheduled while first running. Given a set of jobs S with their start time and end time, find out largest set R such that all events in R are mutually compatible. Two events are compatible if they do not overlap. This problem is known as event scheduling problem.
The selection criteria for the job are following three criteria:
1. We take job with earliest start time first.
2. We take job with earliest end time first.
3. We take job with minimum number of overlapping jobs.
4. We take the shortest job first.
b) Matrix chain multiplication
-Let M[i,j] represent the number of multiplications required for matrix product Ai×.....×Aj
For 1<=i<=j<n
-M[i,i]=0 since no product is required
-The optimal solution of Ai × Aj must break at some point, k, with i k < j
Thus, M[i,j]=M[i,k]+M[k+1,j]+d(i1)d(k)d(j)
-Thus, M[i,j]= {0, if i=j
{min(ik<j) { M[i,k] + M[k+1,j] + d(i1)d(k)d(j) }, if i<j
c) MST & Shortest path
(i) Squaring the weights of the edges in a weighted graph will not change the minimum spanning tree.
Proof:-
-Assume the opposite to obtain a contradiction.
-If the minimum spanning tree changes then at least one edge from the old graph G in the old minimum spanning tree T must be replaced by a new edge in tree T’ from the graph G’ with squared edge weights.
-The new edge from G’ must have a lower weight than the edge from G. This implies that there exists some weights C1 and C2 such that C1 < C2 and C12 >= C22.
-This is a contradiction.
(ii) Squaring the weights of the edges in a directed graph may change the shortest path between two points.
The reason is,
- there may be different number of edges in different paths from s to t. For example, let shortest path be of weight 15 and has 5 edges. Let there be another path with 2 edges and total weight 25. The weight of the shortest path is increased by 5*10 and becomes 15 + 50. Weight of the other path is increased by 2*10 and becomes 25 + 20. So the shortest path changes to the other path with weight as 45.
The Minimum Spanning Tree doesn’t change. Remember the Kruskal’s algorithm where we sort the edges first. IF we increase all weights, then order of edges won’t change.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.