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 All Cookies" you agree ACCU can store cookies on your device and disclose information in accordance with our Privacy Policy and Cookie Policy.

By clicking "Share IP Address" you agree ACCU can forward your IP address to third-party sites to enhance the information presented on the site, and that these sites may store cookies on your device.