COMP3711: Design and Analysis of Algorithms
Tutorial 5: Sorting, Greedy
Integer Sorting
Copyright By PowCoder代写 加微信 powcoder
Solution (a)
Example below illustrates radix sorting 9 #s in [0,80]
Solution (b)
Decision Tree
Optimal Cent Change
Prove that the greedy algorithm for change making always uses the smallest number of possible coins if the coin set consists of quarters (25 cents) , dimes (10) , nickels (5), and pennies (1).
General denominations
Example: The coins are 1, 3, 9, 27, 81
This solution is optimal!
after which 38 cents remain after which 11 cents remain
after which 2 cents remain after which 2 cents remain
By the observation, to get an optimal solution for value n, we always need to try from the coin with the maximal value.
Greedy is optimal
Counter Example for Interval Partition
The goal of the interval partitioning problem (i.e., the classroom assignment problem) taught in lecture was to open as few classrooms as possible to accommodate all of the classes.
The greedy algorithm taught, sorted the classes by starting time. It then ran through the classes one at a time; at each step it first checked if there was an available empty classroom. Only if there was no such classroom would it open a new classroom.
The algorithm looks simple but the proof is actually very dependent upon the classrooms being sorted by starting time.
Prove that if the classes are sorted by finishing time the algorithm might not give a correct answer.
Note: Proving that something does not work usually means to find a counter-example.
Algorithm was modified to use finish time rather than starting time
The 4 intervals provide a counterexample.
The optimal solution is TWO but the greedy algorithm that sorts them by finishing time needs to use THREE classrooms.
12:30 1 1:30 Time
Note that if the intervals were sorted by starting time, the algorithm WOULD use only two classrooms.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com