### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Algorithm Design and Analysis CSE 565

Penn State

GPA 3.53

### View Full Document

## 32

## 0

## Popular in Course

## Popular in Computer Science and Engineering

This 0 page Class Notes was uploaded by Libby Kuhlman on Sunday November 1, 2015. The Class Notes belongs to CSE 565 at Pennsylvania State University taught by Staff in Fall. Since its upload, it has received 32 views. For similar materials see /class/233118/cse-565-pennsylvania-state-university in Computer Science and Engineering at Pennsylvania State University.

## Popular in Computer Science and Engineering

## Reviews for Algorithm Design and Analysis

### 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: 11/01/15

Algorithm Design and Analysis Divide and Conquer Integer Multiplication Karatsuba s algorithm Matrix Multiplication Strassen s algorithm m LECTURE 15 Sofya Raskhodnikova ReView use asymptotic notation The statement my alogirhtm takes time 2n is not accurate 7 Do you mean 2n seconds 2n minutes 7 The exact running time depends on the processor Use asymptotic notation my alogirhtm takes time 901 It means that the running time is proportional to n The same applies to space complexity am Last time order statistics Deterministic 0n time algorithm There is a randomized algorithm that runs in expected linear time The randomized algorithm is far more practical Exercise Why not divide into groups 0f3 7 W Multiplying large integers Given nbit integers a b in binary compute cab am an do Naive gradeschool algorithm X b b b W mbimm 7 Compute n intermediate products 1 bits 0 7 Do n additions 7 Total Work nl oo o Multiplying large integers Divide and Conquer Attempt 1 7 Write a A12m A b B1 2 B0 7 We Want ab A13 2quot ABC Ble 2m A080 7 Multiply n2 7bit integers recursively 7 Tn 4mm n 7 Alas this is still nl Master Theorem Case 1 El Multiplying large integers Divide and Conquer Attempt 1 7 Write a A12 2 A0 B 2m B0 7 We Want ab A13 2quot A180 BIAO 2m A080 7 Karats s idw 0 A081 8140 7 We an get away with 3 multiplications in yellow x AiBI y A030 1 A0AiBoBi 7NoW we use ab A1812 AlB0 BlAO 2 1 A080 x 2 z x y 2m y Multiplying large lntegers MULTIPLY n a b gt a and b are nrbit integers gt Assume n is a power of2 for simplicity Ifn S 2 then use graderschool algorithm else Ale divzm BLltb divzm Aqeamodzm BGltbmod2m x e MULTrPLYn2 A1 B y e MULTIPLYn2 A0 BO z e MULTIPLYn2 A1A0 31Bo Output x 2 z x y y 2 y T39QVZAS JN 91 Multiplying large integers The resulting recurrence Tn 3Tn2 n Master Theorem case 1 T01 3 quot1053 901159 Note There is a n log n algorithm for multiplication more on it later in the course A wquot W Matrix multiplication Input AaijBbijgt 0utputCcijAxB 1 1 2 quotquotquot39 Cu 012 Cin 1111 1112 in bu bll bin 021 022 Cln 1121 1122 in 521 1 22 bin CH 912 Cnn 1M n2 11m bnl bnl bnn n Cij Zaik bkj kl g Standard algorithm forilt 1ton do forjlt 1ton do 5174 0 forklt 1ton do cijlt cijaikx bk Running time 2 n3 Divideandconquer algorithm IDEA ngtltn matrix 2 2X2 matrix of n2gtltn2 submatrices st 3mg C A X B r 16 bg recursive s af bh 8 mults of nZ gtltn2 submattices t 2 Ce dh 4 adds of nZ gtltn2 submatrices n cf dg El Analysis of DampC algorithm Tltngt r H o snbmatrices work adding snbmatrices submatrix size n1 gba nlogzzg n3 2 CASE 1 D Tn n3 N0 better than the ordinary algorithm m Strassen s idea Multiply 2X2 matrices with only 7 recursive mults P1axltfehgt P2abgtlth P3cdgtlte P4dxltgiegt P5adgtlteh Psbdgtltgh P7ltaecgtxltefgt r P5P47P2P6 7 mults 18 addssubs Note No reliance on commutativity of multiplication 93 Strassen s idea Multiply 2X2 matrices with only 7 recursive mults P1agtltf7h rP5P47P2P6 P2abgtlth adeh P3cdgtlte dg7e7abh P4dgtltg bgh aeahdedh dg7de7ahibh bgbh7dgidh aebg P5adgtlteh Psbdgtltgh P7ltaecgtxltefgt mm A M am Strassen s algorithm 1 Divide Partition A and B into ii2 x ii2 submatrices Form terms to be multiplied using and 7 2 Conquer Perform 7 multiplications of ii2 x ii2 submatrices recursively 3 Combine Form product matrix C using and 7 on ii2 x ii2 submatrices m 7 Tn2 nz g Analysis of Strassen Tn 7 Tn2 nz limb n1 gl7 a iii81 2 CASE 1 D Tn nlg7 Number 281 may not seem much smaller than 3 But the difference is in the exponent The impact on running time is significant Strassen s algorithm beats the ordinary algorithm on today s machines for n 2 32 or so Best to date of theoretical interest only n2375 39

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

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

## Why people love StudySoup

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

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

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

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.