Analysis of Algorithms

We begin by considering historical context and motivation for the scientific study of algorithm performance. Then we consider a classic example that illustrates the key ingredients of the process: the analysis of Quicksort.

We begin this lecture with an overview of recurrence relations, which provides us with a direct mathematical model for the analysis of algorithms.

Since the 17th century, scientists have been using generating functions to solve recurrences, so we continue with an overview of generating functions, emphasizing their utility in solving problems like counting the number of binary trees with N nodes.

Exact answers are often cumbersome, so we next consider a scientific approach to developing approximate answers that, again, mathematicians and scientists have used for centuries.

With a basic knowledge of recurrences, generating functions, and asymptotics, you are ready to learn and appreciate the basic features of analytic combinatorics, a systematic approach that avoids much of the detail of the classical methods.

The quintessential recursive structure, trees of various sorts are ubiquitous in scientific enquiry, and they arise explicitly in countless computing applications.

The study of sorting algorithms is the study of properties of permutations. We introduce analytic-combinatoric approaches to studying permutations in the context of this relationship.

From DNA sequences to web indices, strings (sequences of characters) are ubiquitous in modern computing applications, so we use analytic combinatorics to study their basic properties.

We view strings as sets of characters or as functions from [1..N] to [1..M] to study classical occupancy problems.