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.

Your Privacy

By clicking "Accept Non-Essential Cookies" you agree ACCU can store non-essential cookies on your device and disclose information in accordance with our Privacy Policy and Cookie Policy.

Current Setting: Non-Essential Cookies REJECTED

By clicking "Include Third Party Content" you agree ACCU can forward your IP address to third-party sites (such as YouTube) to enhance the information presented on this site, and that third-party sites may store cookies on your device.

Current Setting: Third Party Content EXCLUDED

Settings can be changed at any time from the Cookie Policy page.