---------------------------------------------------------------------------- CSC 366 / L0102 LECTURE NOTES -- WEEK 1 Spring 2000 ---------------------------------------------------------------------------- Monday 3 January: ---------------- * Course organization (going over Course Information handout). * Course overview: - Main topic: "efficient computation". - First, we'll cover some techniques for writing efficient algorithms (greedy, dynamic programming, maximum flow). - Next, we'll take a look at the theory of NP-completeness, which allows us to show that certain problems do *not* have efficient algorithms (almost certainly). - Finally, we'll give a brief survey of computability theory, which allows us to show that certain problems do not have algorithmic solutions at all (let alone efficient ones). * Efficiency and big-Oh notation: - What do we mean by "efficient"? Traditionally, an algorithm is considered efficient (or "feasible", or "tractable") if its running time is bounded by a polynomial in the size of the input. - Recall that we measure the running time of an algorithm as a function of the input size (taking the worst-case), i.e., T(n) is the worst running time over all inputs of size n. - Recall also that we say a function T(n) is bounded by a polynomial (or "poly-bounded") if there exists a fixed integer k such that T(n) is O(n^k). (For a review of big-Oh notation, read Chapter 2 in Cormen, Lieserson, and Rivest's "Introduction to Algorithms".) * Coin-changing problem: - Informally, we want to make change for an amount of money x using as few coins as possible. - Formal statement: CoinChange Input: An amount of money x Output: Nonnegative integers a,b,c,d,e such that 100a+25b+10c+5d+1e = x and a+b+c+d+e is minimal. That is, make change for $x using as few loonies, quarters, nickles, dimes, and pennies as possible. - Greedy strategy (obvious): Give out highest denomination coins first. - Does this work? "Obviously" yes, but there *are* examples where this strategy fails (e.g., denominations 10,8,1). - So how do we know it works also in the first case? We need to *prove* this. Tuesday 4 January: ----------------- * Activity selection problem: - ActivitySelection: Input: Nonnegative integer start and finish times (s_1,f_1), ..., (s_n,f_n) such that s_i <= f_i for all i. Output: A subset S of {1,...,n} such that no two activities in S are in conflict and the size of S is maximal. That is, we want to schedule as many activities as possible, without any two of them overlapping. - Greedy strategy: longest first? -> counter-example shortest first? -> counter-example by nondecreasing start time? -> counter-example by nondecreasing finish time? seems to work... by non*in*creasing start time? (should be equivalent to nondecreasing finish time) - Again, the only way to know for sure that the strategy works is to prove that it does. - Greedy algorithm for ActivitySelection: 1. sort the activities by nondecreasing finish time (so f_1 <= f_2 <= ... <= f_n after this step) 2. S := {}; 3. for i := 1 to n do 4. if (s_i,f_i) is compatible with S 5. S := S U {i}; end for - We want to prove that the solution given by the greedy algorithm is optimal. How can we do this? Let's start by defining some terminology: during the execution of the greedy algorithm, we will be generating a sequence S_0, S_1, S_2, ..., S_n of *partial* solutions to the problem. In general, we say that a partial solution is "feasible" if it can be extended to a complete solution, "promising" if it can be extended to an optimal solution. What do we mean by "extended"? A solution S extends S_i if S_i is included in S S is included in S_i U {i+1,...,n} - Now, how do we prove that S_n is optimal? We will show that S_i is promising for every value of i. What will that tell us about the final solution S_n? By the definition of "promising", this means that there exists an optimal solution S* that extends S_n, which means that S_n is included in S* and S* is included in S_n U {n+1,...,n}. But {n+1,...,n} is the empty set, so S_n must be equal to S*, that is, S_n is an optimal solution! Thursday 6 January: ------------------ * Activity Selection: - Recall the definitions of "promising" and "extends": make sure these are clear and well understood. In particular, recall that we say a solution S "extends" S_i if S_i is included in S S is included in S_i U {i+1,...,n} - Now, we prove that for every i between 0 and n, S_i is promising, i.e., for each i, there exists an optimal solution S*_i that extends S_i (we use the notation "S*_i" because this optimal solution *could* be different for different values of i). We prove this by induction on i. Base case: S_0 = {}, which is promising since for any optimal solution S*, {} is included in S* and S* is included in {1,...,n}. So we can pick S*_0 to be any optimal solution. Ind. Hyp.: For some i between 0 and n-1, assume that S_i is promising, i.e., that there exists some optimal solution S*_i that extends S_i. Ind. Step: We want to show that S_{i+1} is promising. Consider the following cases. Case 1: S_{i+1} = S_i. In this case, let S*_{i+1} = S*_i. Then, S_{i+1} is extended by S*_{i+1} because activity i+1 cannot be compatible with S_i (since the greedy algorithm rejected it), so . S_{i+1} = S_i is included in S*_i = S*_{i+1} (by the induction hypothesis), . S*_{i+1} is included in S_{i+1} U {i+2,...,n} since S*_i is included in S_i U {i+1,...,n} but does not contain i+1 (by the argument above). Case 2: S_{i+1} = S_i U {i+1}. We can consider two subcases. 2(a): If i+1 belongs to S*_i, then we let S*_{i+1} = S*_i and we have that . S_{i+1} = S_i U {i+1} is included in S*_i = S*_{i+1}, . S*_{i+1} = S*_i is included in S_{i+1} U {i+2,...,n} = S_i U {i+1} U {i+2,...,n} = S_i U {i+1,...,n}. 2(b): This is the one interesting case in the proof, the one where we actually have to work! If 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 will show (next time) that there is exactly one activity in S*_i in conflict with activity i+1, and that we can construct S*_{i+1} by simply removing that one conflicting activity from S'.