An Introduction to the Analysis of Algorithms

Details

• Edition 4: In progress: https://prof.msoltys.com/iaa
• Edition 3: March 2018, 328 pages, ISBN: 978-981-3235-90-8, World Scientific and Amazon, and the official DOI: https://doi.org/10.1142/10875
• Edition 2: May 2012, 215 pages, ISBN: 978-981-4401-15-9, World Scientific and Amazon.
• Edition 1: October 2009, 152 pages, ISBN: 978-981-4271-40-0, World Scientific and Amazon.
• Amazon Author Page: https://www.amazon.com/author/msoltys

Resources

• This page (http://www.msoltys.com/book)
• GitHub repository with Python solutions (http://www.msoltys.com/book-code)
• Accompanying Slides (http://www.msoltys.com/book-slides)
• YouTube videos of lectures based on sections in book
• Errata to the 3rd Edition
• Doi: https://doi.org/10.1142/10875
• To reach the publisher: sales@wspc.com.sg
• BibTex entry for the 3rd Edition:
  

  @book{soltys-algs3,
  Author = {Michael Soltys},
  Edition = {3},
  Isbn = {978-981-3235-90-8},
  Month = {March},
  Pages = {328},
  Publisher = {World Scientific},
  Title = {An introduction to the analysis of algorithms},
  Year = {2018}}

  
  

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.