3. Greedy Algorithms Flashcards
What is interval scheduling?
For a set of requests {1, 2, …, n}, the ith request corresponds to an interval of time starting at si and finishing at fi.
A subset of requests is compatible if no two of them overlap in time.
Our goal is to accept as large a compatible subset as possible (maximum size will be called optimal)
What is a greedy algorithm?
An algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.
Explain a concrete application of a greedy algorithm to the interval scheduling problem.
The basic idea in a greedy algorithm for interval scheduling is to use some simple rule to select a first request i1.
Once a request i1 is accepted, we reject all requests that are not compatible with i1.
We then select the next request i2 to be accepted, rejecting all requests that are not compatible with i2.
This continues until we run out of requests.
Greedy algo for Interval Scheduling Problem (ISP) pseudocode
Initially let R be the set of all requests, and A be empty
While R is not yet empty:
Choose a request i w/in R that has smallest finishing time
Add request i to A
Delete all requests from R that are not compatible with request i
Endwhile
Return the set A as the set of accepted requests
Greedy algo for Interval Scheduling Problem (3.1)
A is a compatible set of requests
This is handled by the algorithm specifications. By rejecting all incompatible requests, the only thing left are compatible requests.
Interesting note: The returned set A is one possible optimal set, but not necessarily the only one. Meaning, we can’t directly state that A is optimal by A=O, because O could have many correct permutations. We can, however, show that |A| = |O|, because “optimal” means greatest number of possible requests are satisfied, and despite the ability for specific requests to vary, the total number of requests will not.
Greedy algo for Interval Scheduling Problem (3.2)
For all indices r <= k we have fi(r) <= fj(r)
Induction: For r = 1 the statement is clearly true: the algo starts by selecting the request i1 with minimum finish time.
Now let r > 1. We assume as our induction hypothesis that the statement is true for r-1, and we will try to prove it for r.
In the following figure, we use the lower line to indicate the requests j(r-1) and jr in the optimal schedule, and the upper line to indicate the request i(r-1) from the algo’s schedule.
———-
———– ———
By the induction hypothesis we have fi(r-1)
Why is the runtime of the greedy algo for ISP O(nlogn)?
First the requests are sorted from earliest finish time to latest [O(nlogn) - mergesort]
[Dont yet understand the rest. See pg 62 of textbook]
Two possible variations (complications) of the interval scheduling problem
- Rather than handle scheduling for a single resource (maybe a lecture hall), we could imagine having many similar lecture halls, where each one is equally acceptable at a specified time.
- Rather than consider only the maximal number of satisfied requests, we could ascribe weights of importance to each of the requests. This would change the definition of “optimal” to be the sum of the weights of all satisfied requests.
Greedy algo for Minimum Stopping Points (MSP) (3.4)
Let R = {Xp1, …, Xpk} denote the set of stopping points chosen by the greedy algo, and suppose by way of contradiction that there is a valid set of stopping points S = {Xq1, …, Xqm} with m = Xqj
Prove by induction on j. The case j = 1 follows directly from the definition of the greedy algorithm - my friends travel as long as possible on the first day before stopping.
Now let j>1 and assume that the claim is true for all i
Greedy algo for MSP (3.5)
The greedy algorithm produces a valid set of stopping points of minimum possible size.
(3.4) implies in particular that Xqm
Why is DFS a special case of the explore algorithm?
?
