tailieunhanh - Data Structures and Algorithm Analysis Edition 3.2 (Java Version) - Clifford A. Shaffer

Data Structures and Algorithm Analysis Edition (Java Version) a comprehensive treatment focusing on the creation of efficient data structures and algorithms, this text explains how to select or design the data structure best suited to specific problems. It uses Java as the programming language and is suitable for second-year data structure courses and computer science courses in algorithmic analysis. | Data Structures and Algorithm Analysis Edition (Java Version) Clifford A. Shaffer Department of Computer Science Virginia Tech Blacksburg, VA 24061 January 2, 2012 Update For a list of changes, see ˜shaffer/Book/ Copyright © 2009-2012 by Clifford A. Shaffer. This document is made freely available in PDF form for educational and other non-commercial use. You may make copies of this file and redistribute in electronic form without charge. You may extract portions of this document provided that the front page, including the title, author, and this notice are included. Any commercial use of this document requires the written consent of the author. The author can be reached at shaffer@. If you wish to have a printed version of this document, print copies are published by Dover Publications (see ). Further information about this text is available at ˜shaffer/Book/. Contents Preface xiii I 1 Preliminaries Data Structures and Algorithms A Philosophy of Data Structures The Need for Data Structures Costs and Benefits Abstract Data Types and Data Structures Design Patterns Flyweight Visitor Composite Strategy Problems, Algorithms, and Programs Further Reading Exercises Mathematical Preliminaries Sets and Relations Miscellaneous Notation Logarithms Summations and Recurrences Recursion Mathematical Proof Techniques 1 3 4 4 6 8 12 13 13 14 15 16 18 20 23 23 27 29 30 34 36 iii 2 iv Direct Proof Proof by Contradiction Proof by Mathematical Induction Estimation Further Reading Exercises Contents 3 37 37 38 44 45 46 53 53 59 60 63 63 65 66 67 68 69 74 75 77 78 80 83 84 85 89 Algorithm Analysis Introduction Best, Worst, and Average Cases A Faster Computer, or a Faster Algorithm? Asymptotic Analysis Upper Bounds Lower