1st Edition

Methods in Algorithmic Analysis

By Vladimir A. Dobrushkin Copyright 2009
    826 Pages 54 B/W Illustrations
    by Chapman & Hall

    826 Pages 54 B/W Illustrations
    by Chapman & Hall

    826 Pages 54 B/W Illustrations
    by Chapman & Hall

    Explores the Impact of the Analysis of Algorithms on Many Areas within and beyond Computer Science
    A flexible, interactive teaching format enhanced by a large selection of examples and exercises

    Developed from the author’s own graduate-level course, Methods in Algorithmic Analysis presents numerous theories, techniques, and methods used for analyzing algorithms. It exposes students to mathematical techniques and methods that are practical and relevant to theoretical aspects of computer science.

    After introducing basic mathematical and combinatorial methods, the text focuses on various aspects of probability, including finite sets, random variables, distributions, Bayes’ theorem, and Chebyshev inequality. It explores the role of recurrences in computer science, numerical analysis, engineering, and discrete mathematics applications. The author then describes the powerful tool of generating functions, which is demonstrated in enumeration problems, such as probabilistic algorithms, compositions and partitions of integers, and shuffling. He also discusses the symbolic method, the principle of inclusion and exclusion, and its applications. The book goes on to show how strings can be manipulated and counted, how the finite state machine and Markov chains can help solve probabilistic and combinatorial problems, how to derive asymptotic results, and how convergence and singularities play leading roles in deducing asymptotic information from generating functions. The final chapter presents the definitions and properties of the mathematical infrastructure needed to accommodate generating functions.

    Accompanied by more than 1,000 examples and exercises, this comprehensive, classroom-tested text develops students’ understanding of the mathematical methodology behind the analysis of algorithms. It emphasizes the important relation between continuous (classical) mathematics and discrete mathematics, which is the basis of computer science.

    PRELIMINARIES

    Why Do We Analyze Algorithms?

    Proofs

    Iteration and Recursion

    COMBINATORICS

    Properties of Summation

    Multiple Sums

    Principles of Counting

    Permutations and Combinations

    Binomial Coefficients

    Binomial Coefficient and Hypergeometric Functions

    Stirling Approximation

    PROBABILITY

    Set Operations

    Sample Space and Random Variables

    Calculating Probabilities

    Random Variables

    Conditional Probabilities

    Independence

    Joint Distributions

    Dependent Random Variables

    MORE ABOUT PROBABILITY

    Special Distributions

    Types of Probabilistic Convergence

    The Theorem of Total Probability

    Bayes’ Theorem

    Convolution

    Order Statistics

    Chebyshev Inequality

    Sundry Examples

    RECURRENCES OR DIFFERENCE EQUATIONS

    How Do Difference Equations Arise?

    Properties of Difference Equations

    First Order Linear Difference Equations

    Divide-and-Conquer Recurrences

    Quicksort Recurrence

    Recurrences in Numerical Analysis

    Continued Fractions

    Partial Difference Equations

    Some Applications

    INTRODUCTION TO GENERATING FUNCTIONS

    Generating Functions—Definitions

    Extraction of Coefficients

    Counting Binary Trees

    Solving Recurrences

    Snake Oil Summation

    Applications in Probability

    The Langrage Inversion Theorem

    ENUMERATION WITH GENERATING FUNCTIONS

    Definition of Enumerators

    Sum and Product Rules

    Counting Compositions of Integers

    Further Set Operations

    Partition of Integers

    Exponential Enumerators

    FURTHER ENUMERATION METHODS

    Enumeration of Trees

    Occupancy Enumeration

    The Principle of Inclusion and Exclusion (PIE)

    Extensions and Further Applications of the PIE

    Probabilistic Inclusion-Exclusion Principle

    Runs in Permutations

    Special Topics

    COMBINATORICS OF STRINGS

    Operations on Languages

    Regular Languages

    Counting Regular Languages

    Waiting Time Probabilistic Problems

    Algorithms and Markov Chains

    INTRODUCTION TO ASYMPTOTICS

    Asymptotic Notation and Applications

    The Critical Range Method

    Rice’s Method

    The Euler Summation Formula

    Finding Primes

    Asymptotics from Recurrences

    Limit Laws in Probability

    ASYMPTOTICS AND GENERATING FUNCTIONS

    Elementary Bounds from Generating Functions

    Estimates from Singularities

    Estimates from Entire Functions

    Examples and Exercises

    REVIEW OF ANALYTIC TECHNIQUES

    Complex Numbers

    Review of Power Series

    Functions of a Complex Variable: Basic Concepts

    Differential Operators

    Partial Fraction Decomposition

    Some Special Functions

    Stieltjes Integrals

    APPENDICES

    BIBLIOGRAPHY

    ANSWERS/HINTS TO SELECTED PROBLEMS

    INDEX

    Biography

    Vladimir A. Dobrushkin is a professor in the Division of Applied Mathematics at Brown University and a professor in the Department of Computer Science at Worcester Polytechnic Institute.

    …helpful to any mathematics student who wishes to acquire a background in classical probability and analysis … This is a remarkably beautiful book that would be a pleasure for a student to read, or for a teacher to make into a year's course.

    —Harvey Cohn, Computing Reviews, May 2010