Transcription of Design and Analysis of Algorithms - GitHub Pages
{{id}} {{{paragraph}}}
Example: tourism industry
Design and Analysis of Algorithms - GitHub Pages
Design and Analysis of AlgorithmsGreedy Algorithms1 Introduction of Greedy Algorithm2 Interval Scheduling3 Optimal Loading4 Scheduling to Minimizing Lateness5 Fractional Knapsack Problem6 Greedy Algorithm Does Not Work (not teach in class)1 / 58 Outline1 Introduction of Greedy Algorithm2 Interval Scheduling3 Optimal Loading4 Scheduling to Minimizing Lateness5 Fractional Knapsack Problem6 Greedy Algorithm Does Not Work (not teach in class)2 / 58 MotivationA game like chess can be won only bythinking aheada player who is foucsed entirely on immediate advanatges iseasy to in many other games, such as Scrabbleit s fine to make whichever move seems best at the momentand not worrying too much about future sort of myopic behavior is easy and convinient, making it anattractive algorithmic strategy3 / 58 MotivationA game like chess can be won only bythinking aheada player who is foucsed entirely on immediate advanatges iseasy to in many other games, such as Scrabbleit s fine to make whichever move seems best at the momentand not worrying too much about future sort of myopic behavior is easy and convinient, making it anattractive algorithmic strategy3 / 58 Greedy AlgorithmGreedy algorithm works: proof of correctnessInterval scheduling: induction on stepOptimal loading: induction on input sizeScheduling to minimum lateness: exchange argumentGreedy algorithm does not work.
The sort of myopic behavior is easy and convinient, making it an attractive algorithmic strategy 3/58. Motivation A game like chess can be won only by thinking ahead a player who is foucsed entirely on immediate advanatges is easy to defeat. But in many other games, such as Scrabble
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: