Understanding Greedy Algorithms in Algorithmic Design
Greedy algorithms in algorithmic design involve making the best choice at each step to tackle large, complex problems by breaking them into smaller sub-problems. While they provide efficient solutions for some problems, they may not always work, especially in scenarios like navigating one-way streets or heavy traffic. By analyzing and designing greedy algorithms, one can identify rules for decision-making and understand when they may fail. Examples such as the Fractional Knapsack Problem and Interval Scheduling illustrate the application of greedy strategies in real-world scenarios.
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
Basic Algorithm Design Techniques Divide and conquer Dynamic Programming Greedy Common Theme: To solve a large, complicated problem, break it into many smaller sub-problems.
Greedy Algorithm If a problem requires to make a sequence of decisions, for the first decision, make the best choice given the current situation. (This automatically reduces the problem to a smaller sub-problem which requires making one fewer decisions)
Warm-up: Walking in Manhattan Walk in a direction that reduces distance to the destination.
Greedy does not always work Driving in New York: one-way streets, traffic
Design and Analysis Designing a Greedy Algorithm: 1. Break the problem into a sequence of decisions. 2. Identify a rule for the best option. Analyzing a Greedy Algorithm: Important! Often fails if you cannot find a proof. Technique: Proof by contradiction. Assume there is a better solution, show that it is actually not better than what the algorithm did.
Fractional Knapsack Problem There is a knapsack that can hold items of total weight at most W. There are now n items with weights w1,w2, , wn. Each item also has a value v1,v2, ,vn. The items are infinitely divisible: can put (or any fraction) of an item into the knapsack. Goal: Select fractions p1,p2, ,pn such that Capacity constraint: p1w1+p2w2+ +pnwn <= W Maximum Value: p1v1+p2v2+ +pnvn maximized.
Example Capacity W = 10, 3 items with (weight, value) = (6, 20), (5, 15), (4, 10) Solution: Item 1 + 0.8 Item 2. Weight = 10, Value = 32
Interval Scheduling There are n meeting requests, meeting i takes time (si, ti) Cannot schedule two meeting together if their intervals overlap. Goal: Schedule as many meetings as possible. Example: Meetings (1,3), (2, 4), (4, 5), (4, 6), (6, 8) Solution: 3 meetings ((1, 3), (4, 5), (6, 8))
