The Analysis of Algorithsm

by Purdom, Jr., Paul; Brown, Cynthia

• ISBN13: 9780195174793
• ISBN10: 0195174798
• Format: Paperback
• Copyright: 2004-07-01
• Publisher: Oxford University Press

Summary

This text teaches the techniques needed to analyze algorithms. Organized by analysis techniques, The Analysis of Algorithms includes a systematic and largely self-contained treatment of the mathematics needed for elementary and intermediate analyses, as well as brief guides to the sources for more advanced techniques. Each technique is illustrated by being applied to the analysis of a realistic algorith. The authors provide explicit guidance on the use of various methods--for example, the discussion of mathematical induction emphasizes the process of finding the induction hypothesis, and the chapter on formulas for simplifying summations includes a section on deciding which formulas to apply. Many of the exercises give the student an opportunity to apply the techniques in developing original algorithm analyses.

Table of Contents

Preface

Introduction

Summing Series

Products and Binomials

Asymptotic Approximation

Simple Linear Recurrences

General Linear Recurrences

Full-History and Nonlinear Recurrences

Multidimensional Recurrences

Global Techniques

Lower Bounds and NP Completeness

Statistics

Appendix

References

Math Index

Algorithm Index

Index

Table of Contents provided by Publisher. All Rights Reserved.