×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

by: Shanee Dinay

7

0

4

# Week 3 Notes CMPS 102

Shanee Dinay
UCSC
GPA 3.94

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

Week 3 notes of Computer Science Algorithms Analysis. Topics include Matrix Multiplication, Array Sorting, and Homework Hints.
COURSE
Algorithm Analysis
PROF.
Dimitris Achlioptas
TYPE
Class Notes
PAGES
4
WORDS
CONCEPTS
Computer Science, matrix multiplication, Array Sorting, Algorithms Analysis
KARMA
25 ?

## 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

×

×

### What is Karma?

#### 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 = log​n​ ­ logb​small 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 • ( i​2 → ( 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 n­by­n 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) = n​2  i ​ i 8​problems each of size n/2​   log2n 8 • ( )​2 = n​ • ( )​ → n​2 • 2 → n​ 2 •  ∑ 2 ≈  n​  • C • 2 lo2  = n​3  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 2­by­2 matrices with only 6 scalar multiplications… impossible  ­ two 3­by­3 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  z​2​because k = 2  zn 7 5 + z•n •  10 + C​2​• 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 + Z​k​ n • 4k+2 + C​k​n ≤ Z​k​ n  1 3k+1 n • Z​k​2k+1 + 4k+2 ) + Ck​≤ Z​k​we get rid of n  1 3k+1 Z​k​2k+1 +  4k+2) + C​k​ Z​k  Z​ (3l+3) + C​  ≤ Z​ ←→ Z​ (1 ­ 3k+3 ) ≥ C​  k​4k+2 k​ k​ k​ 4k+2 k Z​  ≥ (4k+2 − 3k )​3 • C​  k​ 4k+2 k Z​  ≥ (4k+2) • C​we want Z​ to be as good as possible so we use equal sign  k​ k−1 k k ​ Z​k​= (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 • C​3  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 n­by­n in time n​  2.81    → n­by­n 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

×

×

### BOOM! Enjoy Your Free Notes!

×

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'

## Why people love StudySoup

Jim McGreen Ohio University

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Anthony Lee UC Santa Barbara

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Steve Martinelli UC Los Angeles

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com