Table of contents
Generally-useful textbooks
The books below are all freely available in electronic format either from the University of Bristol library or (in the case of Erickson) from the author’s website here. None of them are compulsory, but if you’re having a hard time following something from lectures, it might help you to see the same thing presented in a different way. Many of the exercises in the course have also been taken from these books.
Introduction to Algorithms (Cormen, Leiserson, Rivest and Stein): This book is a truly excellent reference, and is generally considered the “standard” algorithms text. When I was learning this material for the first time, though, I found it quite dry and difficult to understand.
Algorithm Design (Kleinberg and Tardos): This book is the one I wish I’d had as an undergraduate. It moves much more slowly and spells things out in far more detail than Cormen, while being very careful not to lose sight of the overall motivation. Highly recommended.
The Algorithm Design Manual (Skiena): When I say Kleinberg and Tardos is the book I wish I’d had as an undergraduate, bear in mind that I did my undergraduate degree in maths! This book is written from a more “engineering” point of view, and assumes less ability to prove things, than either of the books above. I particularly like the “war stories” in each chapter, which give examples of how the techniques we cover in this course can be used in practice.
Algorithms (Erickson): Frankly I don’t know much about this book - I’ve only looked at the chapter on spanning trees in any detail - but that chapter talks about both Borůvka’s algorithm and Hyperbole and a Half, a combination which instantly won my respect. The book opens by quoting Skiena: “It is traditional for the author to magnanimously accept the blame for whatever deficiencies remain. I don’t. Any errors, deficiencies, or problems in this book are somebody else’s fault, but I would appreciate knowing about them so as to determine who is to blame.” It then warns the reader that it contains “several mistakes, bugs, gaffes, omissions, snafus, kludges, typos, mathos, grammaros, thinkos, brain farts, poor design decisions, historical inaccuracies, anachronisms, inconsistencies, exaggerations, dithering, blather, distortions, oversimplifications, redundancy, logorrhea, nonsense, garbage, cruft, junk, and outright lies, all of which are entirely Steve Skiena’s fault”. A much more light-hearted approach to the subject than the other options on the list.
Sometimes I will also recommend parts of other books, generally when none of the above four books cover a topic well enough.
Resources for specific weeks
Week 1
- Cormen et al.: Chapters 3.1 and 3.2 cover O-notation.
- Kleinberg and Tardos: Chapters 2.1 and 2.2 cover O-notation.
- Skiena: Chapter 1.3 covers proof in general, with 1.3.4 dedicated to induction in particular. Chapters 2.1 to 2.5 cover O-notation.