### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Data Structures and Algorithms II CS 362

UNM

GPA 3.76

### View Full Document

## 99

## 0

## Popular in Course

## Popular in ComputerScienence

This 8 page Class Notes was uploaded by Trent Dare on Wednesday September 23, 2015. The Class Notes belongs to CS 362 at University of New Mexico taught by Staff in Fall. Since its upload, it has received 99 views. For similar materials see /class/212209/cs-362-university-of-new-mexico in ComputerScienence at University of New Mexico.

## Reviews for Data Structures and Algorithms II

### 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: 09/23/15

Greedy Algorithms 39 Greed is Good Michael Douglas in Wall Street 0 A greedy algorithm always makes the choice that looks best CS 362 Lecture 9 at the moment 0 Greedy algorithms do not always lead to optimal solutions Jared Saia but for many problems they do University of New Mexico 0 In the next week we will see several problems for which greedy algorithms produce optimal solutions including ac tivity selection fractional knapsack When we study graph theory we will also see that greedy algorithms can work well for computing shortest paths and finding minimum spanning trees 2 l Toda s Outline Activit Selection y I y o Greedy Algorithm Intro 0 You are given a list of programs to run on a single processor 0 Activity Selection 0 Each program has a start time and a finish time o Knapsack 0 However the processor can only run one program at any given time and there is no preemption ie once a program is running it must be completed 39 Ideas Another Motivating Problem I c There are many ways to optimally schedule these activities 0 Suppose you are at a film fest all mOVIes look equally good I o Brute Force examine every possible subset of the actIVItes and you want to see as many complete mOVIes as possible This roblem is also egtltactl the same as the activit selection and nd the largeSt SUbset Of non overlappmg aCtIVItIeS O p y y c Q If there are n activities how many subsets are there 0 The book also gives a DP solution to the problem problem 39 Greedy ActIVIty Selector 39 Example Imagine you are given the following set of start and stop times Sort the activities by their finish times for activities 1 E39 ii v l D 2 Schedule the first actIVIty in this list E ii 3 Now go through the rest of the sorted list in order scheduling E ii El activities whose start time is after or the same as the last l lz39 scheduled activity ii ii ii El 3 39Ei note code for this algorithm is in section 161 ii 39 time Analysis Greedy Algorithm l Sorting the activitie by their fini h time 0 Let n be the total number of activities 0 The algorithm first sorts the activities by finish time taking On log n 0 Then the algorithm visits each activity egtltactly once doing a constant amount of work each time This takes On 0 Thus total time is Onlog n time Greedy Scheduling of Activities Optimality l l time o The big question here is Does the greedy algorithm give us an optimal solution 0 Surprisingly the answer turns out to be yes 0 We can prove this is true by contradiction l 39 Proof of Optimality Let A be the set of activities selected by the greedy algorithm Consider any non overlapping set of activities B We will show that lAl 2 lBl by showing that we can replace each activity in B with an activity in A This will show that A has at least as many activities as any other non overlapping schedule and thus that A is optimal Proof of Optimality Let am be the first activity in A that is different than an activity in B Then Aa17a2amam1 and B a17a27bmbm1 But since A was chosen by the greedy algorithm am must have a finish time which is earlier than the finish time of bag Thus B a1a2ambm1 is also a valid schedule 3 B a ban was gt Continuing this process we see that we can replace each activity in B with an activity in A QED 39 What l We wanted to show that the schedule A chosen by greedy was optimal c To do this we showed that the number of activities in A was at least as large as the number of activities in any other non overlapping set of activities 0 To show this we considered any arbitrary non overlapping set of activities B We showed that we could replace each activity in B with an activity in A Greedy pattern The problem has a solution that can be given some numerical value The best optimal solution has the highestlowest value The solutions can be broken down into steps The steps have some order and at each step there is a choice that makes up the solution 0 The choice is based on what s best at a given moment Need a criterion that will distinguish one choice from another 0 Finally need to prove that the solution that you get by making these local choices is indeed optimal 39 ActIVIty Selection Pattern 39 0 1 Knapsack The problem 0 A thief robbing a store finds n items the i th item is worth vi dollars and weighs wi pounds where wi and vi are integers o The thief has a knapsack which can only hold W pounds for some integer W o The thief39s goal is to take as valuable a load as possible 0 Which values should the thief take 0 The value of the solution is the number of non overlapping activities The best solution has the highest number 0 The sorting gives the order to the activities Each step is examining the next activity in order and decide whether to include it o In each step the greedy algorithm chooses the activity which extends the length of the schedule as little as possible This is called the 0 1 knapsack problem because each item is either taken or not taken the thief can not take a fractional amount 39 Knapsack Problem 39 Fractional Knapsack o Tho e problem for which greedy algorithm can be u ed are a subset of those problems for which dynamic programming can be used 0 So it39s easy to mistakenly generate a dynamic program for a problem for which a greedy algorithm suffices Or to try to use a greedy algorithm when in fact dynamic programming is required The knapsack problem illustrates this difference 0 The 0 1 knapsack problem requires dynamic programming whereas for the fractional knapsack problem a greedy algo rithm suffices o In this variant of the problem the thief can take fractions of items rather than the whole item 0 An item in the 0 1 knapsack is like a gold ingot whereas an item in the fractional knapsack is like gold dust Greedy Failure on 0 1 Knapsack l I Say the knapsack holds weight 5 and there are three items Let item 1 have weight 1 and value 3 let item 2 have weight 2 and value 5 let item 3 have weight 3 and value 6 0 Then the value per pound of the items are 3522 respec tively We can solve the fractional knapsack problem with a greedy algorithm Compute the value per pound viwi for each item 239 sort the Items by value per pound I o The greedy algorithm will then choose item 1 and item 2 3 The thief then follows the greedy strategy of always taking for a total value of 8 as mUCh as DOSSibIe Of the item remaining WhiCh has higheSt 0 However the optimal solution is to choose items 2 and 3 for value per pound39 a total value of 11 2O 22 l 39 Analysis 39 Optimality of Greedy on Fractional o If there are n items this greedy algorithm takes Onlogn time G d t t39 I O lk kbt39t39 t39 I o We39ll show in the in class exercise that it returns the correct reel y 395 no Op 39ma 0 napsac u I Is op lma on soution fractional knapsack I c To show this we can use a proof by contradiction 0 Note however that the greedy algorithm does not work on the O 7 l knapsack 21 23 39 Proof Assume the objects are sorted in order of cost per pound Let vi be the value for item 1 and let wi be its weight 0 Let xi be the fraction of object 1 selected by greedy and let V be the total value obtained by greedy 0 Consider some arbitrary solution B and let be the fraction of object 1 taken in B and let V be the total value obtained by B c We want to show that V g V or that V7 V 2 O 39 Proof Let k be the smallest index with 0 lt l 0 Note thatforiltk acil and forigtk aciO 0 You will show that for all i v vk 90139 i 909 1 Z 90139 i 907 wi wk 77 vi i1 2m 7 x2 wi i1 Z in 90139 i 907 wi i1 k w w 77 vi Z 90139 i 907 wi wk i1 O 39 Proof I7 71 ViV Ecolvii Z yogiZ i1 i1 Z Z 2 39 Proof 1 2 3 4 5 6 0 Note that the last step follows because c is positive and because 77 ZOW QCQ wi i 1 Z 77 77 2 WM 2 MW i1 i1 W 7 W o 7 8 9 0 Where W is the total weight taken by greedy and W is the total weight for the strategy B c We know that W 2 W 39 In Class ExerCIse Consider the inequality v vk 90139 i 909 1 Z 90139 i 902 wi wk 0 Q1 Show this inequality is true for i lt k 0 Q2 Show it39s true for i k 0 Q3 Show it39s true for i gt k

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

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

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