REVIEW - Algorithms and Data Structures - Design, Correctness, Analysis


Algorithms and Data Structures - Design, Correctness, Analysis


Jeffrey H. Kingston




Addison-Wesley (1997)




Mike Ellis


December 1998



The first four chapters of this book look at some of the formal methods for determining the correctness of algorithms. Plenty of easily understandable examples are included using both iteration and recursion. The advantages of using an Abstract Data Type (ADT) to produce a generalised solution are explained.

The remaining nine chapters examine many commonly encountered ADTs, including lists, stacks, queues and various species of tree. For most of the ADTs presented, several alternate realisations are examined separately and then compared to highlight their relative strengths and weaknesses. The examination is very thorough and concentrates on proving the correctness of the algorithms and quantifying their performance using (principally) O- notation. The approach used is very mathematical and can be quite involved.

A couple of chapters present algorithms solving real-world problems using ADTs previously examined. The correctness of these algorithms is proved mathematically where practical, although some results are simply given when the proof is deemed too hard.

Eiffel is used for all of the example code - an appendix is provided for Pascal/Modula-2/C/Ada programmers. Some knowledge of OO techniques, including multiple inheritance, is assumed. No mention is made of C++, nor of its Standard Template Library (STL) which includes ready-made implementations for many of the ADTs examined.

Each chapter concludes with exercise questions. Unfortunately there are no model answers: not a problem when this book is used as part of a university Computer Science course, but their omission makes these exercises less useful for personal study.

Book cover image courtesy of Open Library.