ACCU Home page ACCU Conference Page
Search Contact us ACCU at Flickr ACCU at GitHib ACCU at Facebook ACCU at Linked-in ACCU at Twitter Skip Navigation

Search in Book Reviews

The ACCU passes on review copies of computer books to its members for them to review. The result is a large, high quality collection of book reviews by programmers, for programmers. Currently there are 1949 reviews in the database and more every month.
Search is a simple string search in either book title or book author. The full text search is a search of the text of the review.
    View all alphabetically
Title:
Algorithms and Data Structures: Design, Correctness, Analysis
Author:
J Kingston
ISBN:
0 201 40374 9
Publisher:
Addison-Wesley
Pages:
380
Price:
£24-95
Reviewer:
Mike Ellis
Subject:
algorithms; data structures
Appeared in:
10-6
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.