Practical analysis of algorithms (Q461086)

The book is dedicated to an old, important and complex topic in computer science. The novelty of the book is that its approach is based on numerous examples combined with the classical theory based on theorems and proofs. The books starts with mathematically simple preliminaries like logarithms, sums, factorials or integer division. Then the fundamental notations in the analysis of algorithms are introduced, and later on recurrence relations. Deterministic analysis of algorithms is done in relationship with loops, binary trees, priority queues, binary heaps, merge sorts, quicksort, pattern matching. Another chapter is dedicated to algorithms that use randomized procedures, like simulating random events or selecting a random sample from a population; for those algorithms the expected value theorems are presented and discussed. Particularly interesting for programmers are the applications of expected value theorems and conditional expected value to the analysis of algorithms. Finally, finite graph algorithms are the subject of algorithm analysis. The multiple exercises in each section invite the readers to a deeper exploration of the subjects. The formalized style of the book is expected to attract especially young students introduced already to mathematical formalisms. The material can be used as a textbook for undergraduate courses in computer science.