CISC 365 Lecture Notes - Lecture 10: Huffman Coding, Bit Array, Binary Tree
21 Nov 2016
School
Department
Course
Professor
Document Summary
We have a set of activities to choose from, but some of them overlap. We want to choose the largest possible set of non-overlapping activities. A greedy algorithm always starts by sorting the objects. In class we experimented with di erent criteria for sorting: sort the activities by start time. This algorithm fails on this example: sort the activities by length, shortest rst. Finish time 9:02 8:59 9:05: sort the activities by length, longest rst. None of these work but undaunted by our repeated failures, we nally hit upon another alternative: sort the activities by nish time, earliest rst. Then repeatedly choose the next activity that doesn"t overlap with the ones already chosen. Clearly the algorithm will choose the only activity, thus nding the optimal solution. Assume the algorithm always nds the optimal solution when there are <= n activities, where n is some integer >= 0. Apply the algorithm (sort by nish time, and select as above).
