Algorithm Design and Analysis
Algorithm Design and Analysis CSE 565
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.
Reviews for Algorithm Design and Analysis
Report this Material
What is Karma?
Karma is the currency of StudySoup.
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