### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Class Note for CSCI 212 with Professor Choi at GW (4)

### View Full Document

## 29

## 0

## Popular in Course

## Popular in Department

This 5 page Class Notes was uploaded by an elite notetaker on Saturday February 7, 2015. The Class Notes belongs to a course at George Washington University taught by a professor in Fall. Since its upload, it has received 29 views.

## Popular in Subject

## Reviews for Class Note for CSCI 212 with Professor Choi at GW (4)

### 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: 02/07/15

CSCI 21210 Computer Algorithms I Lecture Notes March 3 2009 1 Review Recall that Prim7s algorithm and Kruskal7s algorithm are used to nd a minimum spanning tree MST for a connected weighted graph We proved that the time complexity for Prim7s algorithm is 00 and Kruskal7s algorithm is log log n7 where E refers the to number of edges and V refers to the number of vertices in a graph We have two algo rithms that both give us a MST We must determine which algorithm would be appropriate for an arbitrary graph Let G be a full graph Recall that a full ie complete graph is a simple graph in which every pair of distinct vertices is connected by an edge We have shown in class that n 7 l S S 271 Generally for a very full graph7 0n2 lf 07127 then the complexity for Prim7s algorithm and Kruskal7s algorithm is 00 and On2 log Clearly Prim7s algorithm is the better choice for a full graph Now consider G to be a planar graph A planar graph can be drawn on a 2D plane in such a way that its edges intersect only at their endpoints ie no two edges cross each other Theorem If G is a planar graph7 then 3 3n 7 6 The importance of this theorem is to demonstrate that there is some limit to the number of edges a planar graph can have We notice that is no more than In this case7 then the complexity of Prim7s algorithm and Kruskal7s algorithm is 00 and n log 71 respectively Clearly we see that Kruskal7s algorithm is a better choice for a planar graph For an arbitrary graph G7 Prim7s algorithm is generally better but it ultimately depends on WW 2 Correctness of Prim s Algorithm To prove the correctness of this algorith7 we must show that Prim7s algorithm constructs a MST where the cost is the smallest Recall that a graph G can have multiple MSTs7 but each of them must have the same smallest cost Proof Proof by induction Let T be a MST obtained by Prim7s algorithm Let T1 239 S 239 S n denote the tree constructed by Prim7s algorithm after the 2th iteration Choose an arbitary start node called 5 lnitially7 T1 contains the start node and no edges because it is a single node T2 contains 5 and a vertex mm with weight mm and the edge between 5 and 1 Note that this edge will have the smallest cost compared to all other nodes that s is connected to If there is a tie between two nodes where their weights are equal arbitrarily choose a single node Eventually Tn T because it contains all the nodes in G Lemma For each 2 1 S 2 S 72 there exists a MST F such that TZ Q Fi On the rst iteration we have T1 On the second iteration we have T2 T17T27T37 7Tn T For each of these trees there exists an F that includes everything in T T1 F17T2 F27 7Tnan Notice that T and F could be equal or unequal because there can be multiple MSTs for a graph Eventually we see that Tn Q Fn Because Fn is a MST then Tn must also be a MST This is what we want to prove All we need to prove is that Tn Q F but proving T1 Q F1 Tn Q Fn is easier and stronger to do We can use induction for this Using induction on 2 I 2 1 This is a trivial case Clearly T1 Q F1 where F1 is any MST U Assume that for each 2 1 S 2 S j 7 1 and some j T Q F where F is a MST I Now consider the jth iteration Pick any x y pair from the two sets Vb which represents the nodes at iteration Tj1 and V 7 V5 which contain the nodes at Fj1 We know that Tj1 Q Fj1 a MST z comes from T and y comes from F We also know that lVT1l j 7 1 There are two cases for the pair Case 1 my 6 Fj1 This edge is found in Fj1 so we can safely add it to T without causing any cycles We can let Fj Fj1 because we are moving the node y to Now we can add node my ie Tj1 Clearly Q Frl Fj Case 2 my Z Fj1 Because 2 y is not found in Fj1 it is found in Tj1 This is a problem because a cycle is formed and a MST cannot have any cycles To x this problem let us de ne a new graph T such that T Fj1 my 7 639 639 is an edge that connects V6 and V7 Vb by adding my and is part of the cycle It is not the same as 6 which is the edge between z and y By de nition of Prim7s algorithm we know that w62ght6 w62ght639 because we always keep the edge with the smallest weight Basically we created a cycle by adding my with edge 6 so we take out edge 639 to eliminate the cycle Now let us look at the weight of T wT wF71 w6 7 LU639 S wFJ1 This implies that wT wF1 which satis es case 2 so induction is complete 2 1 There is a special case if w6 lt LU6 but the algorithm is still correct and the proof is similar to above 3 Correctness of Kruskal s Algorithm First start by sorting the edge weights such that w61 S w62 S S w6n where n Relabel the edges such that edges 6162 76n1 are added in this order to construct a Kruskal7s MST Tk For any other MST T other than Tk T 31 Tk7 de ne fT j 1 S j S n 71 where j is the smallest index such that 6739 Z T ie 61 627 7671 E T but 6739 Z T We do this because if 6739 was included7 then essentially T Tk Our goal is to show that 61 627 6n1 is a MST Let T be a MST such that T 31 Tk and fT is the largest because there can be more than one MST Let fT l which implies that 61627 7611 6 T but 61 Z T Consider a graph where we add edge 61 to T This will form a unique cycle 0 such that 0 includes an edge 6 such that 6 Z Tk Everything from this cycle is coming from Tk but this cannot be true because Tk cannot have a cycle So there must be at least one edge in the cycle that is not in Tk Now lets examine the weights between 6 and 61 There are two cases Case 1 w6 lt w6l This case cannot happen Kruskal7s algorithm must have already considered 6 but already added 61 so we cannot add 6 Case 2 w6 2 w6l De ne T0 T6l76 Clearly this is a MST Then wT0 wTw6l7w6 so wT0 S wT This implies that wT0 wT and w6 w6l and fT0 gt fT Z This is a contradiction to the choice of T because we said T was the largest and we showed it is not 4 More MST Problems Theorem Given graph G let a1 3 a2 3 as S S owl and b1 3 b2 3 b3 3 S bn1 be sequences of edge weights of two arbitrary MSTs7 A and B Let wA wB Then 11 bl for 1 S 239 S n 7 1 The edges may be different7 but the weight is the same This is left as an exercise for the students 5 Shortest Path Problem Given a directed edge weighted graph G the goal is to nd a path between two vertices such that the total weight of this path is minimized compared to any other path Today7s lecture discussed Dijkstra7s algorithm7 which assumes that all weights are non negative The pseudocode for the algorithm can be found on the class notes We iterate over 71 nodes during execution For each node examined7 we must update costs for all other 71 nodes Updates are done in 01 time This means the overall time complexity is 00 51 Proof of Correctness Proof Let V z denote the set of vertices in V after the 2th iteration of the algorithm For example7 V 1 s s is the source vertex Let ui denote the vertex in V 7 V z39 7 1 selected at the 2th iteration Let at the 2th iteration be the distance from the source to ui Recall that the distance is the length of the shortest path in G from s to ui We are now going to construct the shortest path tree Once we select a node7 it will be a permanent member of our shortest path tree We can use induction on 239 for this proof Assume the claim is true for iterations up to 239 7 1 Now lets consider the 2th iteration At this step7 we select a ui from the set V 7 V z39 7 1 and add it to our current shortest path P Let P lt57w17w2 wk7ui where LU17 LU27H39 wk 6 V z39 7 1 ie the nodes that are already in our shortest path We want to prove that this path is the shortest We will use a contradiction to prove it Now suppose that P is not the shortest path in G from s to ui De ne a new path Q 72122 721111 that is the shortest path wQ lt wP Focus on Q Let zq be the smallest index in s 21 22 zq72q11 721111 such that 21 zq V z39 7 1 This means that 2q1 E V 7 V z39 7 1 Below shows where each of the terms are coming from 8 21 22 39 39 39 Zq 2q1 39 39 39 21 ul 7 7 7 7 7 7 7 V i71 V7V i71 7 Note that 2q1 37 ui Because we chose 2q1 instead of ui for our shortest path7 we know that lzq1 2 Let7s examine Q in two separate subpaths Let Q1 72122 72q1gt and Q2 111 7ui Clearly the weights of these two subpaths Q1 and Q2 sum to Q Now lets examine the individual subpaths We know that wQ1 lzq1 We also know that wQ2 gt 0 because there are some vertices addded to the shortest path after Zq1 Because we have non negative edge weights7 the weight must be greater than zero To summarize We know that wP so we see that wQ gt wP This is a contradiction because Q cannot be greater than P This implies that P is the shortest path D

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

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

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