## Free E-Book : An Introduction to the Analysis of Algorithms [Read Online]

An Introduction to the Analysis of Algorithms

The textbook An Introduction to the Analysis of Algorithms (2nd edition) by [ Robert Sedgewick and Philippe Flajolet  ] overviews the primary techniques used in the mathematical analysis of algorithms. The material covered draws from classical mathematical topics, including discrete mathematics, elementary real analysis, and combinatorics, as well as from classical computer science topics, including algorithms and data structures.

Chapter 1: Analysis of Algorithms considers the general motivations for algorithmic analysis and relationships among various approaches to studying performance characteristics of algorithms.

Chapter 2: Recurrence Relations concentrates on fundamental mathematical properties of various types of recurrence relations which arise frequently when analyzing an algorithm through a direct mapping from a recursive representation of a program to a recursive representation of a function describing its properties.

Chapter 3: Generating Functions introduces a central concept in the average-case analysis of algorithms: generating functions — a necessary and natural link between the algorithms that are our objects of study and analytic methods that are necessary to discover their properties.

Chapter 4: Asymptotic Approximations examines methods of deriving approximate solutions to problems or of approximating exact solutions, which allow us to develop concise and precise estimates of quantities of interest when analyzing algorithms.

Chapter 5: Analytic Combinatorics introduces a modern approach to the study of combinatorial structures, where generating functions are the central object of study. This approach is the basis for the study of specific structures through the rest of the book.

Chapter 6: Trees investigates properties of many different types of trees, fundamental structures that arise implicitly and explicitly in many practical algorithms. Our goal is to provide access to results from an extensive literature on the combinatorial analysis of trees, while at the same time providing the groundwork for a host of algorithmic applications.

Chapter 7: Permutations surveys combinatorial properties of permutations (orderings of the numbers 1 through N) and shows how they relate in a natural way to fundamental and widely-used sorting algorithms.

Chapter 8: String and Tries studies basic combinatorial properties of strings, sequences of characters or letters drawn from a fixed alphabet, and introduces algorithms that process strings ranging from fundamental methods at the heart of the theory of computation to practical text-processing methods with a host of important applications.

Chapter 9: Words and Maps covers global properties of words (N-letter strings from an M-letter alphabet), which are well-studied in classical combinatorics (because they model sequences of independent Bernoulli trials) and in classical applied algorithmics (because they model input sequences for hashing algorithms). The chapter also covers random maps (N-letter words from an N-letter alphabet) and discusses relationships with trees and permutations.

Click on this link to read this book : An Introduction to the Analysis of Algorithms