Week 4 Notes
Week 4 Notes CMPS 102
Popular in Algorithm Analysis
Popular in ComputerScienence
This 3 page Class Notes was uploaded by Shanee Dinay on Monday February 8, 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 17 views. For similar materials see Algorithm Analysis in ComputerScienence at University of California - Santa Cruz.
Reviews for Week 4 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/08/16
Day 7 1/26/2016 CMPS 102 Chapter 4 Greedy Algorithms Extra Credit For counterexamples: bad choices counter example, there is something that is a moral choice that does not fit in our framework Not hurting someone will hurt someone more? Benefit of 1 is your love for your grandma, benefit C is the losses of the other families You are emotionally removed from the situation come up with something claim: you can pass moral judgements of interest… C is as perceived by the other person you can estimate C, but the other person knows what C is the other person will suffer C you can to choose between you getting one and them getting C, and C value is getting the other value driving drunk, you get home safe you get a 1 the other side you run over someone and that is C crossing a red light: dont get caught, get caught get a ticket, run over someone go to jail one way you kill someone, one way you get a big fine 4.1 Interval Scheduling Interval Scheduling Jobs j starts at sjand finishes at fj two jobs compatible if they don’t overlap Goal: find maximum subset of mutually compatible jobs Greedy Template consider jobs in some order. Take each job provided it’s compatible with the ones already taken [earliest start time] consider jobs in ascending order of start time s j [earliest finish time] consider jobs in ascending order of finish time f j [shortest interval] consider jobs in ascending order of interval length f s j j [fewest conflicts] for each job, count the number of conflicting jobs c,j . edule in ascending order of conflicts c j ONE of these four rule actually works: increasing order of finish time Greedy Algorithm consider hobs in increasing order of finish time. Take each jobs provided it’s compatible with the ones already take Theorem. Greedy algorithm is optimal Proof (by contradiction) assume greedy is not optimal, and let’s see what happens Let i1 2 …,ikdenote set of jobs selected by greedy Let ji 2… jm denote set of jobs in the optimal solution with i 1 1 2= j2 …, ir jrfor the largest possible value of r 4.2 Interval Partitioning Interval Partitioning lecture j starts at sjnd finishes at fj goal: find minimum number of classrooms to schedule all lectures so that no two occur at the same time in the same room Ex. This lecture uses 4 classrooms to schedule 10 lectures What is the algorithm that will solve the lower bound problem where the lower bound is 3 Fill in the classrooms by the earliest time slot Observation. Greedy algorithm never schedules two incompatible lecture in the same classroom Theorem. Greedy algorithm is optimal Proof let d number of classrooms that the greedy algorithm allocates classroom d is opened because we needed to schedule a job, say j, that is incompatible with all d1 other classrooms since we sorted by start time, all these incompatibilities are caused by lectures that start no later than s j thus, we have d lectures overlapping at time s j+ ε key observation → all schedules use ≥ d classrooms Day 8 1/28/2016 CMPS 102 Greedy Algorithms Interval Partitioning Class Scheduling CounterExample There does not exist a single algorithm that always returns the correct answer, and always returns fast Onion try to find the decision that you can postpone e ≤ 3v 6 5 ≤ 3•2 If a graph is planar it contains one vertex of degree of at least 5 or less n = # of vertices ∑deg(v) = 2e v 2e ≤ 6n 12 divide by n ∑ vdeg(v) 12 n = 6 − n Euler’s identity if graph is planar then the number of edges you can draw is limited 4.2 Scheduling to Minimize Lateness
Are you sure you want to buy this material for
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'