New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Week 6 CMPS 102 Notes

by: Shanee Dinay

Week 6 CMPS 102 Notes CMPS 102

Shanee Dinay
GPA 3.94

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Week 6 notes for CMPS 102, Algorithm Analysis. Topics include Greedy Algorithms, Prim's Algorithm, Kruskal, Clustering.
Algorithm Analysis
Dimitris Achlioptas
Class Notes
CMPS 102, Greedy Algorithms, Prim's Algorithm, Kruskal, Clustering
25 ?




Popular in Algorithm Analysis

Popular in ComputerScienence

This 5 page Class Notes was uploaded by Shanee Dinay on Sunday February 14, 2016. The Class Notes belongs to CMPS 102 at University of California - Santa Cruz taught by Dimitris Achlioptas in Winter 2016. Since its upload, it has received 62 views. For similar materials see Algorithm Analysis in ComputerScienence at University of California - Santa Cruz.

Similar to CMPS 102 at UCSC

Popular in ComputerScienence


Reviews for Week 6 CMPS 102 Notes


Report this Material


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/14/16
Day 11 ­ 2/9/2016  CMPS 102    HW #2  5, 3, 7, 6, 9, 10  less trips is better load  HW #1  think of it as erasing symbols so that the sequence goes down to the subsequence of  the cow  do not find an algorithm that tries to find all the subsequence  HW #3   for each cow  milking, then drinking/then eating  milking can only happen one per time, only one cow can be milked  HW #4  as small as possible ­ subject to the subgraph that it is a spanning subgraph  additional condition ­ want to make sure that you look at any path, it does not have an  edge that is very long  to satisfy a and c, take the entire graph  the tediousness for every pair of vertices is not greater than the tediousness of the entire  graph  prop 3… false. you provide a counterexample  if prop 1 is true then everything else follows    Greedy Algorithms  MST  Simplifying assumption. All edge costs c​ e​are distinct  Cut property. Let S be any subset of nodes, and let e be the min cost edge with exactly  one endpoint in S. Then the MST contains e.  Cycle property.    Proofs  cycle. Set of edges the form a­b, b­c, c­d, d­a…. = cycle  cuteset. a cut us a subset of node S. The corresponding cutset D is the subset of edges  with exactly one endpoint in S  Cycle­Cute Intersection  ­ claim. A cycle and a cutset intersect in an even number of edges  ­ Simplify assumption. all edge costs c​ e​e distinct  ­ cut property. Let S be any subset of nodes and let e be the min cost edge with exactly  one end in S. Then the MST T* contains e  ­ Pf  ­ suppose e does not belong to T* and let’s see what happens  ­ adding e to T* creates a cycle C in T*  ­ edge e is both in the cycle C and in the cutset D corresponding to S → there  exists another edge, say f, that is in both C and D  ­ T’ = T* U {e} ­ {f} is also a spanning tree  ­ since c​e​ c​f​cost(T’) < cost(T*)  ­ this is is a contradiction  ­ Simplifying assumption. All edge costs c​ e​are distinct  ­ Cycle property. Let C be any cycle in G, and let f be the max cost edge belonging to C.  Then the MST T* does not contain f.  ­ Pf  ­ suppose f belong to T* and let’s see what happens  ­ adding f from T* creates a cycle C in T*  ­ edge e is both in the cycle C and in the cutset D corresponding to S → there  exists another edge, say e, that is in both C and D  ­ T’ = T* U {e} ­ {f} is also a spanning tree  ­ since c​ < c​, cost(T’) < cost(T*)  e​ f​ ­ this is is a contradiction  Prim’s Algorithm: Proof of Correctness  Prim’s Algorithm.  ­ initialize S = any node  ­ apply cut property to S  ­ add min cost edge in cutset corresponding to S to T, and add one new explored  node u to S  Shortest Path ­ Dijkstra  MST  ­ maintain a growing partial solution  ­ maintain a growing partial solution  ­ grow by one vertex at a time, the  ­ grow by one vertex at a time, the  vertex being the cheapest to attach  vertex being the cheapest to attach  ­ cheapest edge plus all the edges  ­ cheapest edge  leading from source  Implementation. use a priority queue aka Dijsktra  ­ maintain set of explored nodes S  ­ for each unexplored node v, maintain attachment cost a[v] = cost of cheapest  edge v to a node in S  ­ O(n​2) …  Kruskal’s Algorithm: Proof of Correctness  Kruskal’s Algorithm  Greedy Algorithms  ­ Kruskal’s Algorithm: start with T = . Consider edges in ascending order of cost. Insert  edge e in T unless doing so would create a cycle  ­ Reverse­Delete Algorithm: start with T = E. Consider edges in descending order of cost.  Delete edge e from T unless doing so would disconnect T  ­ Prim’s Algorithm: start with some root node s and greedily grow a tree T from s outward.  At each step, add the cheapest edge e to T that has exactly one endpoint in T  ­ Remark: all three algorithms produce an MST  ­ Reverse­Delete Algorithm  ­ Proof of Correctness: Gives us that if the edges all have distinct lengths, can we  prove that there is only one min spanning tree  ­ all edges have different length → one minimum spanning tree  ­ Prim’s execute is unambiguous  Now we will use Prim’s to prove the correctness of Reverse Delete  ­ claim now, if edges are distinct then MST is unique  ­ if edges are unique, and edge does not belong in MST, remove that edge does not  change MST  Reverse­Delete considers edges in decreasing cost  ­ if we were to remove first edge in order, does it disconnect graph? if no then throw away  edge  ­ RD(n) = “The RD algorithm given a graph with n edges with distinct weights will correctly  decide if the heaviest edge belongs in the unique MST  ­ ∀ n ≥ 1, RD(n) is true  Kruskal’s Algorithm: Proof of Correctness  Kruskal’s algorithm  ­ consider edges in ascending order of weight  ­ case 1: if adding e to T creates a cycle, discard e according to cycle property  ­ case 2: otherwise, insert e = (u, v) into T according to cut property where S = set  of nodes in u’s connected component    Day 12 ­ 2/11/2016  CMPS 102    * Cut property. Let S be any subset of nodes, and let e be the min cost edge with exactly one  endpoint in S. Then the MST contains e.  * Cycle property. Let C be any cycle in G, and let f be the max cost edge belonging to C. Then  the MST T* does not contain f.    Kruskal’s Algorithm  ­ consider edges in ascending order of weight  ­ case 1: if adding e to T creates a cycle, discard e according to cycle property  ­ case 2: otherwise, insert e = (u, v) into T according to cut property where S = set of  nodes in u’s connected component  ­ Proof of Correctness: by adding the next edge that is biggest currently we make a cycle,  and by definition it is the biggest edge in the cycle so it is correct to reject it  ­ any rejection decision is always correct, consider the edge, if it creates a cycle we reject  it because it is the biggest edge because we considered the edges in increasing weight.  So the edges in the cycle are cheapest than the newest edge in the cycle  ­ the decision to be rejected does not depend on the correctness of the edges chosen  before them  ­ acceptance: the cut rule helps us to argue that accepting an edge is correct. Cut rule  shows us that the edge we add is the minimum  ­ assume that our cheapest edge is not the first to be examined, that in the past a different  edge was examines, but if it was examined it was rejected because it is not currently in  the picture. Every rejection decision is based on the formation of a cycle. For the other  edge to be examined and rejected it would have made a cycle, but the addition of the  edge does not form a cycle. So it cannot be that something that is forming a cycle now is  did form a cycle before. Our assumption was that the other edge was examined earlier to  reach our contradiction.  ­ Implementa.  n​ ­ Use the uinni the MST  ­ maintain set for each connected component  ­ O(m log n) for sorting and O(m α (m, n)) for union­find.  O(m log n )  for sortO( α (m, n)) essentially a constant  ­ Kruskal(G, c) {  or egesweghs s tatc1​ 2​ ..  ≤cm   ← ϕ     orac (  ∈ V)mae ase cntanig ingetn     ori  1 o   (, )  ei  i (u nd  ae n dffret sts {  T  TU ei​ megeth ses onainngu nd   }  etrnT  }  ­ find works in constant time. we look at the leader  ­ fin(x, y)  ­ the smaller component leads the bigger component, few vertices end up increasing their  length by one  4.7 Clustering    k­clust. Divide objects into k non­empty groups  distance fun. assume it satisfies several natural properties  ­ d(, ) = 0 = p​ (identity of indiscernibles)  i​ j​ i​ j ­ d(i​ j​ 0 (nonnegativity)  ­ d(, ) = , )​ (symmetry)  i​ j​ j​ i​ spaci. min distance between any pair of points in different clusters.  clustering of maximu. given an integer k, find a k­clustering of maximum spacing.  spacing = minimum distance between two points that are in different clusters  we want to find the clustering that maximizes the minimum distance, we want to find the partition  such that if two things are in different clusters such that their distance is something.  single­link k­clustering algorithm  ­ form a graph on the vertex set U, corresponding to n clusters  ­ find the closest pair of objects such that each object is in a different cluster, and add an  edge between them  ­ repeat n­k times until there are exactly k clusters  key observation.​  This procedure is precisely Kruskal’s algorithm (except we stop when there  are k connected components)  remark​ . equivalent to finding an MST and deleting the k­1 most expensive edges  theorem​ . Let C* denote the clustering into k pieces formed by deleting the k­1 most expensive  edges of a MST. C* is a k­clustering of max spacing  Pf​. Let C denote some other clustering C​ , … C​   1​ k st​ ­ the spacing of C* is the length d* of the (k­1)​  most expensive edge  ­ let p, p​ be in the same cluster in C*, say C*​ , but different clusters in C, say C​  and C​   i​ j​ r​ s​ t ­ some edge (p, q) on p​ i​ pj​ath in C*, spans two different clusters in C  ­ all edges on p​ i​ pj​ath have length ≤ d* since Kruskal chose them  ­ spacing of C is ≤d* since p and q are in different clusters  Main thing to get from lecture: one algorithm is find MST of graph then pick it up and then delete  the two heaviest edges, this will create 3 connected components. Alternative, run kruskal until  you have three cheese curds. Kruskal picks up the edges of the MST in order of increasing cost.    Midterm is Divide and Conquer and Greedy Stuff  ­ either 2 or three problems on midterm that you are supposed to solve in two hours  ­ the problems will be similar to the hw problems  ­ given situation  ­ argue correctness of algorithm  ­ argue runtime  ­ gives us very very strong hints as to what the algorithm should be, then our job will  consist of proving that the algorithm works  ­ run time analysis will not be hard, you will not need to know the master theorem just  know the recurrence relation  ­ main thing correctness proof  ­ for greedy part: typical exchange…  ­ if someone for a particular input, if someone claims there is a better solution, you  say that by changing it around your solution turns out to be the best solution  In Section: they will tell us how to solve homework 2    Dynamic programming…    


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Jim McGreen Ohio University

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

Anthony Lee UC Santa Barbara

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

Steve Martinelli UC Los Angeles

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


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

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.