---------------------------------------------------------------------------- CSC 366 / L0102 LECTURE NOTES -- WEEK 2 Spring 2000 ---------------------------------------------------------------------------- Monday 10 January: ----------------- * Proof of optimality for greedy ActivitySelection: - Recall that we are proving that S_i is promising by induction on i, and we are considering the case when S_{i+1} = S_i U {i+1} and activity i+1 does *not* belong to the optimal solution S*_i that extends S_i. Since i+1 does not belong to S*_i, then we have to construct a new optimal solution S*_{i+1} that extends S_{i+1} (because S*_i does not work). How do we get S*_{i+1}? First, consider what happens if we simply add {i+1} to S*_i to get S'. S' is not a solution anymore (because S*_i was optimal and so it contained as many activities as possible), meaning that there is at least one activity in S*_i that conflicts with activity i+1. How many activities could conflict with i+1? Well, we know that S*_i extends S_i and that i+1 is compatible with S_i, so the only possible activities that could conflict with i+1 are from the set {i+2,...,n}. We want to show that there is exactly one activity in S*_i from the set {i+2,...,n} that can conflict with i+1. Let's prove this by contradiction: assume that there are two activities k < j in S*_i that conflict with activity i+1. Since the activities are sorted in order of nondecreasing finish time, we know that f_{i+1} <= f_k <= f_j, so the only way that activity i+1 can be in conflict with j and k is if s_k < f_{i+1} and s_j < f_{i+1}. But this means that activities j and k are in conflict, since s_j < f_{i+1} <= f_k but f_k <= f_j. This is a contradiction since S*_i does not contain any conflicting activities. Hence, there can be at most one activity in S*_i that conflicts with activity i+1. OK, so we know if we add i+1 to S*_i we create exactly one conflict with some activity k. Well, then, let's simply remove k from S' before adding i+1, so we have S*_{i+1} = S*_i - {k} U {i+1}. Then, S*_{i+1} is certainly a solution (since there are no conflicts in S*_{i+1} by the argument we've given above) and |S*_{i+1}| = |S*_i|, i.e., S*_{i+1} is an optimal solution. Moreover, S_{i+1} is included in S*_{i+1} (since S*_{i+1} contains S_i and {i+1}) and S*_{i+1} is included in S_{i+1} U {i+2,...,n} (since S_{i+1} = S_i U {i+1} and S*_i is included in S_i U {i+1,...,n}). Therefore, S_{i+1} is promising! - By what we've said before, this implies that S_n is optimal, which is exactly what we wanted to prove. Tuesday 11 January: ------------------ * General characteristics of greedy algorithms: 1. Works on an optimization problem. 2. The problem is given as a set of "candidates" {c_1,c_2,...,c_n}, each one of which can be assigned a "value" v(c_i). 3. The greedy algorithm simply checks each candidate one after another, in order of nondecreasing value, and decides for each one whether to include it in the solution or not. Once a decision is made, it is never subsequently changed. GeneralGreedyAlgorithm: 1. Sort candidates so v(c_1) >= v(c_2) >= ... >= v(c_n) (or v(c_1) <= v(c_2) <= ... <= v(c_n), depending on the problem) 2. S := {}; 3. for i := 1 to n do 4. if c_i is compatible with S then 5. S := S U {c_i}; 6. return S; 4. Because of this common structure for greedy algorithms, the proof of optimality for greedy algorithms also has a general structure: . Let S_0,S_1,...,S_n be the sequence of partial solutions generated by GeneralGreedyAlgorithm. We prove, by induction on i, that S_i is promising for each i. . Base case: S_0 = {} is always promising. . Ind. Hyp.: Assume S_i is promising for some i, i.e., there exists an optimal solution S*_i that extends S_i. . Ind. Step: Show S_{i+1} is promising, by considering the following cases. Case 1: If S_{i+1} = S_i, then S*_{i+1} = S*_i extends S_{i+1}. Case 2: If S_{i+1} = S_i U {c_{i+1}}, we consider two subcases. 2(a): If i+1 belongs to S*_i, then S*_{i+1} = S*_i extends S_{i+1}. 2(b): If i+1 does not belong to S*_i, then we need to construct a new S*_{i+1} that extends S_{i+1}. This will usually be done by proving an "exchange lemma", i.e., that it is possible to construct S*_{i+1} from S*_i by exchanging some c_k in S*_i with c_{i+1}. . Conclusion: By induction, S_i is promising for all 0 <= i <= n. In particular, S_n is promising, i.e., there exists an optimal solution S*_n that extends S_n (S_n is included in S*_n and S*_n is included in S_n U {n+1,...,n}). But since {n+1,...,n} = {}, this means S*_n = S_n, i.e., S_n is optimal. * Reminders on graphs [CLR Sec. 5.4,5.5]. * These were not covered in the lecture, but make sure that you are familiar with all those definitions before the next lecture! (This should be review for the most part.) - An *undirected graph* G = (V,E) consists of: . a set V of *vertices* (or *nodes*) and . a set E of *edges* (or *arcs*), each edge being an unordered pair of nodes (so (u,v) and (v,u) are the same edge); "self-loops", edges from v to v, are not allowed. . By convention, we let n = |V| be the number of vertices and m = |E| be the number of edges in a graph. - In a *directed* graph, each edge has a direction, so the edge (u,v) is distinct from the edge (v,u); also, self-loops *are* allowed in a directed graph. (We will generally work only with undirected graphs.) - Two vertices u and v are *adjacent* if the edge (u,v) belongs to E. Similarly, two edges e_1 and e_2 are *adjacent* if they have one vertex in common. A vertex v and an edge e are adjacent if v is one of the vertices of e. - The *degree* of a vertex v is the number of edges adjacent to v. - A *path* in G between two vertices u and v is a sequence u = v_1, v_2, ..., v_{k-1}. v_k = v such that (v_i,v_{i+1}) is an edge of E for i = 1,...,k-1. The *length* of a path is the number of *edges* on it. A path is *simple* if all the vertices on the path are distinct. - A *cycle* of G is a closed path (with the same first and last vertices). The *size* of a cycle is the number of vertices in it, and a cycle is *simple* if it contains no repeated vertex (except the first and last vertices) and no repeated edge. - A graph G is *connected* if there exists at least one path between every pair of vertices. - A graph G is *acyclic* if it does not contain any cycle. - A *tree* is a connected and acyclic graph. Equivalently, a tree is a connected graph with n-1 edges. Equivalently, a tree is an acyclic graph with n-1 edges. (Where n is the number of vertices, as usual.) - A *spanning tree* of a graph G = (V,E) is a tree T = (V,E') defined on the same vertex set such that E' is a subset of E. Thursday 13 January: ------------------- * NO LECTURE!