Lecture 2:
Greedy algorithms
William Umboh
School of Computer Science
The University of Sydney
Page 1
General techniques in this course
– Greedy algorithms [today]
– Divide & Conquer algorithms [12 Mar]
– Dynamic programming algorithms [19 and 26 Mar] – Network flow algorithms [2 and 9 Apr]
The University of Sydney
Page 2
Greedy algorithms
A greedy algorithm is an algorithm that follows the problem solving approach of making a locally optimal choice at each stage with the hope of finding a global optimum.
Greedy algorithms can be some of the simplest algorithms to implement, but they’re often among the hardest algorithms to design and analyse.
The University of Sydney
Page 3
Greedy: Overview
Consider problems that can be solved using a greedy approach:
– Interval scheduling/partitioning – Scheduling to minimize lateness – Shortest path
– Minimum spanning trees
The University of Sydney
Page 4
How to design algorithms
Step 1: Understand problem
Step 4: Better understanding of problem
Step 2: Start with simple alg. Step 5: Improved alg.
Step 3: Does it work? Is it fast?
No Yes
Problem
Algorithm
Analysis
Useful strategy:
– Try some simple examples to get
feel for algorithm.
– If none of them break algorithm,
see if there’s underlying structural property we can use to prove correctness.
The University of Sydney
Page 5
DONE!
Interval Scheduling
The University of Sydney Page 6
Interval Scheduling
– Interval scheduling.
– Input: Set of n jobs. Each job i starts at time sj and finishes at time fj.
– Two jobs are compatible if they don’t overlap in time.
– Goal: find maximum subset of mutually compatible jobs.
b
a
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 11 The University of Sydney
Time
Page 7
Interval Scheduling
– Interval scheduling.
– Input: Set of n jobs. Each job i starts at time sj and finishes at time fj.
– Two jobs are compatible if they don’t overlap in time.
– Goal: find maximum subset of mutually compatible jobs.
b
a
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 11 The University of Sydney
Time
Page 8
Interval Scheduling: Greedy Algorithms
Greedy template. Consider jobs in some order. Take each job provided it is compatible with the ones already taken.
– [Earliest start time] Consider jobs in ascending order of start time sj.
The University of Sydney Page 9
Interval Scheduling – [Earliest start time]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 10
Interval Scheduling – [Earliest start time]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 11
Interval Scheduling – [Earliest start time]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
A
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 12
Interval Scheduling – [Earliest start time]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
A
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 13
Interval Scheduling – [Earliest start time]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
A
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 14
Interval Scheduling – [Earliest start time]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
A
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 15
Interval Scheduling – [Earliest start time]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
A
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 16
Interval Scheduling – [Earliest start time]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
A
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 17
Interval Scheduling – [Earliest start time]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
A
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 18
Interval Scheduling – [Earliest start time]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
A
G
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 19
Interval Scheduling – [Earliest start time]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
A
G
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 20
Interval Scheduling: Greedy Algorithms
Greedy template. Consider jobs in some order. Take each job provided it is compatible with the ones already taken.
breaks [Earliest start time]
The University of Sydney Page 21
Interval Scheduling: Greedy Algorithms
Greedy template. Consider jobs in some order. Take each job provided it is compatible with the ones already taken.
– [Earliest start time] Consider jobs in ascending order of start time sj.
– [Shortest interval] Consider jobs in ascending order of interval length fj – sj.
The University of Sydney Page 22
Interval Scheduling – [Shortest interval]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 23
Interval Scheduling – [Shortest interval]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
C
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 24
Interval Scheduling – [Shortest interval]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
C
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 25
Interval Scheduling – [Shortest interval]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
C
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 26
Interval Scheduling – [Shortest interval]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
C
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 27
Interval Scheduling – [Shortest interval]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
C
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 28
Interval Scheduling – [Shortest interval]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
C
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 29
Interval Scheduling – [Shortest interval]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
C
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 30
Interval Scheduling – [Shortest interval]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
C
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 31
Interval Scheduling – [Shortest interval]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
C
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 32
Interval Scheduling: Greedy Algorithms
Greedy template. Consider jobs in some order. Take each job provided it is compatible with the ones already taken.
breaks [Earliest start time] breaks [Shortest interval]
The University of Sydney Page 33
Interval Scheduling: Greedy Algorithms
Greedy template. Consider jobs in some order. Take each job provided it is compatible with the ones already taken.
– [Earliest start time] Consider jobs in ascending order of start time sj.
– [Shortest interval] Consider jobs in ascending order of interval length fj – sj.
– [Fewest conflicts] For each job, count the number of conflicting jobs cj. Schedule in ascending order of conflicts cj.
The University of Sydney Page 34
Interval Scheduling – [Fewest Conflicts]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 35
Interval Scheduling – [Fewest Conflicts]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 36
Interval Scheduling – [Fewest Conflicts]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 37
Interval Scheduling – [Fewest Conflicts]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
B
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 38
Interval Scheduling – [Fewest Conflicts]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
B
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 39
Interval Scheduling – [Fewest Conflicts]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
B
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 40
Interval Scheduling – [Fewest Conflicts]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
B
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 41
Interval Scheduling – [Fewest Conflicts]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
B
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 42
Interval Scheduling – [Fewest Conflicts]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
B
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 43
Interval Scheduling – [Fewest Conflicts]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
B
E
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 44
Interval Scheduling – [Fewest Conflicts]
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
B
E
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 45
Interval Scheduling: Greedy Algorithms
Greedy template. Consider jobs in some order. Take each job provided it is compatible with the ones already taken.
breaks [Earliest start time] breaks [Shortest interval]
breaks [Fewest conflicts]
The University of Sydney Page 46
Interval Scheduling: Greedy Algorithms
Greedy template. Consider jobs in some order. Take each job provided it is compatible with the ones already taken.
– [Earliest start time] Consider jobs in ascending order of start time sj.
– [Shortest interval] Consider jobs in ascending order of interval length fj – sj.
– [Fewest conflicts] For each job, count the number of conflicting jobs cj. Schedule in ascending order of conflicts cj.
– [Earliest finish time] Consider jobs in ascending order of finish time fj.
The University of Sydney Page 47
Interval Scheduling
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 48
Interval Scheduling
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
B
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 49
Interval Scheduling
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
B
C
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 50
Interval Scheduling
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
AB
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 51
Interval Scheduling
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
B
E
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 52
Interval Scheduling
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
B
DE
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 53
Interval Scheduling
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
B
E
F
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 54
Interval Scheduling
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
B
E
G
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 55
Interval Scheduling
A
B
C
D
E
F
G
H
0 1 2 3 4 5 6 7 8 9 10 11
Time
B
E
H
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney Page 56
Interval Scheduling: Greedy Algorithm
Only [Earliest finish time] remains to be tested.
– Greedy algorithm. Consider jobs in increasing order of finish time.
Take each job provided it is compatible with the ones already taken.
Sort jobs by finish times so that f1 £ f2 £ … £ fn. jobs selected
A®
for j = 1 to n {
if (job j compatible with A) A ¬ A È {j}
}
return A
– Implementation. O(n log n).
– Rememberjobj*thatwasaddedlasttoA. – Job j is compatible with A if sj 3 fj*.
The University of Sydney Page 57
Interval Scheduling: Analysis
High-Level General Idea:
At each step of Greedy, there is an optimal solution consistent with Greedy’s choices so far
One way to do this is by using an exchange argument.
1. Define your greedy solution.
2. Compare solutions. If Xgreedy 1 Xopt, then they must differ in some specific way.
3. Exchange Pieces. Transform Xopt to a solution that is “closer” to Xgreedy and prove cost doesn’t increase.
4. Iterate. By iteratively exchanging pieces one can turn Xopt into Xgreedy without impacting the quality of the solution.
The University of Sydney Page 58
Interval Scheduling: Analysis
– Theorem: Greedy algorithm [Earliest finish time] is optimal. – Proof: (by contradiction)
– Assume greedy is not optimal, and let’s see what happens.
– Let i1, i2, … ik denote the set of jobs selected by greedy.
– Let J1, J2, … Jm denote the set of jobs in an optimal solution with i1 = J1, i2 = J2, …, ir = Jr for the largest possible value of r.
Greedy: OPT:
job ir+1 finishes before Jr+1
i1
i1
ir
ir+1
J1
J2
Jr
Jr+1
…
…
The University of Sydney
Page 59
Why not replace job Jr+1 with job ir+1?
Interval Scheduling: Analysis
– Theorem: Greedy algorithm [Earliest finish time] is optimal. – Proof: (by contradiction)
– Assume greedy is not optimal, and let’s see what happens.
– Let i1, i2, … ik denote the set of jobs selected by greedy.
– Let J1, J2, … Jm denote the set of jobs in an optimal solution with i1 = J1, i2 = J2, …, ir = Jr for the largest possible value of r.
Greedy: OPT’:
The University of Sydney
solution still feasible and optimal
and agrees with larger prefix of greedy’s solution, contradicting definition of r
Page 60
job ir+1 finishes before Jr+1
i1
i1
ir
ir+1
…
J1
J2
Jr
Jr+1
…
Exchange argument!
Interval Scheduling: Recap of Exchange Argument
Greedy: OPT:
– We have an optimal solution that is “closer” to the greedy solution.
– Start the argument over again, but now the first (r+1) elements of the greedy solution and the optimal solution are identical.
– Continue iteratively until the optimal solution is transformed into the greedy solution without increasing the cost.
i1
i1
ir
ir+1
…
J1
J2
Jr
Jr+1
…
The University of Sydney Page 68
Interval Scheduling
There exists a greedy algorithm [Earliest finish time] that computes an optimal solution in O(n log n) time.
The University of Sydney Page 69
Scheduling to Minimize Lateness
The University of Sydney Page 70
Scheduling to Minimizing Lateness
– Minimizing lateness problem. [No fix start time]
– Single resource processes one job at a time.
– Job i requires ti units of processing time and is due at time di.
– Due times are unique
– Ifistartsattimesi,itfinishesattimefi =si +ti.
– Lateness: !i =max{0, fi -di }.
– Goal: schedule all jobs to minimize maximum lateness L = max !j.
1
2
3
4
5
6
ti
3
2
1
4
3
2
di
6
8
9
10
14
15
– Ex: lateness = 0
jobs
processing time due time
lateness = 0
lateness = 0
lateness = 2
lateness = 0
max lateness = 5
12 13 14 15
d3 = 9
d2 = 8
d6 = 15
d1 = 6
d5 = 14
d4 = 10
0 1 2 3 4 5 6 7 8 9 10 11
The University of Sydney
Page 71
Minimizing Lateness: Greedy Algorithms
Greedy template. Consider jobs in some order.
– [Shortest processing time first] Consider jobs in ascending order of processing time ti.
– [Smallest slack] Consider jobs in ascending order of slack di – ti.
– [Earliest deadline first] Consider jobs in ascending order of deadline di.
The University of Sydney Page 72
Minimizing Lateness: Greedy Algorithms
– Greedy template. Consider jobs in some order.
– [Shortest processing time first] Consider jobs in ascending order of
processing time ti.
counterexample
– [Smallest slack] Consider jobs in ascending order of slack di – ti. counterexample
The University of Sydney
Page 73
ti
1
1
2
10
di
100
10
1
2
ti
1
10
di
2
10
Minimizing Lateness: Greedy Algorithm
– Greedy algorithm. [Earliest deadline first]
Sortnjobsbydeadlinesothatd1 £ d2 £ … £ dn
t¬0
for j = 1 to n
Assign job j to interval [t, t + tj] sj ¬ t, fj ¬ t + tj
t ¬ t + tj
output intervals [sj, fj]
jobs
processing time due time
1
2
3
4
5
6
ti
3
2
1
4
3
2
di
6
8
9
10
14
15
The University of Sydney
Page 74
Minimizing Lateness: Greedy Algorithm
– Greedy algorithm. [Earliest deadline first]
Sortnjobsbydeadlinesothatd1 £ d2 £ … £ dn
t¬0
for j = 1 to n
Assign job j to interval [t, t + tj] sj ¬ t, fj ¬ t + tj
t ¬ t + tj
output intervals [sj, fj]
jobs
processing time due time
d1 = 6
0 1 2 3 4 5 6 7 8 9 10 11
12 13 14 15
1
2
3
4
5
6
ti
3
2
1
4
3
2
di
6
8
9
10
14
15
The University of Sydney
Page 75
Minimizing Lateness: Greedy Algorithm
– Greedy algorithm. [Earliest deadline first]
Sortnjobsbydeadlinesothatd1 £ d2 £ … £ dn
t¬0
for j = 1 to n
Assign job j to interval [t, t + tj] sj ¬ t, fj ¬ t + tj
t ¬ t + tj
output intervals [sj, fj]
jobs
processing time due time
0 1 2 3 4 5 6 7 8 9 10 11
12 13 14 15
1
2
3
4
5
6
ti
3
2
1
4
3
2
di
6
8
9
10
14
15
d1 = 6
d2 = 8
The University of Sydney
Page 76
Minimizing Lateness: Greedy Algorithm
– Greedy algorithm. [Earliest deadline first]
Sortnjobsbydeadlinesothatd1 £ d2 £ … £ dn
t¬0
for j = 1 to n
Assign job j to interval [t, t + tj] sj ¬ t, fj ¬ t + tj
t ¬ t + tj
output intervals [sj, fj]
jobs
processing time due time
0 1 2 3 4 5 6 7 8 9 10 11
12 13 14 15
1
2
3
4
5
6
ti
3
2
1
4
3
2
di
6
8
9
10
14
15
d1 = 6
d2 = 8
d3 = 9
The University of Sydney
Page 77
Minimizing Lateness: Greedy Algorithm
– Greedy algorithm. [Earliest deadline first]
Sortnjobsbydeadlinesothatd1 £ d2 £ … £ dn
t¬0
for j = 1 to n
Assign job j to interval [t, t + tj] sj ¬ t, fj ¬ t + tj
t ¬ t + tj
output intervals [sj, fj]
jobs
processing time due time
max lateness = 1
1
2
3
4
5
6
ti
3
2
1
4
3
2
di
6
8
9
10
14
15
d1 = 6
d2 = 8
d3 = 9
d4 = 10
0 1 2 3 4 5 6 7 8 9 10 11
12 13 14 15
The University of Sydney
Page 78
Minimizing Lateness: Greedy Algorithm
– Greedy algorithm. [Earliest deadline first]
Sortnjobsbydeadlinesothatd1 £ d2 £ … £ dn
t¬0
for j = 1 to n
Assign job j to interval [t, t + tj] sj ¬ t, fj ¬ t + tj
t ¬ t + tj
output intervals [sj, fj]
jobs
processing time due time
max lateness = 1
1
2
3
4
5
6
ti
3
2
1
4
3
2
di
6
8
9
10
14
15
d1 = 6
d2 = 8
d3 = 9
d4 = 10
d5 = 14
0 1 2 3 4 5 6 7 8 9 10 11
12 13 14 15
The University of Sydney
Page 79
Minimizing Lateness: Greedy Algorithm
– Greedy algorithm. [Earliest deadline first]
Sortnjobsbydeadlinesothatd1 £ d2 £ … £ dn
t¬0
for j = 1 to n
Assign job j to interval [t, t + tj] sj ¬ t, fj ¬ t + tj
t ¬ t + tj
output intervals [sj, fj]
jobs
processing time due time
max lateness = 0
1
2
3
4
5
6
ti
3
2
1
4
3
2
di
6
8
9
10
14
15
d1 = 6
d2 = 8
d3 = 9
d4 = 10
d5 = 14
d6 = 15
0 1 2 3 4 5 6 7 8 9 10 11
12 13 14 15
The University of Sydney
Page 80
Algorithm ignores processing time!
Minimizing Lateness: No Idle Time
– Observation: There exists an optimal schedule with no idle time.
d = 4 d = 6 d = 12
0 1 2 3 4 5 6 7 8 9 10 11
0 1 2 3 4 5 6 7 8 9 10 11
– Observation: The greedy schedule has no idle time. The University of Sydney
Page 81
d=4
d=6
d = 12
Minimizing Lateness: Inversions
– Definition: An inversion in schedule S is a pair of jobs i and k such that i < k (by deadline) but k is scheduled before i.inversion– Observation: Greedy schedule has no inversions. Moreover, Greedy is only such schedule (by uniqueness of deadlines).– Observation: If a schedule (with no idle time) has an inversion, it has one with a pair of inverted jobs scheduled consecutively.k i The University of Sydney Page 82 Minimizing Lateness: Inversions– Definition: An inversion in schedule S is a pair of jobs i and k such that i < k (by deadline) but k is scheduled before i.inversionfif’jk i before swap after swap i k – Claim: Swapping two adjacent, inverted jobs reduces the number of inversions by one and does not increase the max lateness.The University of Sydney Page 83 Minimizing Lateness: Inversions– Definition:AninversioninscheduleSisapairofjobsiandksuch that i < k (by deadline) but k is scheduled before i.before swap after swapinversionfif‘kk ii k – Claim: Swapping two adjacent, inverted jobs reduces the number of inversions by one and does not increase the max lateness.– Proof: Let ! be the lateness before the swap, and let !’ be the lateness after the swap.– !‘x =!x forallx1i,k – !’i £ !i– Ifjobkislate: `0k = fk0 dk = fi dk fi di = `idefinition (i finishes at time fi) (i < k) (definition)The University of SydneyPage 84 Minimizing Lateness: Analysis of Greedy Algorithm– Theorem: Greedy schedule S is optimal.– Proof: Define S* to be an optimal schedule that has the fewest number of inversions, and let’s see what happens.– Can assume S* has no idle time.– If S* has no inversions, then S = S*.– If S* has an inversion, let i-k be an adjacent inversion.• swapping i and k does not increase the maximum lateness and strictly decreases the number of inversions• this contradicts definition of S* ■The University of SydneyPage 85 Minimizing LatenessThe University of SydneyPage 86There exists a greedy algorithm [Earliest deadline first] that computes the optimal solution in O(n log n) time.What if deadlines are not unique?Can show that all schedules with no idle time and no inversions have the same lateness (p.g. 128 of textbook) Interval PartitioningThe University of Sydney Page 87 Interval Partitioning– Interval partitioning.– Lecture i starts at si and finishes at fi. Assume integers.– Goal: find minimum number of classrooms to schedule all lectures so that no two occur at the same time in the same room.– Ex: This schedule uses 4 classrooms to schedule 10 lectures. cej dgbha fi 9 9:30 10 10:30 11 11:30 12 12:30 1 1:30 2 2:30 3 3:30 4 4:30TimeThe University of Sydney Page 88 Interval Partitioning– Interval partitioning.– Lecture i starts at si and finishes at fi.– Goal: find minimum number of classrooms to schedule all lectures so that no two occur at the same time in the same room.– Ex: This schedule uses only 3. cdfj bgi aeh 9 9:30 10 10:30 11 11:30 12 12:30 1 1:30 2 2:30 3 3:30 4 4:30TimeThe University of Sydney Page 89 Interval Partitioning: Lower bound– Definition: The depth of a set of open intervals is the maximum number that contain any given time.– Observation: Number of classrooms needed 3 depth.– Example: Depth of schedule below is 3 Þ schedule below is optimal.(a, b, c all contain 9:30) – Question: Does there always exist a schedule equal to depth of intervals? cdfj bgi aeh The University of SydneyPage 909 9:30 10 10:30 11 11:30 12 12:30 1 1:30 2 2:30 3 3:30 4 4:30Time Interval Partitioning: Greedy Algorithm– Greedy algorithm. Consider lectures in increasing order of start time: assign lecture to any compatible classroom. Sort intervals by starting time so that s1 £ s2 £ … £ sn. d ¬ 0 number of allocated classroomsfor i = 1 to n { if (lecture i is compatible with some classroom k)schedule lecture i in classroom kelseallocate a new classroom d + 1 schedule lecture i in classroom d + 1 d¬d+1} The University of Sydney Page 91 Interval Partitioning: Greedy Algorithm– Greedy algorithm. Consider lectures in increasing order of start time: assign lecture to any compatible classroom. Sort intervals by starting time so that s1 £ s2 £ … £ sn.d ¬ 0 number of allocated classroomsfor i = 1 to n { if (lecture i is compatible with some classroom k)schedule lecture i in classroom kelseallocate a new classroom d + 1 schedule lecture i in classroom d + 1 d¬d+1}– Implementation. O(n log n).– Foreachclassroomk,maintainthefinishtimeofthelastjobadded. – Keeptheclassroomsinapriorityqueue.The University of SydneyPage 92 Interval Partitioning: Greedy Analysis– Observation: Greedy algorithm never schedules two incompatible lectures in the same classroom so it is feasible.– Theorem: Greedy algorithm is optimal.– Proof:– d = number of classrooms that the greedy algorithm allocates.– Classroom d is opened because we needed to schedule a job, say i, that is incompatible with all d-1 other classrooms.– Since we sorted by start time, all these incompatibilities are caused by lectures that start no later than sj. just after– Thus, we have d lectures overlapping at time [sj ,sj + 1]. time si– Key observation Þ all schedules use 3 d classrooms.■ The University of Sydney Page 93 Interval PartitioningThere exists a greedy algorithm [Earliest starting time] that computes the optimal solution in O(n log n) time.The University of Sydney Page 94 Greedy Analysis Strategies– Exchange argument. Gradually transform any solution to the one found by the greedy algorithm without hurting its quality.– Structural. Discover a simple “structural” bound asserting that every possible solution must have a certain value. Then show that your algorithm always achieves this bound.The University of Sydney Page 95 Minimum Spanning TreeThe University of Sydney Page 96 Minimum Spanning Tree– Minimum spanning tree (MST). Given a connected graph G = (V, E) with real-valued edge weights ce, an MST is a subset of the edges T Í E such that T is a spanning tree whose sum of edge weights is minimized. 4 24 4 62396 9 1618511 5118 14 7 8 7 1021G = (V, E)T, SeÎT ce = 50– Cayley’s Theorem. There are nn-2 spanning trees of Kn. can’t solve by brute force The University of SydneyPage 97 ApplicationsMST is fundamental problem with diverse applications. – Network design.– telephone, electrical, hydraulic, TV cable, computer, road – Approximation algorithms for NP-hard problems.– traveling salesperson problem, Steiner tree– Indirect applications.– max bottleneck paths– LDPC codes for error correction– image registration with Renyi entropy– learning salient features for real-time face verification– reducing data storage in sequencing amino acids in a protein –…The University of SydneyPage 98 Cycles and Cuts– Cycle. Set of edges of the form a-b, b-c, c-d, …, y-z, z-a. 12364 5 Cycle C = 1-2, 2-3, 3-4, 4-5, 5-6, 6-178 – Cutset. A cut is a subset of nodes S. The corresponding cutset D is the subset of edges with exactly one endpoint in S.2364 5 178 The University of SydneyPage 99 Cycles and Cuts– Cycle. Set of edges of the form a-b, b-c, c-d, …, y-z, z-a. 12364 5 Cycle C = 1-2, 2-3, 3-4, 4-5, 5-6, 6-178 – Cutset. A cut is a subset of nodes S. The corresponding cutset D is the subset of edges with exactly one endpoint in S. 123 64Cut S= { 4, 5, 8 }5 78 The University of SydneyPage 100 Cycles and Cuts– Cycle. Set of edges of the form a-b, b-c, c-d, …, y-z, z-a. 12364 5 Cycle C = 1-2, 2-3, 3-4, 4-5, 5-6, 6-178 – Cutset. A cut is a subset of nodes S. The corresponding cutset D is the subset of edges with exactly one endpoint in S.2364 5 178 CutS = {4,5,8}Cutset D = 5-6, 5-7, 3-4, 3-5, 7-8 The University of SydneyPage 101 Greedy Algorithm Design Strategy– In previous problems, many obvious greedy algorithms but most of them fail– For minimum spanning tree, many “obvious” greedy algorithms work! E.g. Prim’s, Boruvka’s, Kruskal’s, Reverse-delete algorithm– Single framework from which we can derive these 4 24 462396 9 18511 5118 14 7 8 7161021 The University of SydneyPage 102G = (V, E)T, SeÎT ce = 50 Framework for MST algorithms– Notion of progress– Greedy algorithm picks cheapest choice to make progress– Prim’s algorithm– Start with some vertex s– Maintain a connected subgraph H containing s (initially, H = ({s},∅))– Progress = # of vertices connected to s– Greedy step: Pick cheapest edge e s.t. adding e to H increases number of vertices connected to s Sanity check: does greedy step ever add an edge introducing a cycle? The University of Sydney Page 103 Framework for MST algorithms– Notion of progress– Greedy algorithm picks cheapest choice to make progress– Prim’s algorithm– Start with some vertex s– Maintain a connected subgraph H containing s (initially, H = ({s},∅))– Progress = # of vertices connected to s– Greedy step: Pick cheapest edge (u,v) such that u is in V(H) but not v, i.e. cheapest edge in cut set corresponding to V(H) Sanity check: does greedy step ever add an edge introducing a cycle? No! The University of Sydney Page 104 Walk-Through Legend:- Red vertices = current cut- Bold edges = current solution- Dashed edges = intra-cut edges2 23 3 18 9 s157 146611 4 192305520 16 644t The University of SydneyPage 106 Walk-Through Legend:- Red vertices = current cut- Bold edges = current solution- Dashed edges = intra-cut edges2 23 3 189 s157146611 4 192305520 16 644t The University of SydneyPage 107 Walk-Through Legend:- Red vertices = current cut- Bold edges = current solution- Dashed edges = intra-cut edges2 23 3 189 s157146611 4 192305520 16 6448 The University of SydneyPage 108 Walk-Through Legend:- Red vertices = current cut- Bold edges = current solution- Dashed edges = intra-cut edges2 23 3 189 s157146611 4 192305520 16 6448 The University of SydneyPage 109 Walk-Through Legend:- Red vertices = current cut- Bold edges = current solution- Dashed edges = intra-cut edges2 23 3 189 s157146611 4 192305520 16 6448 The University of SydneyPage 110 Walk-Through Legend:- Red vertices = current cut- Bold edges = current solution- Dashed edges = intra-cut edges2 23 3 18 9 s157 146611 4 192305520 16 6448 The University of SydneyPage 111 Walk-Through Legend:- Red vertices = current cut- Bold edges = current solution- Dashed edges = intra-cut edges2 23 3 18 9 s157 146611 4 192305520 16 6448 The University of SydneyPage 112 Walk-Through Legend:- Red vertices = current cut- Bold edges = current solution- Dashed edges = intra-cut edges2 23 3 18 9 s157 146611 4 192305520 16 6448 The University of SydneyPage 113 Walk-Through Legend:- Red vertices = current cut- Bold edges = current solution- Dashed edges = intra-cut edges2 23 3 18 9 s157 146611 4 192305520 16 6448 The University of SydneyPage 114 MST properties– Simplifying assumption. All edge costs ce are distinct.– Cut property. Let S be any subset of nodes, and let e be the min cost edge with exactly one endpoint in S. Then the MST contains e.– Cycle property. Let C be any cycle, and let f be the max cost edge belonging to C. Then the MST does not contain f. SefCThe University of SydneyPage 115e is in the MSTf is not in the MST Cycle-Cut Intersection– Claim. A cycle and a cutset intersect in an even number of edges.2364 5 Cycle C = 1-2, 2-3, 3-4, 4-5, 5-6, 6-1 Cutset D = 3-4, 3-5, 5-6, 5-7, 7-8 Intersection = 3-4, 5-617– Proof: (by picture) S8C V-SThe University of SydneyPage 116 Structural Property of MSTs– Simplifying assumption. All edge costs ce are distinct.– Cut property. Let S be any subset of nodes, and let e be the min cost edge with exactly one endpoint in S. Then every MST T* contains e.– Proof: (exchange argument)– Suppose e does not belong to T*, and let’s see what happens.– Adding e to T* creates a cycle C in T*.– Edge e is both in the cycle C and in the cutset D corresponding to S Þ there exists another edge, say f, that is in both C and D.– T’=T*È{e}-{f}isalsoaspanningtree.– Since ce < cf, cost(T’) < cost(T*). S– This is a contradiction. ■f eThe University of SydneyT* Page 117 Proof of Correctness of Prim’s– Cut property. Let S be any subset of nodes, and let e be the min cost edge with exactly one endpoint in S. Then every MST T* contains e.– Theorem: Prim’s algorithm finds an MST.– Proof:– Let T be Prim’s solution.– Every edge of Prim’s is the cheapest edge of some cutset. – By cut property, every MST T* contains T.– T and T* have the same number of edges so T = T*.■– Corollary: If edge costs are distinct, then MST is unique.– Alternative viewpoint:– At every step of Prim’s, current tree T is contained in every MST T*. – T is always consistent with every optimal solution.The University of SydneyPage 118 Implementation: Prim’s Algorithm– Implementation. Use a priority queue.– Maintain set of explored nodes S.– For each unexplored node v, maintain attachment cost a[v] = cost of cheapest edge v to a node in S.– O(m log n) with a priority queue. [O(n2) with an array] Prim(G, c) {foreach (v Î V) d[v] ¬ ¥Initialize an empty priority queue Q foreach (v Î V) insert v onto Q Initialize set of explored nodes S ¬ Æwhile (Q is not empty) {u ¬ delete min element from Q S¬SÈ{u}foreach (edge e = (u, v) incident to u)}if ((v Ï S) and (ce < d[v])) decrease priority d[v] to ceThe University of SydneyPage 135 Framework for MST algorithms– Notion of progress– Greedy algorithm picks cheapest choice to make progress– Prim’s algorithm– Start with some vertex s– Maintain a connected subgraph H containing s (initially, H = ({s},∅))– Progress = # of vertices connected to s– Greedy step: Pick cheapest edge e s.t. adding e to H increases number of vertices connected to s– Kruskal’s algorithm– Start with empty graph– Maintain a subgraph H (possibly disconnected)– Progress = # of connected components in current subgraph– Greedy step: Pick cheapest edge that reduces # of connected components The University of SydneyPage 136Sanity check: does Kruskal’s ever add an edge introducing a cycle?Naïve implementation: O(nm) time Need a Union-Find data structure to efficiently keep track of connected componentsKruskal’s AlgorithmKruskal’s algorithm. [Kruskal, 1956] Consider edges in ascending order of weight.Case 1: If adding e to T creates a cycle, discard e according to cycle property.Case 2: Otherwise, insert e = (u, v) into T according to cut property where S = set of nodes in u’s connected component. vuSeeThe University of SydneyCase 1Case 2Page 137 Lexicographic TiebreakingTo remove the assumption that all edge costs are distinct: perturb all edge costs by tiny amounts to break any ties.Impact. Kruskal and Prim only interact with costs via pairwise comparisons. If perturbations are sufficiently small, MST with perturbedcosts is MST with original costs.e.g., if all edge costs are integers, perturbing cost of edge ei by i / n2boolean less(i, j) {if (cost(ei) < cost(ej)) return true else if (cost(ei) > cost(ej)) return false else if (i < j) return true else return false}Implementation. Can handle arbitrarily small perturbations implicitly by breaking ties lexicographically, according to index.The University of Sydney Page 138 Shortest Paths in a GraphShortest path from SIT to the Sydney Opera house The University of SydneyPage 139 Shortest Path Problem– Shortest path network.– Directed graph G = (V, E).– Source s, destination t.– Length !e = length of edge e.– Shortest path problem: find shortest directed path from s to t. cost of path = sum of edge costs in path9 s152 23 3 18The University of Sydney57 44 tPage 140146611 4 19520 16 62Cost of path s-2-3-5-t = 9+23+2+16= 5030 Recall: How to design algorithms Step 1: Understand problemStep 4: Better understanding of problemStep 2: Start with simple alg. Step 5: Improved alg.Step 3: Does it work? Is it fast?No YesProblemAlgorithm Analysis The University of SydneyPage 141DONE! What is simple alg. for Shortest Paths Problem?– Previous problems have easy-to-guess simple algorithms– A good algorithms design strategy is to first consider specialcasesThe University of Sydney Page 142 Shortest Path Problem (Unit Length Edges, Undirected)– Shortest path network.– Undirected graph G = (V, E).– Source s, destination t.– Length!e =lengthofedgee=1.Can solve this with BFS! – Shortest path problem: find shortest path from s to t. cost of path = number of edges in path 23s Cost of path s-7-t = 1+1=2 654The University of Sydney7tPage 143 Shortest Path Problem (Unit-Length Edges)– Shortest path network.– Directed graph G = (V, E).– Source s, destination t.– Length!e =lengthofedgee=1.Can solve this with directed BFS! – Shortest path problem: find shortest directed path from s to t. cost of path = number of edges in path23s Cost of path s-7-t = 1+1=2 654The University of Sydney7tPage 144 Shortest Path Problem (First try)– Shortest path network.– Directed graph G = (V, E).– Source s, destination t.– Length !e = length of edge e.– Algo:– Subdivide each edge e into !e edges of unit length – Run directed BFS 9 s152 23 3 18 146611 4 19230The University of Sydney57 44 tPage 145520 16 6 Shortest Path Problem (First try)– Shortest path network.– Directed graph G = (V, E).– Source s, destination t.– Length !e = length of edge e.Input size = O(n + m log L) Issue: Running time = O(L(m+ n)) where L is max edge length – Algo:– Subdivide each edge e into !e edges of unit length – Run directed BFS– Exercise: Shortest path in subdivided graph ↔ Shortest path in original graph 9 s152 23 3 18 11468630 1 11 4 19 557 44 t 20 16 6 The University of SydneyPage 146 Dijkstra’s Algorithm– Compute shortest path distances to every vertex. – Dijkstra’s algorithm.– Maintain a set of explored nodes S for which we have determined the shortest path distance d(u) from s to u and the shortest path tree T rooted at s spanning S– InitializeS={s},d(s)=0,T={}– Repeatedly choose unexplored node v and edge e which minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, e to T, and set d(v) = p(v). – Observe: s-v path in T has length d(v) !e ushortest path to some u in explored part, followed by a single edge (u, v)vd(u) Ss The University of SydneyPage 147 Dijkstra’s Algorithm– Compute shortest path distances to every vertex. – Dijkstra’s algorithm.– Maintain a set of explored nodes S for which we have determined the shortest path distance d(u) from s to u and the shortest path tree T rooted at s spanning S– InitializeS={s},d(s)=0,T={}– Repeatedly choose unexplored node v and edge e which minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, e to T, and set d(v) = p(v). – Observe: s-v path in T has length d(v)!e ushortest path to some u in explored part, followed by a single edge (u, v)v d(u) Ss The University of SydneyPage 148 Dijkstra’s Shortest Path AlgorithmIn each iteration, choose v not in S that minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, and set d(v) = p(v). ¥shortest path to some u in explored part, followed by a single edge (u, v)¥09 s2 24 31466¥182 ¥30 ¥ 11 4 1915 5 5 206 167 44 t The University of Sydney¥¥Page 149 Dijkstra’s Shortest Path AlgorithmIn each iteration, choose v not in S that minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, and set d(v) = p(v). 9shortest path to some u in explored part, followed by a single edge (u, v)¥09 s2 24 314 14 61826 ¥30 ¥ 11 4 1915 5 5 206 167 44 t The University of Sydney15 ¥ Page 150 Dijkstra’s Shortest Path AlgorithmIn each iteration, choose v not in S that minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, and set d(v) = p(v). 9shortest path to some u in explored part, followed by a single edge (u, v)¥09 s2 24 314 14 61826 ¥30 ¥ 11 4 1915 5 5 207 44166t¥The University of Sydney 15Page 151 Dijkstra’s Shortest Path AlgorithmIn each iteration, choose v not in S that minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, and set d(v) = p(v). 9shortest path to some u in explored part, followed by a single edge (u, v)3309 s2 24 314 14 61826 ¥30 ¥ 11 4 1915 5 5 207 44166t¥The University of Sydney 15Page 152 Dijkstra’s Shortest Path AlgorithmIn each iteration, choose v not in S that minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, and set d(v) = p(v). 9shortest path to some u in explored part, followed by a single edge (u, v)3309 s2 24 314 14 61826 ¥30 ¥ 11 4 1915 5 5 207 44166t¥The University of Sydney 15Page 153 Dijkstra’s Shortest Path AlgorithmIn each iteration, choose v not in S that minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, and set d(v) = p(v). 9shortest path to some u in explored part, followed by a single edge (u, v)X 32 33 09 s2 24 314 14 6182¥63044 114 15 5 519 6t¥207 4416 The University of Sydney 15Page 154 Dijkstra’s Shortest Path AlgorithmIn each iteration, choose v not in S that minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, and set d(v) = p(v). 9shortest path to some u in explored part, followed by a single edge (u, v)X 32 33 09 s2 24 314 14 6182¥63044 114 15 5 519 6t¥207 4416 The University of Sydney 15Page 155 Dijkstra’s Shortest Path AlgorithmIn each iteration, choose v not in S that minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, and set d(v) = p(v). 9shortest path to some u in explored part, followed by a single edge (u, v)X 32 33 09 s2 24 314 14 6182¥6 30 4X435 11 4 15 5 519 6t59207 4416 The University of Sydney 15Page 156 Dijkstra’s Shortest Path AlgorithmIn each iteration, choose v not in S that minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, and set d(v) = p(v). 92 24 3 shortest path to some u in explored part, followed by a single edge (u, v)X 323309 s182¥30 44 35 4X 11 1914 14 6615 5 5 207 44166t59Page 157The University of Sydney 15 Dijkstra’s Shortest Path AlgorithmIn each iteration, choose v not in S that minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, and set d(v) = p(v). 92 24 314 14 6 shortest path to some u in explored part, followed by a single edge (u, v)X 323309 s1826 XX11 19 34 ¥ 30 44 35 4 15 5 5 207 44166tThe University of Sydney 1559 51XPage 158 Dijkstra’s Shortest Path AlgorithmIn each iteration, choose v not in S that minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, and set d(v) = p(v). 92 24 314 14 6 shortest path to some u in explored part, followed by a single edge (u, v)X 323309 s1826 XX11 19 34 ¥ 30 44 35 4 15 5 5 207 44166tThe University of Sydney 1559 51XPage 159 Dijkstra’s Shortest Path AlgorithmIn each iteration, choose v not in S that minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, and set d(v) = p(v). 92 24 314 14 6 shortest path to some u in explored part, followed by a single edge (u, v)X 323309 s1826 XX11 19 45 30 44 35 434 15 5 5 207 44The University of Sydney 15166t5 9 X5 1 5 0 XPage 160 Dijkstra’s Shortest Path AlgorithmIn each iteration, choose v not in S that minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, and set d(v) = p(v). 92 24 3 shortest path to some u in explored part, followed by a single edge (u, v)X 323309 s18214 14 66 X11 19 34207 44The University of Sydney 15454 30 4X435 15 5 56t59 5X1 50 X 16 Page 161 Dijkstra’s Shortest Path AlgorithmIn each iteration, choose v not in S that minimizesp(v) = min d(u) + !e , e = (u,v) : uÎSadd v to S, and set d(v) = p(v). 92 24 3 shortest path to some u in explored part, followed by a single edge (u, v)X 323309 s18214 14 66 X11 19 34207 44The University of Sydney 15454 30 4X435 15 5 56t 16 5X9 51 50 XPage 162 Dijkstra’s Algorithm: Proof of Correctness– Invariant: For each node u Î S, d(u) is the length of the shortest s-u path.– Proof: (by induction on |S|)Base case: |S| = 1 is trivial.Inductive hypothesis: Assume true for |S| = k > 1.
– Let v be next node added to S, and let (u,v) be the chosen edge.
– Claim The shortest s-u path plus (u, v) is an s-v path of length p(v).
– Pf Consider any s-v path P. We’ll show that it’s no shorter than p(v).
– Let x-y be the first edge in P that leaves S, and let P’ be the subpath to x.
– PisalreadytoolongassoonasitleavesS. s !(P) 3 !(P’) + !(x,y) 3 d(x) + !(x,y) 3 p(y) 3 p(v)
y
P
v
P’
x u
The University of Sydney
Page 163
inductive hypothesis
S instead of y
defn of p(y)
Dijkstra chose v
Dijkstra’s Algorithm: Implementation
– For each unexplored node, explicitly maintain p(v)= min d(u)+”e .
!! e = (u,v) : uÎS
– Next node to explore = node with minimum p(v).
– When exploring v, for each incident edge e = (v, w), update p(w) = min { p(w), p(v)+”e }.
– Efficient implementation. Maintain a priority queue of unexplored nodes, prioritized by p(v).
!!
Priority Queue
PQ Operation
Dijkstra
Array
Binary heap
d-way Heap
Fib heap †
Insert
n
n
log n
d log d n
1
ExtractMin
n
n
log n
d log d n
log n
ChangeKey
m
1
log n
logd n
1
IsEmpty
n
1
1
1
1
Total
n2
m log n
m log m/n n
m + n log n
The University of Sydney † Individual ops are amortized bounds Page 165
Shortest Path
The shortest path between two vertices in a graph G with n vertices and m nodes can be computed in O(m+n log n)
time.
The University of Sydney Page 185
Summary: Greedy algorithms
A greedy algorithm is 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.
Problems
– Interval scheduling/partitioning
– Scheduling: minimize lateness
– Shortest path in graphs (Dijkstra’s algorithm) – Minimum spanning tree (Prim’s algorithm) –…
The University of Sydney
Page 186
This Week
–Quiz 1:
– Posted tonight
– Due Sunday 8 March 23:59:00 • One try
• 20 minutes from the time quiz is opened
• No late submissions accepted – Assignment 1:
– Released today 12:00
– Due Wednesday 11 March 23:59:00
– No submissions later than Friday 13 March 23:59:00 accepted
– Assignment 2:
– Released Thursday 12 March
– Due Wednesday 25 March 23:59:00
– No submissions later than Friday 27 March 23:59:00 accepted
The University of Sydney
Page 187
Reviews
There are no reviews yet.