An Introduction to the Analysis of Algorithms

Ed 1: October 2009, 152 pages
Ed 2: May 2012,
215 pages
Ed 3: 2018,
328 pages
Ed 4: In progress

Details

Resources

A note on the 2018 Third Edition

A successor to the first and second editions, this updated and revised book is a leading companion guide for students and engineers alike, specifically software engineers who design reliable code. While succinct, this edition is mathematically rigorous, covering the foundations for both computer scientists and mathematicians with interest in algorithms.

The exposition contains traditional algorithms such as Greedy, Dynamic Programming, and Divide & Conquer. The initial chapter contains a detailed introduction to proofs of correctness, based on pre and post-conditions, and loop invariants, as well as a section on Ranking Algorithms, including the Stable Marriage, Page Rank, and Pairwise Comparisons algorithms.

The book also explores two classes of algorithms that are often overlooked in introductory textbooks: Randomized and Online algorithms. The coverage of both fields is timely: Randomized algorithms have become ubiquitous due to the emergence of cryptography (covered in the book), while Online algorithms are essential in numerous fields as diverse as operating systems and stock market predictions.

The 3rd edition has two new chapters: Chapter 7 on algorithms in Linear Algebra, from the point of view of parallelism, and Chapter 8 on the Foundations of Computation, from the point of view of operations on strings (Finite Automata, Context Free Grammars, and Turing machines).

Finally, the mathematical background material to the book has been placed in Chapter 9. This chapter contains material on induction, number theory, relations and logic.

There are many more exercises, practically all of them have solutions in the textbook. All the programming exercises have solutions on GitHub, and slides have been prepared for the instructor.