Book contents
- Frontmatter
- Dedication
- Content
- List of Figures
- List of Tables
- Preface
- Acknowledgments
- 1 Model and Analysis
- 2 Basics of Probability and Tail Inequalities
- 3 Warm-up Problems
- 4 Optimization I: Brute Force and Greedy Strategy
- 5 Optimization II: Dynamic Programming
- 6 Searching
- 7 Multidimensional Searching and Geometric Algorithms
- 8 String Matching and Finger Printing
- 9 Fast Fourier Transform and Applications
- 10 Graph Algorithms
- 11 Maximum Flow and Applications
- 12 NP Completeness and Approximation Algorithms
- 13 Dimensionality Reduction*
- 14 Parallel Algorithms
- 15 Memory Hierarchy and Caching
- 16 Streaming Data Model
- Appendix A Recurrences and Generating Functions
- Bibliography
- Index
Preface
Published online by Cambridge University Press: 27 April 2019
- Frontmatter
- Dedication
- Content
- List of Figures
- List of Tables
- Preface
- Acknowledgments
- 1 Model and Analysis
- 2 Basics of Probability and Tail Inequalities
- 3 Warm-up Problems
- 4 Optimization I: Brute Force and Greedy Strategy
- 5 Optimization II: Dynamic Programming
- 6 Searching
- 7 Multidimensional Searching and Geometric Algorithms
- 8 String Matching and Finger Printing
- 9 Fast Fourier Transform and Applications
- 10 Graph Algorithms
- 11 Maximum Flow and Applications
- 12 NP Completeness and Approximation Algorithms
- 13 Dimensionality Reduction*
- 14 Parallel Algorithms
- 15 Memory Hierarchy and Caching
- 16 Streaming Data Model
- Appendix A Recurrences and Generating Functions
- Bibliography
- Index
Summary
This book embodies a distillation of topics that we, as educators, have frequently covered in the past two decades in various postgraduate and undergraduate courses related to Design and Analysis of Algorithms in IIT Delhi. The primary audience were the junior level (3rd year) computer science (CS) students and the first semester computer science post-graduate students. This book can also serve the purpose of material for a more advanced level algorithm course where the reader is exposed to alternate and more contemporary computational frameworks that are becoming common and more suitable.
A quick glance through the contents will reveal that about half of the topics are covered by many standard textbooks on algorithms like those by Aho et al. [7], Horowitz et al. [65], Cormen et al. [37], and more recent ones like those by Kleinberg and Tardos [81] and Dasgupta et al. [40]. The first classic textbook in this area, viz., that by Aho et al., introduces the subject with the observation ‘The study of algorithms is at the very heart of computer science’ and this observation has been reinforced over the past five decades of rapid development of computer science as well as of the more applied field of information technology. Because of its foundational nature, many of the early algorithms discovered about five decades ago continue to be included in every textbook written including this one – for example, algorithms like FFT, quicksort, Dijkstra's shortest paths, etc.
What motivated us to write another book on algorithms are the several important and subtle changes in the understanding of many computational paradigms and the relative importance of techniques emerging out of some spectacular discoveries and changing technologies. As teachers and mentors, it is our responsibility to inculcate the right focus in the younger generation so that they continue to enjoy this intellectually critical activity and contribute to the enhancement of the field of study. As more and more human activities are becoming computer-assisted, it becomes obligatory to emphasize and reinforce the importance of efficient and faster algorithms, which is the core of any automated process. We are often limited and endangered by the instictive use of ill-designed and brute force algorithms, which are often erroneous, leading to fallacious scientific conclusions or incorrect policy decisions.
- Type
- Chapter
- Information
- Design and Analysis of AlgorithmsA Contemporary Perspective, pp. xxi - xxivPublisher: Cambridge University PressPrint publication year: 2019