### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Advanced Algorithms CS 5050

Utah State University

GPA 3.85

### View Full Document

## 18

## 0

## Popular in Course

## Popular in ComputerScienence

This 14 page Class Notes was uploaded by Reed Aufderhar on Wednesday October 28, 2015. The Class Notes belongs to CS 5050 at Utah State University taught by Vicki Allan in Fall. Since its upload, it has received 18 views. For similar materials see /class/230447/cs-5050-utah-state-university in ComputerScienence at Utah State University.

## Reviews for Advanced Algorithms

### 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: 10/28/15

Matrix chain multiplication is an optimization problem that can be solved using dynamic programming Given a sequence of matrices we want to nd the most ef cient way to multiply these matrices together The problem is not actually to perform the multiplications but merely to decide in what order to perform the multiplications We have many options because matrix multiplication is associative In other words no matter how we parenthesize the product the result will be the same For example if we had four matrices A B C and D we would have ABCD ABCD ABCD ABCD We could go through each possible parenthesization brute force but this would require time 92quot which is very slow and impractical for large n One simple solution is called memoization each time we compute the minimum cost needed to multiply out a specific subsequence we save it If we are ever asked to compute it again we simply give the saved answer and do not recompute it Since there are about n22 different subsequences where n is the number of matrices the space required to do this is reasonable It can be shown that this simple trick brings the runtime down from 02quot to On3 which is more than efficient enough for real applications This is topdown dynamic programming Dynamic Programming Another solution is to anticipate which costs we will need and precompute them It works like this For each I from 2 to n the number of matrices Compute the minimum costs of each subsequence of length I using the costs already computed dim is the sizes of the matrices Matrix Ai has the dimension dimil x dimi costij is the best cost of multiplying matricies i through j sij saves the division point so you can actually report the matrix multiplication order void matrixChainOrderint dim l int cost new int SIZE1 SIZE1 int s new int SIZE1 SIZE1 int matrith dimlength l for int i l i lt matrith i actually not needed in Java costii O Fills in matrix by diagonals for int l2 llt matrith l l is chain length for int il ilt matrith ll i int j il l costij lntegerMAXVELUE computing the best cost so far Try all possible division points ik and kj for int ki kltj l k int thisCost costik costklj dimi ldimkdimj if thisCost lt costij costij thisCost Slil j k Cost of matrix Multiplies A B C D E F 0 A 0 5 00 2100 2250 2220 2820 B 0 0 2000 2300 2150 3130 C 0 0 0 3000 690 8330 D 0 0 0 0 90 330 E 0 0 0 0 0 1800 F 0 0 0 0 0 0 1 Save division points TJP JUOUJCD CJO o o o o v cgto o o o H w cgto o o N H O CJO o m m m U cgto m m m m cgtm m m m w m The s165 means divide ABCDEF after the fifth matrix so divide as ABCDEF To find the next division point see s15 3 so ABCDEF To find the next division point see s13 1 so ABCDEF Looking for a senior project Considerturningyour first programming assignment optimal binaw search trees into a manipulative tool to help other students learn the concepts We solved the Optimal Binaw search tree three ways See httpwwwcsusueduZNallanchsSOSOchSOSOhtml Problem 1 1 Greedin 2 Using exhaustive recursion 3 Using Memoizing A logical extension is to solve itvia dynamic programming Things you could add 1 Interact with the user so they can pick problem size orfrequency values 2 Allow the userto pick a greedy strategy a Select largest frequency b Select node nearest the middle ofthe keys to get a balanced tree c Other strategies 3 Show how you use dynamic programmingto not only find the cost ofthe optimal binaw search tree but build it i 1 2 3 4 S p 024 022 023 03 001 Backtrack the Optimal BS39l39 Recording every r during filling l 7 quotIE I99 2 IN i3 CM 75 78 i 3 Kay 4 0 my 4 Show the tree you create graphically See the demo at httpzwebpagesullesusers39rierazDocenciaAVLZAVL oZOtree20applethtm for ideas Perhaps you would show the nodes with a size proportional to its frequency 5 Demonstrate the time required to use the various methods 0 Notation Big Oh We want to give an upper bound on the amount of time it takes to solve a problem defn vn Ofn gt El constants c and no such that lvnl S clfnl whenever n gt no Termed complexity has nothing to do with difficulty of coding or understanding just time to execute Important tool for analyzing and describing the behavior of algorithms Is an n2 algorithm always better than a n3 algorithm No it depends on the speci c constants but if n is large enough an On3 is always slower Complexity Class 01 Olog n On On log n Onz 02quot For small n c may dominate Intractable all known algorithms are of exponential complexity Measuring Complexity 1 Additive Property If two statements follow one another the complexity of the two of them is the larger complexity Om On Omaxnm 2 If Else For the fragment 3 if cond then 81 else 2 The complexity is the running time of the cond plus the larger of the complexities of SI and 2 4 Multiplicative Property For Loops the complexity of a for loop is at most the complexity of the statements inside the for loop times the number of iterations However if each iteration is different in length it is more accurate to sum the individual lengths rather than just multiply Nested For Loops Analyze nested for loops inside out The total complexity of a statement inside a group of nested for loops is the complexity of the statement multiplied by the product of the size of each for loop Example 1 0mn n ru r The area ofthe gure wru than represent the total work om Example 2 heg lt m beam in he in hEg 1 lt m 1m u x In this example our complexity premre rs mangular Mun2 am 1 Recursive Algorithms mm mathematics approach You shouldbe able to use any two omrerr Example 3 Procedure mm rer 1 1 u x e x 1 J ELM21 all ELM21 end procedure 7002 Tn2 n Thrs rs eaned areeurrerree relaaor In our pmconal mew m m P ur39hwd In other Words the recursive calls xtmakes n lug quot om lug 11 Example 4 Procedure mm m 1 1 x 1 Call mum end procedure T01 1 7012 n A 012quot n m comm ry W m Mm I h 2E Example 5 Procedure mm x x 1 Call ELM21 end procedure T01 7012 1 In on In Example 6 Procedure mm x x 1 Call ELM21 Call ELM21 end procedure T01 27012 1 4 0n A Formula Approach Theorem Tn a Tnb 00 xf a gt bkthe complexity 15 0n by xf a bkthe complexity 15 0nklog n if a lt bk the complexity is Onk In this case a represents the number of recursive calls you make b represents the number of pieces you divide the problem into k represents the power on n which represents the work you do in breaking the problem into two pieces or putting them back together again In other words nk represents the work you do independent of the recursive calls you make Note this corresponds to one row in our pictorial representation Let39s use the theorem to revisit the same problems we solved pictorially Example 3 procedure BN for i l N x x i Call BN2 Call BN2 end procedure a2 b2 kl as work is n Since abk we are in the equals case if a bk the complexity is Onk log n O n log g which is exactly what our pictures told us Example 4 procedure BN for i l N x x i Call BN2 end procedure a1 b2 k1 Since a lt bk we are in the less thanquot case if a lt bk the complexity is Onk On which is exactly what our pictures told us Example 5 procedure BN x x i Call BN2 end procedure alb2 k0 as the work ls l or n a bk as l 2 we are m the equals ease if a bk k log n Example 6 Procedure ELM x x 1 J ELM21 all ELM21 end procedure a 2 b 2 k 0 slhee a gt bkwe are m the quotgreatertham ease if a gt bk the complexlty ls cm a cm 622 0h Whleh ls exactly what our plctures told us Recurrence Relations butyou shouldbe able to denve them Arithmetic Progression Example S35792mUIZWAU whahg the same sumbaekwards s2h1zh7112h7312h7553 Ifwe add the two S s together 5 a 5 9 zhel zh 1 5 2 1 zhel zhea 2h 75 5 3 25 n4 n4 zh41 n4 n4 n4 zs 294 Geometric Progression Example 4E15 32 zquot Multaplym both sides by the base zs41532 Zquotzazquot Subtracting s from 25 we get szozquotrzzquot rz Mathematically Solving Recurrence Relations Example 7 Suppose our reeurrenee relauon rs Tquot za n2 z and T2 1 for m mte n let 1 32 to see the pattern and generanze for any n Tquot ZTnz 2 2m2 mm z zZTquot 22 21m zanyX z 2313x 23 23138 rum5 z Z Tnls 2 Z Tnls 2 1quot2 2 o1z Now by subsmuung each equauon mto une prevrous equauon we have Tarzz 23z z green2 re Nouee une upperlxmxt on me surnrnauon rs relatedto me me ofn Srnee 2 n2 m 1an case we conjecture the upper bound call u b wru always be determined by 2quot n2r e b logm r1 We N n h r Lhe problem 5122 Each time Tarzz 23z z green2 re usmg ourgeomemc sum technique 7 2m 2 Thus TquotZ lZmZZZ ZmZZmZZmZ3mZZ m work For 1 would be mtg m by 15121 checka the case of n 32 we got Tazzz 23z z 45 Smee 3322 r 2 46 we are reasonably tartam we 64de computations eoneeuy T V Tquot ZTnz z Tquot 7 22Tn 2 2 Tquot4Tn 4Z 4ZTnx z 4 2 Tquot TquotETquotx342 TquotEZTquotls2342 Tquot15Tquot515E4Z Butsmcen32 Tquot15Tz15342 Tquot1515E43 7 Tszz 23z z 2239n2 Thus Tquotz rznzzsztznzzmz ZmZ3mZZ Examples Suppose the relation was TquotZTquot2m T1 and me accumulating the results takes time propomonal to n H but for u often useful 1 pt 0 Tr g Tquot quot2 7 i 1 712 Thxs equauon 15 vahdfor any gown oftwo so quot2 7 TM 712 and Tquot Tquot x 1 714 711 Tquot Tquot e 7 15 1 711 7115 T2 T1 7 7 1 z 1 1 L ObserVE ofthe equation and may be eaee11edTA1tee everythmg 15 cancelled we get quot 1 T 7 7 Tquot t 7 1m Example 9 Consxder L sma11este1ement m1 1H k 71 compares to nd the sma11est1swapand then sort the remammg n71 e1ements Tquot 71 anl Ifthere are only two e1ements there 15 a compare and at most 1 swap T2 To see the pattem let s assume 116 Tquot 71 anl Tquotl 7 71 The TV 7 n r z ana Tquota 7 73 Tr Ll l T 7 T 2 Backwards subsmuuon yields 739 Z 73 4 5 6k general TquotZ345m quot234

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

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

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

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

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