| Next revision | Previous revision |
| courses:cs211:winter2012:journals:garrett:entries:week_5 [2012/03/01 04:49] – created garrettheath4 | courses:cs211:winter2012:journals:garrett:entries:week_5 [2012/03/07 03:43] (current) – changed title garrettheath4 |
|---|
| ====== Week 5 ====== | ====== Week 5-6 ====== |
| | |
| | ===== Chapter Scores ===== |
| | * **Readability Score**: 7/10 |
| | * **Interest Score**: 9/10 |
| |
| ===== Readings ===== | ===== Readings ===== |
| The interval scheduling problem involves a shared resource and a set of requests. Each request wants to use that resource from a certain point in time to a certain ending point in time. When a request is using a resource, no other request can be using the resource during any part of its time slot, meaning that there can be no more than one request scheduled on the resource at any given time. | The interval scheduling problem involves a shared resource and a set of requests. Each request wants to use that resource from a certain point in time to a certain ending point in time. When a request is using a resource, no other request can be using the resource during any part of its time slot, meaning that there can be no more than one request scheduled on the resource at any given time. |
| |
| The interval scheduling problem can be solved with a greedy algorithm. A **greedy algorithm** is an algorithm that, like an inductive proof, starts with a base case and takes growing steps in which it always makes the best choice at each step in the solution and each step makes progress toward the solution. The greedy algorithm to solve the interval scheduling problem is as follows: | The interval scheduling problem can be solved with a greedy algorithm. A **greedy algorithm** is an algorithm that, like an inductive proof, starts with a base case and takes growing steps in which it always makes the best choice at each step in the solution and each step makes progress toward the solution. The greedy algorithm to solve the interval scheduling problem is as follows (based on algorithm on Page 118): |
| |
| * ''Initially let R be the set of all requests, and let A be empty''\\ | **Overall Runtime: O(n*log n)** |
| * ''While R is not yet empty''\\ | * ''Initially let R be the set of all requests, and let A be empty''\\ **O(n)** |
| * ''Choose a request i in R that has the smallest finishing time''\\ | * ''While R is not yet empty''\\ **O(n*log n)** |
| * ''Add request i to A''\\ | * ''Choose a request i in R that has the smallest finishing time'' **O(log n)**\\ |
| * ''Delete all requests from R that are not compatible with request i''\\ | * ''Add request i to A'' **O(1)**\\ |
| | * ''Delete all requests from R that are not compatible with request i''\\ **O(n)** |
| * ''EndWhile''\\ | * ''EndWhile''\\ |
| * ''Report the set A as the set of accepted requests'' | * ''Report the set A as the set of accepted requests'' |
| Another problem similar to the interval scheduling problem is the task scheduling problem. The task scheduling problem involves a set of tasks that have a set length of time but are flexible in when they are done. Each task has a deadline, however, to indicate when the task should be done by. Every task must be completed and no two tasks can be scheduled at the same time. The goal of the algorithm is to schedule the tasks such that the amount of time that every task is late is minimal (the “lateness” of the schedule). | Another problem similar to the interval scheduling problem is the task scheduling problem. The task scheduling problem involves a set of tasks that have a set length of time but are flexible in when they are done. Each task has a deadline, however, to indicate when the task should be done by. Every task must be completed and no two tasks can be scheduled at the same time. The goal of the algorithm is to schedule the tasks such that the amount of time that every task is late is minimal (the “lateness” of the schedule). |
| |
| The task scheduling problem can be solved with an intuitive greedy algorithm. The central concept of the algorithm is to minimize lateness by “being ahead” and scheduling tasks in order of earliest deadline to late deadline. The algorithm is as follows: | The task scheduling problem can be solved with an intuitive greedy algorithm. The central concept of the algorithm is to minimize lateness by “being ahead” and scheduling tasks in order of earliest deadline to late deadline. The algorithm is as follows (based on algorithm on Page 124): |
| |
| * ''Order the jobs in order of their deadlines''\\ | **Overall Runtime: O(n*log n)** |
| * ''Assign labels to the ordered jobs such that d_i ≤ … ≤ d_n''\\ | * ''Order the jobs in order of their deadlines'' **O(n*log n)**\\ |
| * ''Set the finishing time, f, to be the start time for all jobs''\\ | * ''Assign labels to the ordered jobs such that d_i ≤ … ≤ d_n'' **O(n)**\\ |
| * ''For each job j_i where 1≤i≤n:''\\ | * ''Set the finishing time, f, to be the start time for all jobs'' **O(1)**\\ |
| * ''Assign the job i to the time interval from s(i)=f to f(i)=f+t_i''\\ | * ''For each job j_i where 1≤i≤n:'' **O(n*1)**\\ |
| * ''Let f=f+t_i''\\ | * ''Assign the job i to the time interval from s(i)=f to f(i)=f+t_i''\\ **O(1)** |
| | * ''Let f=f+t_i'' **O(1)**\\ |
| * ''End''\\ | * ''End''\\ |
| * ''Report the set of scheduled intervals [s(i), f(i)] for i=1 to i=n''\\ | * ''Report the set of scheduled intervals [s(i), f(i)] for i=1 to i=n''\\ |
