tailieunhanh - Data Structures and Algorithm Analysis in C++, Third Edition

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 C++ 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 C Version Clifford A. Shaffer Department of Computer Science Virginia Tech Blacksburg VA 24061 January 2 2012 Update For a list of changes see http 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 http 04 8 64 . Further information about this text is available at http shaffer Book . Contents Preface xiii I Preliminaries 1 1 Data Structures and Algorithms 3 A Philosophy of Data Structures 4 The Need for Data Structures 4 Costs and Benefits 6 Abstract Data Types and Data Structures 8 Design Patterns 12 Flyweight 13 Visitor 13 Composite 14 Strategy 15 Problems Algorithms and Programs 16 Further Reading 18 Exercises 20 2 Mathematical Preliminaries 25 Sets and Relations 25 Miscellaneous Notation 29 Logarithms 31 Summations and Recurrences 32 Recursion 36 Mathematical Proof Techniques 38 iii iv Contents Direct Proof 39 Proof by Contradiction 39 Proof by Mathematical Induction 40 Estimation 46 Further Reading 47 Exercises 48 3 Algorithm Analysis 55 Introduction 55 Best Worst and Average Cases 61 A Faster Computer or a Faster Algorithm 62 Asymptotic Analysis 65 Upper Bounds 65 Lower Bounds 67 0 Notation 68 Simplifying Rules 69 .