Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioni [2012/02/24 20:48] – QA mugabej | courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioni [2012/02/24 20:55] (current) – [Designing a Greedy Algorithm] mugabej | ||
|---|---|---|---|
| Line 50: | Line 50: | ||
| * The //depth// of a set of intervals is the maximum number of intervals that pass over any single point on the time-line | * The //depth// of a set of intervals is the maximum number of intervals that pass over any single point on the time-line | ||
| * The number of of resources needed is always at least the depth of the set of intervals. | * The number of of resources needed is always at least the depth of the set of intervals. | ||
| - | ==Algorithm | + | ==Algorithm |
| >>>>>>>>> | >>>>>>>>> | ||
| Line 65: | Line 65: | ||
| >>>>>>>>>> | >>>>>>>>>> | ||
| + | --> With this algorithm, every interval is assigned a label and no two overlapping intervals receive the same label.\\ | ||
| + | \\ | ||
| + | --> This algorithm also schedules every interval on a resource using a number of resources equal to the depth of the set of intervals.\\ | ||
| + | \\ | ||
| + | After writing this section,I realized how tricky,yet simple, designing a greedy algorithm. As it was an introduction to greedy algorithm, one reading wasn't really enough for this section to make sense. But after rereading it, it now make senses.\\ | ||
| + | \\ | ||
| + | On our usual rating scale, I give this section an 8/10. | ||
