### Create a StudySoup account

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

Already have a StudySoup account? Login here

# DATA STRUCT ALG II CMPSC 130B

UCSB

GPA 3.96

### View Full Document

## 59

## 0

## Popular in Course

## Popular in ComputerScienence

This 4 page Class Notes was uploaded by Ted Robel Sr. on Thursday October 22, 2015. The Class Notes belongs to CMPSC 130B at University of California Santa Barbara taught by T. Gonzalez in Fall. Since its upload, it has received 59 views. For similar materials see /class/227008/cmpsc-130b-university-of-california-santa-barbara in ComputerScienence at University of California Santa Barbara.

## Similar to CMPSC 130B at UCSB

## Reviews for DATA STRUCT ALG 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: 10/22/15

CS 130B UCSB Optimization Problem Given an Optimization Function and a set of constraints nd an optimal solution Optimal Solution A feasible solution for which the optimization function has the best possible value Feasible Solution Solution that satis es the constraints Example Printer problem The constraint is to print all the jobs nonpreemptively one at a time and the objective is to minimize the average nish time Container Loading problem The constraint is that the container loaded have total weight g the cargo weight capacity and the objective function is to nd a larget set of containers to load TC 2004 CS 130B lVrl Coin Changing Give change using the least number of coins Greedy Method Chapter 101 Attempt to construct an optimal solution in stages At each stage we make a decision that appears to be the best under some criterion at the time local optimum A decision made in one stage is not changed in a later stage so each decision should assure feasibility Greedy criterion criterion used to make the greedy decision at each stage UCSB TC 2004 CS 130B UCSB Large ship is to be loaded with cargo Cargo is in equal size containers Container 239 has weight mi The cargo weight capacity is c and every wi g 6 Load the ship with maximum number of containers without exceeding the cargo weight capacity Find values I 6 01 such that 2211 wi m g c and the optimization function 21 is maximized TC 2004 CS 130B IVVB wl 1112 w3 w4 w5 w6 1117 1113 c 100 200 50 90 150 50 20 80 400 l l l 0 0 l 0 0 400 ls it an optimal solution No Why One can take out object 2 and add objects 7 and 8 That would be a better solution ls a feasible solution optimal if one cannot trade two objects for one in the solution while maintaining feasibility Answer See the following nonoptimal solution wl 1112 w3 w4 w5 w6 1117 c UCSB TC 2004 CS 130B Load ship in stages one container per stage At each stage we need to decide which container to load Greedy criterion From the remaining containers select the one with least weight 150 200 400 CS 130B Correctness Proof Theorem The above greedy algorithm generates an optimal set of containers to load 0 Proof ldea No matter which feasible solution Y you start with it is possible to transform it to the solution generatated by the algorithm without decreasing the objective function value Assume without loss of generality wlog wi SWZS mSwn Let X 1112 In be the solution generated by the algorithm Let Y y1y2 yn be any feasible 1 1 1 1 1 1 0 0 390 solution such that Z wiyz g c Transform Y to X in several steps without decreasing the objective function value UCSB TC 2004 UCSB TC 2004 CS 130B IVVS CS 130B Ivrv UCSB From the way the algorithm works there is a k 6 071 st 1 1 for 139 g k and z 0 for 139 gt 11 ie X l l M l 00 0 Transformation Let j be the smallest integer in 171 st 1139 7 yj So either 1 No such j exists in which case Y X 2 j g k as otherwise Y is not feasible So zj 1 and yj 0 Change yj to 1 If Y is infeasible then there is an 1 in j 171 st y 1 y is changed to 0 and the new Y is feasible because wj g ml No matter what the new Y is it has at least as many 1s or more as before Apply the transformation until you get Y X TC 2004 Example for Proof Solution Generated by our algorithm wl 112 w3 w4 w5 w6 7117 1113 c 20 50 50 80 90 100 150 200 400 1 1 1 1 1 1 0 0 390 Consider the following feasible solution Y wl 112 w3 w4 w5 w6 7117 1113 c 20 50 50 80 90 100 150 200 400 0 1 0 0 0 0 1 1 400 Transformations as in the proof of the previous theorem j in the proof is 1 then 3 4 5 6 UCSB TC 2004 CS 130B 1V3 w1 112 w3 w4 w5 w6 1117 1113 c 20 50 50 80 90 100 150 200 400 1 1 0 0 0 0 0 1 270 1 1 1 0 0 0 0 1 320 1 1 1 1 0 0 0 1 400 1 1 1 1 1 0 0 0 290 1 1 1 1 1 1 0 0 390 Implementation Remaining objects are stored in a heap ordered with respect to their weight smallest on top of the heap Algorithm talks 071 logn time n deletes from a heap with initially 71 objects creating the heap takes 071 time CMPSC 130A Alg takes 071 time if optimal sol has very CS 130B IVVQ Linear Time Implementation 1139 0 Assume all weights are different if there are repeated weights then a similar algorithm exists for the solution of the problem 0 We use an algorithm which we will describe when we cover diVide andconquer algorithms that nds the middle object of 71 objects ie nd the element such that there are exactly objects smaller or equal to it in On time few nlog 71 objects UCSB TC 2004 UCSB TC 2004 CS 130B 1V710 CS 130B IVrll UCSB Our algorithm works by doing a binary Search type of search on the unsorted weights Let S be the smallest objects in W and let it be their total weight There are three cases 1 If t gt c then search for a solution in S only with the same capacity c 2 If t c then add all the objects in S to the solution and end the procedure 3 Else add all the elements in S to the solution and set the the remaining capacity to c it and now try to add as many objects as possible from W 7 S Repeat the above step until there are no objects left Time complexity is cln 61712 61714 czn TC 2004 0 Suppose that W is 610815221959 and c 25 The middle object is 9 S 6859 and t 28 The objects in S do not t 0 The new W is 6895 and c 25 The middle object is 6 S 65 and t 11 The objects in S t and are added to the solution 0 The new W is 89 and c 14 The middle object is 8 S 8 and t 8 The object in S t and are added to the solution 0 The ne W is 9 and c 6 The middle object is 9 S 9 and t 9 The object in S does not t 0 There are no objects left and we are done The solution are the objects with weight 5 6 and 8 UCSB TC 2004 CS 130B lVrl2 Example 2 0 Suppose W is 610815221959 and c 53 The middle object is 9 S 6859 and t 28 The objects in S t and are added to the solution 0 The new W is 10152219 and c 25 The middle object is 15 S 1015 and t 25 The objects in S t exactly and the algorithm nishes o The solution are the objects with weight 6 8 5 9 10 and 15 UCSB TC 2004 CS 130B Deterministic Scheduling Printer Scheduling with Complete Information 0 Problem is identical to the one in Section 1011 0 At time zero there are 71 tasks to be printed o Tasks are denoted by T1 T2 Tn with execution time requirements t1t2 tL 0 Once a task starts printing it will continue are not allowed UCSB T printing until it terminates 1e preemptions 1V713 G 2004 CS 130B lVrl4 Example t1 2t2 1t3 4t4 9 Two schedules 2 n H n n H a Let be the nish time for task T in S The Average Finish Time AFT for S is The AFT for S1 is 54 61 975 and the AFT for 32 is Ui i l l S 800 Objective Function Find a schedule with minimum AFT a 4 5 a O l 5 7 IE Shortest Processing Time First SPT Assign the tasks to the printer from smallest to largest UCSB TC 2004 CS 130B 1V715 SPT is Optimal Proof By contradiction is an optimal schedule wrt AFT ie mltmwm n 71 Since S is not an SPT schedule there exist two tasks Ti Tj such that they are scheduled one after the other in S rst Ti and then such that t gt tj UCSB Theorem SPT schedules are optimal wrt AFT Suppose that there is a problem instance I such that schedule S which is not an SPT schedule TC 2004

### 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 used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

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

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