Week 3 Notes
Week 3 Notes CMPS 102
Popular in Algorithm Analysis
Popular in ComputerScienence
This 4 page Class Notes was uploaded by Shanee Dinay on Monday February 8, 2016. The Class Notes belongs to CMPS 102 at University of California - Santa Cruz taught by Dimitris Achlioptas in Winter 2016. Since its upload, it has received 7 views. For similar materials see Algorithm Analysis in ComputerScienence at University of California - Santa Cruz.
Reviews for Week 3 Notes
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/08/16
Day 5 1/19/2016 CMPS 102 Homework 1. fairly straightforward algorithm that takes O(n log n) a. first make sure you have the O(n log n) algorithm and there is a linear algorithm b. harder to prove that it actually works bulleted list of what to do T(n) = aT(n/b) + f(n) k = logn logbsmall k) ← small so: K = log n b i Total amount of work in level i, will be the amount of work in a problems. Each of which has size i i n/b. Therefore it will require work f(n/b ) lob n ∑ af( ) i i−0 b The terms of the function sums will either increase, stay constant, or decrease Example. a = 2, b = 3, f(n) = n 2 log n i n 2 2 i 2 2 3 2 i 2 • (3i = (9) • n → n∑ ( ) 9→ you can replace the limit of the sum with infinity and i=0 nothing major would happen 1 = ≈ 1 → O(n 2) 1−2/9 7 Example. a = 4, b = 3, f = n 2 4 • ( i2 → ( 9 • n 3 Example. a = 4, b = 3, f = n lo3 n 4 • ( i → ( ) •n > n ∑ ( ) → n • ( )4 log4n 3 3 i=0 3 3 Matrix Multiplication rows by columns, fiven two nbyn matrices A and B, computer C = AB Bute force. Θ(n ) arithmetic operations Fundamental question. Can we improve upon brute force? 2 3 8T(n/2) + Θ(n ) → T(n) = Θ(n ) 2 3 8T(n/2) + Θ(n ) → T(n) = Θ(n ) a = 8, b = 2, f(n) = n2 i i 8problems each of size n/2 log2n 8 • ( )2 = n • ( ) → n2 • 2 → n 2 • ∑ 2 ≈ n • C • 2 lo2 = n3 2i 4 i = 0 Matrix Multiplication: Key IDea multiple 2 by 2 block matrices with only 7 mulitplications you get 18 10 + 8 additions = we have replaced the 8 with a 7 7T(n/2) + Θ(n 2) → T(n) = Θ(n 3) this is magic, no reason for it to be true, but it’s true i. n 2 2 7 i 2 7 log2n 7 • (2 ) = n • (4) ≈n • C • (4) Know change of base for the test l2g 7 7T(n/2) + Θ(n ) → T(n) = Θ(n n ) = O(n) .81 Fast Matrix Multiplication in Practice implementation issues common misperception remark Group Theory multiply 2by2 matrices with only 6 scalar multiplications… impossible two 3by3 matrices with only 21 scalar multiplications T(n) = 21T(2/x) O*(n 2) … impossible Q: two 70 by 70 matrices with only 143, 640 scalar multiplications A: yes [pan, 190] Best known time O(n ) 376 Splitting an array and finding the average, medium in an array T(n) = T(n/2) + lightsaber (n) → assume that we have the algorithm in linear time n + n/2 + n.8 + n.16 + … 5(n + n/2 + n.8 + n.16 + … ) = O(n) what are the odds of what you want: if we say ¾? Middle half of the element, we have a one into chance of getting what you want. We have to try twice deterministic algorithm that runs in O(n), choose the element in the middle of the array We will take the unsorted array and partition it into blocks of size 2k + 1. And therefore 2k + 1 is an odd number. Sort each array, then take its middle element. It cost 11 • log 11. We’ll have to do it 11 times, so we get n/1 n • (2k + 1) log(2k + 1) 2k+1 take the number you get to see in each block. Sort the blocks so that their exposed element is in increasing order we cannot afford to sort all the blocks, but we can afford to find their median n the new block of exposed elements is 2k+1 the number we hold is going to be the number in the middle block Day 6 1/21/2016 CMPS 102 If you cannot completely answer a question write: I could only get this far If you cannot do a question write: intentionally left blank Given a sorted array: find middle element split unsorted array into blocks of size 2k+1 takes time n log(2k+1) n find the middle element of each block and put it into a new array with size 2k+1 the middle element in this new array is in the middle of the sorted array n • • (k + 1) = n • k+1 2k+1 2 4k+2 on right half of all 2k+1 blocks, we are getting rid of at least k+1 elements on the left half, same thing, getting rid of at least k+1 elements k+1 k+1 4k+2 − k − 1 3k+1 n n • 4k+2 = n(1 4k+2) = n ( 4k+2 ) = (4k+2 )•n Sort(n) = C • n • log n T(n) = n • C • (2k + 1) log(2k+1) + n + T( n ) + n + T( 3k+1 • n) 2k+1 2k+1 2k+1 4k+2 T(n) = LS(n) + T( 4k+2• n) LS = light saber LS(n) → 2k+1• C • (2k + 1) log(2k+1) + 2k+1+ T( 2k+1) + n this is all the work we do to split 1 T(n) = n[C log(2k+1) + 2k+1 + 1] + T( n ) + T(3k+1 • n) 2k+1 4k+2 both of the expressions on the second line are decreasing in k we want k to be big n 3k+1 We claim: 2k+1 + n4k+2 < n Our ultimate goal: we believe that we can get a linear time algorithm Imagine that we take k = 1 Then we would have T( ) + T( •n) + … more stuff 3 6 T( 3 + T( •3) + … more stuff n 2n IF our recursion is correct then we would have 10•( ) + 10(3 3) = 10n * picking the 10 out of thin air n 2n we have a3d 3 = n If we take k = 2 we have T( ) + T( 7 • n) + …. 5 10 Now observe that and 7n is less than one and will give us a geometric solution 5 10 T( ) + T( 7• n) + C • n ← let’s see how much this is 5 10 2 We claimed that there exists a constant z such that the equation ≤ z • n z2because k = 2 zn 7 5 + z•n • 10 + C2• n ≤ z2 ...so how much is this? zn( + 7 ) + C • n ≤ zn we get rid of the n 5 10 2 2 z( + 7 ) + C ≤ z we get → z(1( 9 )) ≤ C → z( 1) ≤ C 5 10 2 2 10 2 10 2 Algorithm does not work in linear time for blocks of size 3, but for blocks of size 5 it starts to work n 3k+1 T(n) ≤ Z k 2k+1 + Zk n • 4k+2 + Ckn ≤ Zk n 1 3k+1 n • Zk2k+1 + 4k+2 ) + Ck≤ Zkwe get rid of n 1 3k+1 Zk2k+1 + 4k+2) + Ck Zk Z (3l+3) + C ≤ Z ←→ Z (1 3k+3 ) ≥ C k4k+2 k k k 4k+2 k Z ≥ (4k+2 − 3k )3 • C k 4k+2 k Z ≥ (4k+2) • Cwe want Z to be as good as possible so we use equal sign k k−1 k k Zk= (4k+2) • Ck k−1 k > 1, our running time of the algorithm is linear If k = 2 → ( 10) • C2= 10 • C 2 1 If k = 3 → 7 • C3 If k = 4 → 6 • C 4 It turns out that the best case is with blocks of size 11 → 24 • C5 after that as we make k bigger, it is not optimal Computing the product of two matrices nbyn in time n 2.81 → nbyn multiplication Example: Sudoku, Netflix uses this Homework #4: remember that it is a question in which the answer is not O(log 3??) it has to work for every specific n even if n is not divisible by 3 you’re supposed to get running time log n +1 that plus one is there for a reason, to get 3 log3 in some sense you need to be splitting perfectly in equal piles of 3 every time, but this is not always possible → that is what the +1 is there for. you do not get an extra +1 per split. decision tree, that is what you are building. the extra little +1 in each level, aggregate it so it is only +1 in the end
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'