Methods in Algorithmic Analysis

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.

Autorentext
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.

Inhalt
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

#	Onlineshop	Preis CHF	Versand CHF	Total CHF
1	Seller	0.00	0.00	0.00