Differences

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

--- courses:cs211:winter2014:journals:emily:entryfour [2014/02/10 19:02] – [Chapter 3.5] hardye
+++ courses:cs211:winter2014:journals:emily:entryfour [2014/02/11 03:24] (current) – [Chapter 3.4] hardye
@@ Line 31: / Line 31: @@
 Consider case 2 where G must contain an odd cycle so there is an edge that connects two nodes in the same layer. Supposed the two nodes in the same layer, x and y, are in layer L<sub>j</sub>. Let z be the node that is in layer L<sub>i</sub>, the lowest common ancestor, the node that is directly above x and y, and L<sub>i</sub> > L<sub>j</sub>. There is a cycle in the path z-x and y-z. The length of the cycle is 2(j-i)+1 which is an odd number.
+Readability: 10. Very easy reading, kind of dry.
 ====== Chapter 3.5 ======
@@ Line 65: / Line 67: @@
 **Proof**
+Two nodes s and t are mutually reachable so we claim that the strong components containing s and t are identical. So for any node v if s and v are mutually reachable then t and v are mutually reachable (by 3.16). But if s and t are NOT mutually reachable then there cannot be a node v that is in the strong component of each. If there were then s and v and v and t would be mutually reachable so s and t would be.
+We can compute the strong components for all nodes in **O(m+n)**
+I thought this section was pretty dry. It was short and easy to read but not that interesting to me. Readability: 8
+====== Chapter 3.6 ======
+**Directed Acyclic Graphs and Topological Ordering**
+A directed acyclic graph (DAG) has no cycles.
+{{ :courses:cs211:winter2014:journals:emily:356px-directed_acyclic_graph_3.svg.png?300 | DAG}}
+We use DAGs to represent dependencies or precedence relations for example showing a set of tasks where one is dependent on the other or one needs to be performed before the other can. Example: Course prerequisite for CS major.
+A DAG has a **topological ordering** which is an ordeing of its nodes so that for every edge (v<sub>i</sub>, v<sub>j</sub>), i<j. All of the edges must point forward in an ordering.
+**3.18**
+If G has a topological ordering, then G is a DAG.
+An algorithm for finding a topological ordering:
+**3.19**
+In every DAG, there is a node v with no incoming edges
+**Proof**
+There is a directed graph G where every node has at least one incoming edge. To show how to find a cycle, we pick a node v and follow the edges backward from v  since it has at least one incoming edge we can move to node u. And from u backward to x etc. After n+1 steps we will have visited some node twice which shows there is a cycle
+Having a node with no incoming edges is all that is needed to produce a topological ordering.
+**3.20** If G is a DAG, then G has a topological ordering.
+**Algorithm**
+     To compute a topological ordering of G:
+     Find a node v with no incoming edges and order it first
+     Delete v from G
+     Recursively compute a topological ordering of G-{v} and append this order after v
+The runtime of this algorithm is O(n<sup>2</sup>)
+To achieve an algorithm with O(m+n) we use the same one but iteratively delete nodes with no incoming edges.
+This section was definitely more interesting to read than the last. I think DAG's are pretty cool. The readability was a 9 out of 10 even though some things felt a little vague the first time through.
+====== Chapter 4.1 ======
+**Interval Scheduling: The Greedy Algorithm Stays Ahead**
+The idea for a greedy algorithm in the terms of the interval scheduling problem is create a rule to choose the first request then reject all other requests that are not compatible with the chosen request. Then select the next request and repeat. There are many ways we could choose a rule to pick the first request such as ordering by the earliest start time, the smallest interval time, or the job with fewest conflicts, or what we choose to use, finish time.
+**The Algorithm**
+   Initially let R be the set of all requests, and let A be empty
+   While R is not yet empty
+       Choose a request i in R that has the smallest finishing time
+       Add request i to A
+       Delete all requests from R that are not compatible with request i
+   Endwhile
+   Return the set A as the set of accepted requests
+We declare that the intervals in the set returned by the algorithm are all comparable. The set is a compatible set of requests.
+We now want to show that the greedy solution A, is optimal. So we show that A = O. The greedy rule guarantees that f(i<sub>1</sub>) <= f(j<sub>i</sub>) this how we show that the greedy solution "stays ahead". It stays ahead of O: for each r, the r<sub>th</sub> interval it selects finished at least as soon as the r<sub>th</sub>  interval in O.
+**4.3** The greedy algorithm returns an optimal set A.
+We can make our algorithm run in O(n log n)...
+  * begin by sorting the n requests in order of finishing time
+  * assume that f(i) =< f(j) when i<j
+  * construct an array S[1...n] with the property that S[i] contains the value s(i).
+  * select requests by processing intervals in order of increasing f(i).
+  * This takes O(n) time!!
+**A Related Problem: Scheduling All Intervals**
+In this problem we have identical resources and have to schedule all of the requests using as few resources as possible. Example: scheduling classes in the smallest number of classrooms possible.
+This is called the //interval partitioning problem//
+We can define the depth of a set of intervals to be the maximum number that pass over any single point on the time-line.
+**4.4**
+In any instance of Interval Partitioning, the number of resources needed is as least the depth of the set of intervals.
+**Algorithm**
+   Sort the intervals by their start times, breaking ties arbitrarily
+   Let I<sub>1</sub> , I<sub>3</sub>,..., I<sub>n</sub> denote the intervals in this order
+   For j = 1, 2, 3, ..., n
+      For each interval I<sub>j</sub> that precedes I<sub>j</sub> in sorted order and overlaps it
+          Exclude the label of I<sub>i</sub> from consideration for I<sub>j</sub>
+      Endfor
+      If there is any label from {1, 2, ..., d} that has not been excluded then
+         Assign a nonexcluded label to I<sub>j</sub>
+      Else
+         Leave I<sub>j</sub> unlabeled
+      Endif
+   Endfor
+**4.5**
+If we use the greedy algorithm above, every interval will be assigned a label, and no two overlapping intervals will receive the same label.
+If you have d labels to use then as you go through the intervals from left to right you assign a label to each interval you encounter, you never reach a point where all of the labels are currently in use.
+**4.6** The greedy algorithm above schedules every interval on a resources, using a number of resources equal to the depth of the set of intervals. This is the optimal number of resources needed.
+This section was very interesting. I like scheduling a lot because I feel like it is really applicable to a problem that needs to be solved every day and something I could make use of. The readability of this section was a 9 out of 10 especially after reading it after the class lecture.