An Introduction to the Analysis of Algorithms

algorithms-2edMichael Soltys

First Edition: October 2009, 152 pages
ISBN: 978-981-4271-40-0

Second Edition: May 2012, 215 pages
ISBN: 978-981-4401-15-9
[Sample: Chapter 1]

World Scientific: [1st ed][2nd ed]
Amazon: [1st ed][2nd ed]

GitHub repository with Python solutions

A note on the forthcoming 2017 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.

Besides expositions on traditional algorithms such as Greedy, Dynamic Programming and Divide & Conquer, the book explores two classes of algorithms that are often overlooked in introductory textbooks: Randomised and Online algorithms — with emphasis placed on the algorithm itself.

The coverage of both fields is timely: Randomised algorithms have become ubiquitous due to the emergence of cryptography, while Online algorithms are essential in numerous fields as diverse as operating systems and stock market predictions.

A new chapter on String Algorithms has been added, as this exciting field is growing due to numerous applications, such as biocomputing and its exploration of genetic codes, pattern matching in general, and compression algorithms.

While being relatively short to ensure the essentiality of content, a strong focus has been placed on self-containment, introducing the idea of pre/post-conditions and loop invariants to readers of all backgrounds. The programming exercises in Python will be available on the web.