Analysis and Design of Algorithms provides a structured view of algorithm design techniques in a concise, easy-to-read manner. The book begins with a clear explanation of the basics: what algorithms are, their practical applications, asymptotic notation, and data structures. The second section covers the algorithmic design techniques of divide and conquer, greedy, dynamic programming, branch and bound, and graph traversal. For each of these techniques, the book presents templates and guidelines on when to use and not to use each technique. The third major section of the book covers NP-completeness and the inherent hardness of problems. Using the material provided in this book, students and professionals can master the processes to use in solving the most difficult algorithmic problems. Users can explore various techniques, and learn to decide which algorithm design technique to use for a given problem. Many sections contain innovative mnemonics to aid the readers in remembering the templates and key takeaways.
Author(s): Amrinder Arora
Edition: 2nd
Publisher: Cognella Academic Publishing
Year: 2015
Language: English
Pages: 146
Tags: Algorithms: Analysis And Design
Table of Contents......Page 4
Table of Figures......Page 10
Acknowledgements......Page 12
Preface......Page 13
Section I: The Basics......Page 16
Chapter 1: Introduction and Bare Essentials......Page 17
Chapter 2: Asymptotic Analysis and Notation......Page 23
Chapter 3: Data Structures......Page 29
Section II: Algorithm Design Techniques......Page 38
Chapter 4: Divide and Conquer......Page 39
Chapter 5: Greedy Method......Page 56
Chapter 6: Dynamic Programming......Page 68
Chapter 7: Graph Traversal Techniques......Page 84
Chapter 8: Branch and Bound......Page 94
Section III: Intrinsic Hardness of Problems......Page 99
Chapter 9: NP Completeness......Page 100
Chapter 10: Slaying the NP-Hardness Dragon......Page 113
Chapter 11: Theory of Lower Bounds......Page 119
Section IV: Conclusions and Auxiliary Materials......Page 127
Chapter 12: Wrapping Up......Page 128
Appendix A: How Do We Learn?......Page 131
Appendix B: More Graphs Theory Areas......Page 133
Appendix C: Minimum Spanning Tree......Page 135
Appendix D: Time Complexity of Union Find Data Structure......Page 137
Appendix E: Facility Location Problem......Page 139
Appendix F: String Matching......Page 141
Index......Page 143
Works Cited......Page 145
