What is a greedy algorithm?
The greedy:
- builds the solution in steps
- In every step it adds an element from the input to the solution, according to some choosing rule
- The algorithm _does not regret its choices._
What is the template for a greedy algorithm?
Input:
- S={1,…n} events.
Initialization:
- empty set G
step:
- While S is not empty:
- Choose i from S according to some rule
- Add i to G
- Remove from S all the events which intersect with i(including i itself)
End:
- Return G
What is the template for a mathematical proof of greedy algorithms?
- Observation: how the algorithm provides a legal solution?
- Claim: let G be the solution output by the algorithm and O be the optimum solution. If G is different from O, then we can tweak O to get another O* that is different from O and strictly better than O.
- we prove it by choosing the smallest index by which Oi not equals Ki, then we’ll change Oi to be Si(greedy choice at the ith step), and then show that this leads to an even better solution.(this involves observations regarding the problem).
greedy algorithm proof template:
*
How the algorithm(shortest end time) for the activities problem is proved to be correct?
- Observation:
- the greedy creates a legal solution.
- Explanation:
- it removes all intersection with i in S.
- claim:
- In every step of the algorithm there exists an optimal solution O which contains G.
- proof by induction:
- Assumption holds for the (k-1)th step. There exists such O
- step: let i be the kth choice. There are two cases:
- i belongs to O - we’re done.
- i does not belong to O.
- we want to compre a choice from O/G(k-1) to i
- We compare by the choosing rule
- let j be the activity with the smallest end time in O/G(K-1)
- why O/G(k-1) must have an element?
- Because Gk is a legal solution according to the observation, and O is a maximal one.
- If O/G(k-1) is empty, it can’t be maximal
- O*=(O{j}) U {i} contains G.
- O{j}) contains G(k-1) and {i} contains i.
- O* is of maximal size
- O is of maximal size, so is O*
- O* is legal
- Gk is legal so i does not intersect with G(k-1)
- Define A= O{j}\G(k-1).
- O is legal - thus j does not intersect with G(k-1) thus at the kth step j was part of S. The fact i was chosen shows the end time of i is earlier than the end time of j.
- O is legal, thus any activity in A starts not before j is finished. Therefore, any activity in A starts not before i is finished.
- we want to compre a choice from O/G(k-1) to i
- Correctness statement:
- The algorithm returns a legal set of maximal size.
- Proof:
- According to the claim, when S is empty, there exists a solution O which contains G. If S is empty it means there is no element in the input which does not intersect with any of the elements of G. That means there can’t be in O also an elements which intersects with G, thus G=O.
Activities problem S
Legal solution:
- A division of S into sets.
- Find a legal solution of minimum number of sets.*
Show an algorithm for this problem.
Initialization:
- k = 1
- C1 is the empty set
- Sort S by start time
loop: for all i in the sorted S
- if i can be added to some set Ci, do it
- else, open a new set: k=k+1 , C{k} = {i}.
Activities problem(division)
what is a depth of an instance of the problem?
It is the maximal number of sections which intersect.
Activities problem(division)
Stages in the proof:
- What is the observation?
- In any legal solution, the number of sets is greater or equal to the depth.*
- Explanation:*
- Assume the number of sets is smaller than the depth. Contradiction by the peigion principal.
Activities problem(division)
Stages in the proof:
- What is the correctness statement?
The algorithm returns a legal solution with minimum number of sets.
Activities problem(division)
Stages in the proof:
- What is the helping statement?
The number of sets the algorithm opens is smaller or equal to the depth of the instance for the problem.
Activities problem(division)
Stages in the proof:
- What is the proof of the correctness statement using the helping statement?
Observation: the algorithm returns a legal solution
- All the actvities are distributed
- We never assign activity such that it intersects with one of the elements in its set.
Proof:
- Assume the algorithm open d sets.
- By helping statement : d <= depth
- By observation, depth <= any legal solution
- we get: d<=depth<any></any>
- That is, d is minimal.
Activities problem(division)
Stages in the proof:
- What is the proof of the helping statement?
- Let i the the elements which makes the algorithm create the last set d.*
- That is, i satisfies two traits:*
- There exists x in every set Ck ,[1,d-1], s.t.:
- start time of i < end time of x.
- According to the sorting:
- start time of x <= start time of i
That means, there are d-1 elements which intersect with i, and because i’s length is positive, there is a point in which all d elements intersects. Thus, the depth is at least d.
Activities problem(division)
How is it implemented:
- Before the implementation we use two observations. what are they?
- i can be added to Cj if and only if Fj<=Si
- Si - start time of i
- Fj - maximal end time of Cj
- There exists such set Cj for whichi Fj<=Si if and only if Min {Fj}<=Sj.
- That is, we should look for the minimal Fj and check this condition only.
Activities problem(division)
How is it implemented:
- Which data structure helps us keep Min{Fj}?
- What is its initilized value?
- How do we sort the activities
- Minimum heap Q
- {Cj, Fj} - each set and its maximal end time
- Initialized to:
- Q = {emptyset, -infinity}
- Sorting by start time
Activities problem(division)
How is it implemented:
- What is the loop part of the algorithm?
Loop:
- For each activity i:
- ExtractMin to get (Cj,Fj)
- if Fj<=Si then:
- Cj = Cj U {i}
- Fj=Fi
- IncreaseKey(Q,(Cj,Fj))
- else
- open a new set C = {i}
- Insert (Q, (C,Fi))
End:
- Return all the sets in Q.
Heap:
- What is the run-time for:
- Extract-Min
- Insert
- Increase-Key
O(log(n))
