Dipartimento di Sistemi e Informatica, Firenze (Italy), 2006. - 100 pages.Introduction
What is the Analysis of an Algorithm
The Analysis of Sequential Searching
Binary Searching
Closed Forms
The Landau notation
Special numbers
Mappings and powers
Permutations
The group structure
Counting permutations
Dispositions and Combinations
The Pascal triangle
Harmonic numbers
Fibonacci numbers
Walks, trees and Catalan numbers
Stirling numbers of the first kind
Stirling numbers of the second kind
Bell and Bernoulli numbers
Formal power series
Definitions for formal power series
The basic algebraic structure
Formal Laurent Series
Operations on formal power series
Composition
Coefficient extraction
Matrix representation
Lagrange inversion theorem
Some examples of the LIF
Formal power series and the computer
The internal representation of expressions
Basic operations of formal power series
Logarithm and exponential
Generating Functions
General Rules
Some Theorems on Generating Functions
More advanced results
Common Generating Functions
The Method of Shifting
Diagonalization
Some special generating functions
Linear recurrences with constant coefficients
Linear recurrences with polynomial coefficients
The summing factor method
The internal path length of binary trees
Height balanced binary trees
Some special recurrences
Riordan Arrays
Definitions and basic concepts
The algebraic structure of Riordan arrays
The A-sequence for proper Riordan arrays
Simple binomial coefficients
Other Riordan arrays from binomial coefficients
Binomial coefficients and the LIF
Coloured walks
Stirling numbers and Riordan arrays
Identities involving the Stirling numbers
Formal methods
Formal languages
Context-free languages
Formal languages and programming languages
The symbolic method
The bivariate case
The Shift Operator
The Difference Operator
Shift and Difference Operators - Example I
Shift and Difference Operators - Example II
The Addition Operator
Definite and Indefinite summation
Definite Summation
The Euler-McLaurin Summation Formula
Applications of the Euler-McLaurin Formula
Asymptotics
The convergence of power series
The method of Darboux
Singularities: poles
Poles and asymptotics
Algebraic and logarithmic singularities
Subtracted singularities
The asymptotic behavior of a trinomial square root
Hayman’s method
Examples of Hayman’s Theorem
Bibliography
