### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Design and Analysis Of Algorithms CSC 505

NCS

GPA 3.94

### View Full Document

## 57

## 0

## Popular in Course

## Popular in ComputerScienence

This 4 page Class Notes was uploaded by Jaden Jakubowski on Thursday October 15, 2015. The Class Notes belongs to CSC 505 at North Carolina State University taught by Matthias Stallmann in Fall. Since its upload, it has received 57 views. For similar materials see /class/223814/csc-505-north-carolina-state-university in ComputerScienence at North Carolina State University.

## Reviews for Design and Analysis Of 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/15/15

CSC 505 Spring 2005 A Search A Practical Variant of Dijkstra s Algorithm page l of The generic Dijkstra plus fudge factor77 algorithm is often referred to as A search De ne d u du and assume that the RELAX algorithm is rewritten as RELAxu v w newCost lt7 du wuv 7 if d v gt newCost then d v lt7 newCost u lt7 u endif end RELAX Now we want to prove the following assume 0 where t is the desired destination and let 6su the total cost of the shortest path from s to H d u 7 2 68 u for all vertices u E0 If d u lt 00 there is a path from s to u with total cost d u 7 and u is Ms predecessor on that path 3 If u E S in the current tree then d u 7 6sul These three together imply that when t E S the algorithm we have found the shortest path from s to t The rst two items are easy to prove inductively using the same arguments as for Dijkstra s algorithm For the third item consider the point in the algorithm when u is chosen to be added to S iiei it has the smallest d u value among all vertices not in 5 As in the proof of Dijkstra s algorithm let P be an arbitrary path from s to u and let Pij denote the part of P between vertices i and j Then wP wPs wzy wPyu where my is the rst edge that leaves the set S 2 d m 7 wzy wPy by induction iiei using the fact that d m 7 68 1 S cost of an arbitrary path from s to z 2 d m 7 wz y 7 this will be true as long as 7 is always a ower bound on t 6 total cost of a path om y to u as for example when Euclidian distance from 2 to t 2 d y 7 because d z 7 wz y was a pos sible value for newCost when I was visited 2 d u 7 hey we chose u as the next vertex to add to S of course u and y could be the same vertex Important this proof works as long as for any pair of vertices u and v 7 is either a correct or an underestimate of 6uvl 080 505 Fall 2001 Notes from 16 NOV 2001 M 3136 1 of 3 pioo Team guts D Inva aMs r quottree gamma gamma Prim s Magusd b 3ksms A SH mat wquot 8 a MS nun me wuss pctoet 5 s wwmms We nu moot as v wk v 1 M MM Mons wvlt Ota ksha st ol l39h 50 time t a he 0ng 3quot arcs QT egg 2 2 s 2 39ErwmrcL m Equot k k a D FS LGLK ProWR 5 a U 3 Coo39139 59W L verfoc Ts 0M3 beiwm 39s 9mnkkt5 3 CSC 505 Fall 2001 Notes from 16 NOV 2001 page 2 C3 Remus ovx ndmcmm K E ltE E K N Wm 39em Min nd N 2 B M 534M MM 5 U 5 W K E KE K3 E K mt Walks S m KL OJ 2mm ob Ts 90 but 5 4quot 39 W 9 Amam w quotKE K 0K Marc E K quot MA m quot stuesm ex acb u of smut vd39o m Solu w C a 2 smdM x j 1 080 505 Fall 2001 Notes from 16 Nov 2001 page 3 C 6 Shine pmpelh es Gupk G 5 smC VQCj QA 1 P o The ciag 035 S CC s has CL wdwlf CL We erfh CQSbMe V HcKS 06 we SCC 3 each 0m lt9 3ch MiGSQMS cm SCC 0 xjogfgs vm C SemlcmnededL agt Me was a 9ch M MM QM veri es quotIn W 30 13 Suepose M s 0 Suck pamomi let P bake paxkof the Sec MW the Mosf Vefh ces Let X be a vafcx MT M PM 21 xe sec mswgi 5 6 X Lu Y be aka as We at cande M3 ewesscrws 03 x Mot E be we rst fm39ex 4RQCDMK MV 6 M SMQSSMS Them YX amLXZ Musk be 813618 of he scc ampagcmtmamp ivw chow of 9 as Nutmeg we km Hwai Y amt Z extsk because 3 ts Smlcomedesi CW3 ve x muS r am he a pmcsassm or successorof Q m hem We SCC 65m 6 actgotta If 6amp3 WW cmutcLCvxeA both de W Successors mam mucug acacia xwudutvu6 X awk ai W Extsfmce sf VCLH L IS G SemCmmed fL This pad Cs ens 1390 amp0 dimd g Choose M5 podf 0 Ierftcgs u Miv ML at CK MAL CV he air Scds 1 Cw CV quot33 11W bf namtsa If CK Qrece39oles CV on m Ja y muffmes obvimgo Oka M mo V In 5 mamp vice verm7 Cy wade Cw g

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

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

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