| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2012:journals:garrett:entries:week_5 [2012/03/01 04:55] – Added scores 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 ===== | ===== Chapter Scores ===== |
| 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): |
| |
| **Overall Runtime: O(n*log n)** | **Overall Runtime: O(n*log n)** |
| 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''\\ |
