### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Algorithms CSCD 320

Eastern Washington University

GPA 3.55

### View Full Document

## 24

## 0

## Popular in Course

## Popular in ComputerScienence

This 19 page Class Notes was uploaded by Oscar Spinka on Sunday October 11, 2015. The Class Notes belongs to CSCD 320 at Eastern Washington University taught by Staff in Fall. Since its upload, it has received 24 views. For similar materials see /class/221499/cscd-320-eastern-washington-university in ComputerScienence at Eastern Washington University.

## Similar to CSCD 320 at Eastern Washington University

## Popular in ComputerScienence

## Reviews for 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/11/15

Thomas J Naps Introduction to Data Structures and Algorithm Analysis 2nd edition West Publishing Company 1992 p 453 quotA Relevant Issuequot sidebar titled quotCritical path Analysis PERT and CPMquot in Chapter 9 Graphs and Networks The network shown below represents roughly the activities involved in building a small house The events are labeled 0 through 10 with node 0 representing the starting time for the project and node 10 representing completion time for the project The dashed edges marked dummy are used to establish precedence relationships only and do not represent real activities of the project They have an associated weight of 0 We associate the following completion times with each activity prepare lot 7 3 lay foundation 7 4 erect external frame 7 10 erect root 7 3 install plumbing 7 9 install electrical wiring 7 7 external walls 7 7 cover roof 7 2 interior walls oor and ceiling 7 nish exterior 7 5 and nish exterior 7 8 Then an examination of the network will show that there is one path in the network 0 9 l 9 2 9 3 9 5 8 9 9 9 10 such that any delay in the completion of an activity in this path will delay the whole project The length of this path is 39 Paths such as this are known as critical paths of the network Interior walls floor ceilings Erect prepare ay external I I lot foundation frame IFH IlSh G lt Install mterror electrical 3 4 in 1 F inish exterior Note In CScD327 this is an example of nding the longest simple path but the algorithm used requires that edges have nonzero values since edges in use are turned negative Consequently the data le for this example has used edges of weight 1 for the dummy edges 58 and 68 Listing of All Simple Paths 0 to l 3 0 to l 3 0 to l 3 0 to l 3 lto2 4 lto2 4 lto2 4 lto2 4 2 to 3 10 2 to 3 10 2 to 3 10 2 to 3 10 3 to 4 3 3 to 5 9 3 to 6 7 3 to 7 7 4 to 8 2 5 to 8 l 6 to 8 l 7 to 10 5 8 to 9 5 8 to 9 5 8 to 9 5 9 to 10 8 9 to 10 8 9 to 10 8 Total 29 Total 35 Total 40 Total 38 Printed 2010716 at 0751 BTKQE A39DTOtM M 3 TH U Fun SHELL 4 L Am 3 asp1 2159 Fart LA L 4 mGugde 16mm gmzm cl 21 A MR sack 3L kn Find node to inscn inn 5 ri earth keys in node left to gm nding currec place Splh nude inm wu nodes placing hall of kays and pointers In one nude and I hall in the ether with m 6 M 1 m new key in 15 correct Damion 34 IA omen using 73 AH raga 4 J M on 10 uw ridJ C M 1215 DJ aqua IF davf quota I lnnmkev and Hz 94 Quown 0F 3 pointerfm new lt o r 4 nadcinnarmx E quotV s L 015 ML r n J Kev lnL39TJ39 K 9 em a J 7m 0N7 cm 9 lt Crnale mm rounplacin n 39quotI L5 puinxmm both nodeaini L any 13 snumr Hove k 5L 1AL 1 H Mcmr u 21 At Fax22x L4 r x WV 1 3 9 I 5 I cnm I 7 51 mtu ER gt ail 3 II Lil J k E 39 II 5 G rowlh of a Btrue 6 mgt DELETE m quotWW MW quotL A 39a3 mm Cgo tALi F rgshu Z K K 5 9 lpxz casw wi 1 ms SERUM 153 1quot r nal g vvd ide wa J an 39 q g x av Fina amallczx kly mu m mum named 10 av puinm u h right at m TAKKT W1 a A 39 I n Nrvquot hl rmme LJCLISIGVIZ r quotMKZCET K Fl 5 wncmmzauy T3 quot91 A 9 iu A L39lt F W v KEKV Umqu Exchange lhi key valu wuh key value M me Ta 54 K r S 7iquot F I L my hZIgux t 2 K I 7 Tao l L quotquot Yng 6 VwwT ramou 4 Rev vzlua 1mm aiming mm mum and mm a key ham no Earth In lhl mas gmnq x u quola ul klvi siblmg n 39fnaugh key In E u K1 9 t Dal Ian or right av u cm 2 56 Combine mung mm on nod n u o L pzs r xr quotNC 12539s I x a 39 7lt Ca mmmg mum by QZLETQ 5 quot 3 Samba 33 737 115 B T t 39DGL 7 OrLS Lune1 h r 2 Elaine D Full x dawn Full up 1 3 Del d Cambine Cambina a mu dnluu ham lul CScD320 Algorithms Prim s Algorithm Detailed Traces of Execution 1 Node and Edge List Node A edges to B3 Cl Node B edges to A3 Cl DD Node C edges to Al Bl D2 Node D edges to Bl C2 MinHeap AC1 l AB3 C off AB3 47 then enter CB1 CD2 MinHeap CB1 AB3 CD2 B off CD2 l AB3 47 then add BD1 MinHeap BD1 l AB3 CD2 D off CD2 AB3 Drop D AB3 Drop B ltemptygt Prim39s minspanning tree A AC CB BD Weight 3A1 133 02 M4 Printed 10Jul10 2257 Note This graph has a shape somewhat similar to the one for assignment 9 but the different edges and different edge weights will make Prim s Algorithm behave very differently on this graph than it does on the homework assignment Node and Edge List Node A edges to B1 32 35 Node B edges to A1 36 131 F5 Node 3 edges to A2 B6 Dl F Node D edges to 31 F2 31 Node E edges to B1 F3 Node F edges to B5 32 132 133 31 Node G edges to A5 D1 F1 MinHeap AB1 1 A32 AG5 B off A32 1 AG5 i then enter B36 BE1 BF5 MinHeap BE1 1 A32 B36 1 AG5 BF5 E off A32 1 BF5 B36 1 AG5 i then enter EF3 MinHeap A32 1 EF3 B36 1 AG5 BF5 3 off EF3 1 BF5 B36 1 AG5 i then enter 3D1 3F2 MinHeap 3D1 1 EF3 3F2 1 AG5 BF5 B36 D off 3F2 1 EF3 B36 1 AG5 BF5 i then enter DF2 D31 MinHeap D31 1 EF 3F 1 AG5 BF5 B36 DF2 1 3 off DF2 1 EF3 3F2 1 AG5 BF5 B36 i then enter 3F1 MinHeap 3F1 1 EF3 DF2 1 AG5 BF5 B36 3F2 F off 3F2 1 EF3 DF2 1A35 BF5 B36 At this point all vertices are in the MST so that successive removals will be discarded Prim39s minspanning tree a a a A AB BE AC 3D D3 3F Weight 7 A1 132 04 D5 133 F7 36 Printed 10Ju1 1 0 2257 CScD320 Algorithms Dijkstra s Algorithm Detailed Traces of Execution 1 Node and Edge List Node A edges to B3 Cl Node B edges to A3 Cl DD Node C edges to Al Bl D2 Node D edges to Bl C2 MinHeap AC1 l AB3 C off AB3 47 then enter CB11 CD21 MinHeap CB2 AB3 CD3 B off CD3 AB3 47 then test BD12 versus CD3 and reject MinHeap CD3 l AB3 D off AB3 Drop B ltemptygt Dijkstra39s single source shortest path spanning tree A AC CB CD Weight 3A1 133 02 M4 Printed 10Jul10 2257 Note This graph has a shape somewhat similar to the one for assignment 9 but the different edges and different edge weights will make Dijkstra s Algorithm behave very differently on this graph than it does on the homework assignment Node and Edge List Node A edges t Bl C2 G5 Node B edges to Al C6 El F5 Node C edges to A2 B6 Dl F Node D edges to C1 F2 Gl Node E edges to Bl F3 Node F edges to B5 C2 D2 E3 G1 Node G edges to A5 Dl l MinHeap AB1 AC2 AG5 B off AC2 AG5 47 then toss BC6gt2 enter BE1 BF5 MinHeap AC2 AG5 13122 BF6 C off BE2 AG5 BF6 47 then enter cD3 cF4lt6 MinHeap 13132 CD3 BF6 AG5 CF4 E off CD3 CF4 BF6 AG5 7 then toss eF5gt4 MinHeap CD3 CF4 BF6 AG5 D off CF4 AG5 BF6 7 then add dG4lt5 MinHeap CF4 DG BF6 AG5 F off DG4 AG5 BF6 7 then toss fG55 MinHeap DG4 AG5 BF G Off AG5 BF6 At this point all vertices are in the spanning tree so that successive removals will be discarded Dijkstra39s single source shortest path spanning tree A AB AC BE CD CF DG 1M1 B2 03 MS 134 N6 37 Printed 10Ju1 1 0 2257 Pr sM Imum Snann g Tree Algo m a 3 m we 3 M X a m e MmWWWmmmmmwwmwmM gww Pm M w w v m MM m M WuwmsWwwmwww Wm Sedgewlck39stngl 1 Sedgewlck39s mm 12 aned man 22 57 Tron Algorithm y Mm WWW my uywyyyymmmmmm 31 at Wm Wm mm mm Mm WW mm m m mmymmyeym cm my 3quot node obwmslychargesm edgsmme ns 1 k shamstyachs Bumdrmsml39lg mdz m xmum a yy H Mu yummy mm yy quot A m c a n n y my mm a k m y y m rhyyul H yum H M y yum Mme ma we n n y my my my 1 y r u H H J y yhy J m x we W Lu my my m my my my 2 y by 2 H w 2 y m 2 m r we n my my nu my rgtt J y rgtt u H by 2 y by 2 m s we n us my my my Ms rgtn 2 y rgtn 2 H H 1 y bk 1 min we n my my by 2 y by 2 H aw 1 y ha 1 m y a n km 2 by 2 y by 2 H My 1 y x m m 4 we n ymy my my my rgt U y r u H bx 1 y by 1 m x age n my my My 1 y m u H vx J y w J y ak Wage n In my my my my my 1 y m u H m 2 y A 2 m u we n my my bk 1 y Mk 1 H 57gt 3 y My 2 by J y by u H My 2 y gtx 2y M 3 y M 3 H rgtc U y mu y y Sedgewmk39s myquot 31 1 aned mm 22 57 CScD 320 Algorithms Kruskal s Algorithm Detailed Traces of Execution Node and Edge List Node A e ges to B to Node C edges to D edges to Sorted Edge List AC1 Bc1 BD1 CD2 AB3 Printed 10Ju1 1 0 2257 No e A edg s to Node B edges to Node C edges to Node D edges to Node E edges to Node F edges to G Sorted Edge List AB1 BE1 CD1 edges to aned man 22 57 Nude and Edge Lust Made A edges ca Made a edges r am H21 H21 1 H21 mu 5st m2 Em rm m2 n21 m2 LL21 may am um um 55 us may um new cam awn ELLE may 5m us run LL41 p 1 p 1 3 1 I p 1 p 1 AVL Tree Node Violation The Four Weiss Violation Types Sahni39s Notation Included1 Q Left subtree has a height two greater than the right subtree and at the left child the two subtrees are of equal height or the left subtree has a height one greater than the right A single right rotation at the point of Violation will suf ce Sahni LL type imbalance Left subtree has a height two greater than the right subtree and at the left child the right subtree has a height one greater than the left There must be a setup rotation at the left child to the left After that is the rightward rotation at the point of Violation Sahni LR type imbalance Right subtree has a height two greater than the left subtree and at the right child the left subtree has a height one greater than the right There must be a setup rotation at the right child to the right After that is the leftward rotation at the point of Violation Sahni RL type imbalance Right subtree has a height two greater than the left subtree and at the right child the two subtrees are of equal height or the right subtree has a height one greater than the left A single left rotation at the point of Violation will suf ce Sahni RR type imbalance 1 Mark Allen Weiss Data Structures amp Algorithm Analysis in C 2nd edition AddisonWesley 1999 pp 145 ff Sartaj Sahni Data Structures Algorithms and Applications in Java 2nd edition Silicon Press 2005 pp 607 ff Printed on 20100720 at 0127 BTKQE A39DTOtM M 3 TH U Fun SHELL 4 L Am 3 asp1 2159 Fart LA L 4 mGugde 16mm gmzm cl 21 A MR sack 3L kn Find node to inscn inn 5 ri earth keys in node left to gm nding currec place Splh nude inm wu nodes placing hall of kays and pointers In one nude and I hall in the ether with m 6 M 1 m new key in 15 correct Damion 34 IA omen using 73 AH raga 4 J M on 10 uw ridJ C M 1215 DJ aqua IF davf quota I lnnmkev and Hz 94 Quown 0F 3 pointerfm new lt o r 4 nadcinnarmx E quotV s L 015 ML r n J Kev lnL39TJ39 K 9 em a J 7m 0N7 cm 9 lt Crnale mm rounplacin n 39quotI L5 puinxmm both nodeaini L any 13 snumr Hove k 5L 1AL 1 H Mcmr u 21 At Fax22x L4 r x WV 1 3 9 I 5 I cnm I 7 51 mtu ER gt ail 3 II Lil J k E 39 II 5 G rowlh of a Btrue 6 mgt DELETE m quotWW MW quotL A 39a3 mm Cgo tALi F rgshu Z K K 5 9 lpxz casw wi 1 ms SERUM 153 1quot r nal g vvd ide wa J an 39 q g x av Fina amallczx kly mu m mum named 10 av puinm u h right at m TAKKT W1 a A 39 I n Nrvquot hl rmme LJCLISIGVIZ r quotMKZCET K Fl 5 wncmmzauy T3 quot91 A 9 iu A L39lt F W v KEKV Umqu Exchange lhi key valu wuh key value M me Ta 54 K r S 7iquot F I L my hZIgux t 2 K I 7 Tao l L quotquot Yng 6 VwwT ramou 4 Rev vzlua 1mm aiming mm mum and mm a key ham no Earth In lhl mas gmnq x u quola ul klvi siblmg n 39fnaugh key In E u K1 9 t Dal Ian or right av u cm 2 56 Combine mung mm on nod n u o L pzs r xr quotNC 12539s I x a 39 7lt Ca mmmg mum by QZLETQ 5 quot 3 Samba 33 737 115 B T t 39DGL 7 OrLS Lune1 h r 2 Elaine D Full x dawn Full up 1 3 Del d Cambine Cambina a mu dnluu ham lul Expense of Finding the Kth Smallest Element Best and Worst Cases To find the kth smallest element in a not necessarily sorted array we can use the Partition algorithm from Quick Sort Initially the region of interest is I0 as 0 through hi as n71 where n is the number of elements in the array Then we apply the following loop While the region bracketed by lo and hi has more than one entry Apply the Partition algorithm to the region generating pivot subscript mid lf mid is less than k Set Io to mid 1 else if mid is greater than k Set hi to mid 71 else mid is exactly at k Exit the loop early set Io hi mid Let us examine the number of elements processed in finding the kth smallest element 7 and de ne this as kthn We can examine two cases the best case where Partition evenly splits the array segments and the worst case where Partition only discards one element We are going to examine the case where the algorithm continues until the region has size one Obviously the best case has a single call to Partition and that returns as the pivot subscript k itself a Best case 7 partition function leaves n2 after each pass of the algorithm We restrict n to be a power of2 n 2J for somej 3 0 Recurrence kthl 1 Region size 1 return that item Examine n elements in artition lam 7 n lamquot 2 Region remaining has sipze n 2 Prove inductively that kthn 2 n 7 l hence also kzhn 2 2 n 2 7 l kthl l 2 l 7l 1 Basis case established kthn n kzhn 2 Recurrence n 2 n 2 7 1 Substitute the inductive hypothesis n n 71 Algebra 2 n 7 1 Combine n n 7 final result b Worst case 7 partition function leaves n 7 1 after each pass ofthe algorithm Here we restrict n to be a strictly positive number n gt 0 Recurrence kthl 1 Region size 1 return that item klhm n klhm 7 1 Examine n elements in partition Region remaining has Size n 7 l n n 1 n n 7 l Prove inductively that kthn 7 hence also kthn7l 7 2 2 kthl l l 2 2 1 Basis case established kthn n kzhn 7 l Recurrence 2n n n7 l 7 7 Substitute the inductive hypothesrs 2 2 7 7 2n 1 Bring to a common denominator 7 2 Factor out the n 7 n n1 Simplify 7 final result 2 Printed 20107ul716 at 0141

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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

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

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

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