Greedy Algorithms Practice Problems
Explore a series of challenging greedy algorithm practice problems, including maximizing quantity values, finding unit-length intervals, and scheduling events for maximum reward.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CS 330 Discussion 3 Spring 2017
Greedy Algorithms Practice 1 You re given two lists of numbers of size ?, X = {?1,?2 ??} and Y = {?1,?2 ??}. Find the matching of values ?:X Y such that the quantity ?1? ?1 + ?2?(?2) + ???(??) is maximized. Prove this matching is optimal.
Greedy Algorithms Practice 2 Given an ordered set of real numbers S = ?1,?2,?3 ??, find the smallest set of unit-length intervals whose union contains ?. That is, your goal is to come up with the smallest list of values {?1,?2 ??} such that for any ??, there is some ? such that ?? [??,??+ 1]. Write an algorithm which does this and show its correctness.
Greedy Algorithms Practice 3 You re given a list of ? events with associated positive rewards ?1to ??. Each takes 1 unit of time. Event ? has a latest start time ??. Your goal is to schedule a subset of these events such that: If event ? is scheduled, it starts at a time in [0,??] No two events can overlap (so, if you schedule one event to start at time ?, no other event can start at times in [?,? + 1)) The total reward of the scheduled events is maximized Write an algorithm which does this, and show its correctness.
Greedy Algorithms Practice 4 Consider the interval coloring problem discussed in lecture. Consider the following greedy algorithm: use the greedy algorithm for one room to determine what events to assign to the first color. From the remaining events, repeat this process to determine what events to assign to the second color. Repeat until all events are colored. Give a counter-example where this algorithm does not produce an optimal coloring.
