CS341 Lecture Notes - Greedy Algorithm, Gordon Gekko, Huffman Coding
16 Oct 2011
School
Department
Course
Professor
Document Summary
Greed cuts through, clarifies, and captures the essence of the evolutionary spirit. Greedy algorithms: simple idea, but it doesn"t always work. Used to solve optimization problems that involve choosing objects, events, (some type of entities) from a set: the greedy strategy: At each step, make the best next choice. Never look ahead to see if this choice has negative consequences: depending on the problem: this may or may not give the correct answer, the text treats greedy algorithms as a special case of dynamic programming. Properties of greedy algorithms: usually simple and fast (often linear time), hard part is demonstrating optimality, examples: huffman encoding, some sorting algorithms, typically applied to optimization problems (find solution which maximizes or minimizes some objective function). Suppose we are given the specification of a monetary denominational system: (a list of the values of different coins that are in use, for example: 1, 5, 10, 25, 100, 200 cents).
