TAILIEUCHUNG - Lecture Data structures and algorithms in Java (6th edition): Chapter 12.2 - Goodrich, Tamassia, Goldwasser

This chapter provides knowledge of greedy. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Greedy Method 3/29/14 21:21 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 The Greedy Method and Text Compression © 2014 Goodrich, Tamassia, Goldwasser Greedy Method 1 The Greedy Method Technique ! The greedy method is a general algorithm design paradigm, built on the following elements: n   n   configurations: different choices, collections, or values to find objective function: a score assigned to configurations, which we want to either maximize or minimize ! It works best when applied to problems with the greedy-choice property: n   a globally-optimal solution can always be found by a series of local improvements from a starting configuration. © 2014 Goodrich, Tamassia, Goldwasser Greedy Method 2 1 Greedy Method 3/29/14 21:21 Text Compression ! Given a string X, efficiently encode X into a smaller string Y n   Saves memory and/or bandwidth ! A good approach: Huffman encoding n   n   n   n   Compute frequency f(c) for each character c. Encode high-frequency characters with short code words No code word is a prefix for another code Use an optimal encoding tree to determine the code words © 2014 Goodrich, Tamassia, Goldwasser Greedy Method 3 Encoding Tree Example ! A code is a mapping of each character of an alphabet to a binary code-word ! A prefix code is a binary code such that no code-word is the ! prefix of another code-word An encoding tree represents a prefix code n   n   Each external node stores a character The code word of a character is given by the path from the root to the external node storing the character (0 for a left child and 1 for a right child) 00 010 011 10 11 a b c d e © 2014 Goodrich, Tamassia, Goldwasser Greedy Method a d b c e 4 2 Greedy Method 3/29/14 21:21 Encoding Tree Optimization ! Given a text string X, we want to find a prefix code for the characters of X that yields a .

• Cơ sở dữ liệu
• Data structures
• Data structures and algorithms
• Computer science
• Design of data structures
• Algorithms in Java
• Ebook Data structures and algorithms made easy
• Data structures and algorithms made easy
• Data structures and algorithmic puzzles
• Data structures for storing strings
• Algorithms design techniques
• algorithms
• data structure lectures
• structured document data
• teaching data structures
• algorithms in data structures
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Programming assignments
• Data structures organize data
• Resource constraints
• Lecture Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Lecture ECE 250
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming