Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioni [2012/02/23 05:51] – [Designing a Greedy Algorithm] mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioni [2012/02/24 20:55] (current) – [Designing a Greedy Algorithm] mugabej
@@ Line 48: / Line 48: @@
   * With this problem,we have many identical resources available and we wish to schedule all of the requests using as few resources as possible.
   * The goal here is to partition all intervals across multiple resources: Thus the problem is called the **Interval Partitioning Problem**.
+  * 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.
+==Algorithm for the Interval Partitioning Problem ==
+>>>>>>>>>Sort the intervals by their start times,breaking ties arbitrarily
+>>>>>>>>>Let I<sub>1</sub>,I<sub>2</sub>,...I<sub>n</sub> be the intervals in that order
+>>>>>>>>>For j = 1,2,3,...n:
+>>>>>>>>>>>>>>>>>For each interval I<sub>i</sub> that precedes I<sub>j</sub> in sorted order and overlaps it:
+>>>>>>>>>>>>>>>>>>>>>>>>>>>Exclude the label I<sub>i</sub> from considerations for I<sub>j</sub>
+>>>>>>>>>>>>>>>>>End For
+>>>>>>>>>>>>>>>>>If there is any label from {1,2,...d} that has not been excluded:
+>>>>>>>>>>>>>>>>>>>>>>>>>>>Assign a non excluded label to I<sub>j</sub>
+>>>>>>>>>>>>>>>>>else:
+>>>>>>>>>>>>>>>>>>>>>>>>>>>Leave I<sub>j</sub> unlabeled
+>>>>>>>>>>>>>>>>>End if
+>>>>>>>>>>End For
+--> 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.