Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioni [2012/02/23 04:48] – [Designing a Greedy Algorithm] mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectioni [2012/02/24 20:55] (current) – [Designing a Greedy Algorithm] mugabej
@@ Line 23: / Line 23: @@
 >>>>>>>Return the set A as the set of accepted requests
-===Algorithm Analysis ===
+===Algorithm Analysis And implementation===
-  * The set A returned is that of compatible requests
+  * The set A returned is that of compatible requests and it is optimal.
-  *
+  * For all indices r ≤ k, we have f(//i//<sub>r</sub>) ≤ f(//j//<sub>r</sub>), f(//j//<sub>r</sub>) being the finishing time of the request in the optimal solution corresponding to the request f(//i//<sub>r</sub>) in A
+\\
+==Implementation ==
+-->Our goal: A O(nlogn)running time
+>>>>>>>>> First sort the n requests in order of finishing time and label them in this order:f(//i//) ≤ f(//j//) if i ≤  j. Sorting takes O(nlogn) time)
+>>>>>>>>>We then construct an array S[1,...,n] where S[//i//] contains the value S(//i//). This takes O(n) time.
+>>>>>>>>>>>>>>>>>Now we select requests in order of increasing f(//i//). We always select the first interval.
+>>>>>>>>>>>>>>>>>Then iterate through the interval in order until S(//j//) ≥ f(1). We then select this interval S(//j//).
+>>>>>>>>>>>>>>>>>In this way, we spend O(1) time per each interval and implement our greedy rule in a single pass through the intervals. This part of the algorithm takes O(n) time.\\
+\\
+=== Extensions of the Interval Scheduling Problem ===
+  * For all scheduling problems, all of the requests are not known in advance. In case all of the requests are not known in advance, the greedy algorithm must take decisions as time goes on.
+  * The solution given here assumes all of the requests are of equal value. However, they may have different values associated with them, such as in the case of the Weighted Interval Scheduling Problem.
+\\
+=== A Related Problem: Scheduling all of Intervals ===
+  * 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.