【文章內(nèi)容簡介】 Algorithm 34 Interval Scheduling: Analysis Theorem. Greedy algorithm is optimal. Pf. (by contradiction) ? Assume greedy is not optimal, and let39。s see what happens. ? Let i1, i2, ... ik denote set of jobs selected by greedy. ? Let j1, j2, ... jm denote set of jobs in the optimal solution with i1 = j1, i2 = j2, ..., ir = jr for the largest possible value of r. j1 j2 jr i1 i1 ir ir+1 . . . Greedy: OPT: jr+1 why not replace job jr+1 with job ir+1? job ir+1 finishes before jr+1 35 j1 j2 jr i1 i1 ir ir+1 Interval Scheduling: Analysis Theorem. Greedy algorithm is optimal. Pf. (by contradiction) ? Assume greedy is not optimal, and let39。s see what happens. ? Let i1, i2, ... ik denote set of jobs selected by greedy. ? Let j1, j2, ... jm denote set of jobs in the optimal solution with i1 = j1, i2 = j2, ..., ir = jr for the largest possible value of r. . . . Greedy: OPT: solution still feasible and optimal, but contradicts maximality of r. ir+1 job ir+1 finishes before jr+1 36 Greedy Analysis Strategies Greedy algorithm stays ahead. Show that after each step of the greedy algorithm, its solution is at least as good as any other algorithm39。s. Structural. Discover a simple structural bound asserting that every possible solution must have a certain value. Then show that your algorithm always achieves this bound. Exchange argument. Gradually transform any solution to the one found by the greedy algorithm without hurting its quality. Other greedy algorithms. Kruskal, Prim, Dijkstra, Huffman, … 37 Coin Changing Goal. Given currency denominations: 1, 5, 10, 25, 100, devise a method to pay amount to customer using fewest number of coins. Ex: 34162。. Dose this algorithm work? At each iteration, add coin of the largest value that does not take us past the amount to be paid. 38 CoinChanging Observation. Greedy algorithm is not optimal for US postal denominations: 1, 10, 21, 34, 70, 100, 350, 1225, 1500. Counterexample. 140162。. ? Greedy: 100, 34, 1, 1, 1, 1, 1, 1. ? Optimal: 70, 70. 39 DivideandConquer Divideandconquer. ? Break up problem into several parts. ? Solve each part recursively. ? Combine solutions to subproblems into overall solution. Most mon usage. ? Break up problem of size n into two equal parts of size 189。 n. ? Solve two parts recursively. ? Combine two solutions into overall solution in linear time. 40 Integer Arithmetic Add. Given two ndigit integers a and b, pute a + b. ? O(n) bit operations. Multiply. Given two ndigit integers a and b, pute a b. ? Brute force solution: ?(n2) bit operations. 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 1 0 0 * 1 0 1 1 1 1 1 0 1 + 0 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 Add Multiply 41 To multiply two ndigit integers: ? Multiply four 189。 ndigit integers. ? Add two 189。ndigit integers, and shift to obtain result. DivideandConquer Multiplication: Warmup ??T( n ) ? 4 T n / 2? ?r e c u r s i ve c a l l s ? ? ( n )a dd , s h i f t ? T ( n ) ? ? ( n 2 ) ??x ? 2 n / 2 ? x 1 ? x 0y ? 2 n / 2 ? y 1 ? y 0xy ? 2 n / 2 ? x 1 ? x 0? ? 2 n / 2 ? y 1 ? y 0? ? ? 2 n ? x 1 y 1 ? 2 n / 2 ? x 1 y 0 ? x 0 y 1? ? ? x 0 y 0assumes n is a power of 2 42 To multiply two ndigit integers: ? Add two 189。 n digit integers. ? Multiply three 189。ndigit integers. ? Add, subtract, and shift 189。 ndigit integers to obtain result. Theorem. [KaratsubaOfman, 1962] Can multiply two ndigit integers in O() bit operations. Karatsuba Multiplication ??x ? 2 n / 2 ? x 1 ? x 0y ? 2 n / 2 ? y 1 ? y 0xy ? 2 n ? x 1 y 1 ? 2 n / 2 ? x 1 y 0 ? x 0 y 1? ? ? x 0 y 0? 2 n ? x 1 y 1 ? 2 n / 2 ? ( x 1 ? x 0 ) ( y 1 ? y 0 ) ? x 1 y 1 ? x 0 y 0? ? ? x 0 y 0 ??T( n ) ? T n / 2? ?? ? ? T n / 2? ?? ? ? T 1 ? n / 2? ?? ?r e c u r s i ve c a l l s? ? ( n )a dd , s u b t r a c t , s h i f t? T( n ) ? O ( n l o g 2 3 ) ? O ( n 1 . 5 85 )A B C