TABLE OF CONTENTS The purpose of the case studies in this book is to demonstrate the use of some of the concepts presented in the preceding chapters. The defects analyzed are the actual mistakes made by the author when developing this software. Different people are prone to make different mistakes. Focus on the method used in debugging, rather than the particular error in question.
The algorithms implemented in the case studies for this book were chosen based on the following criteria:
There is a published design in pseudocode for the algorithm accessible in the computer science literature.
The implementation should follow the original design relatively closely so that it is easy to compare it with the design.
The algorithm computes a useful result. Toy programs do not make interesting examples.
The algorithm has excellent computational complexity. Toy programs do not make convincing examples.
The algorithm is complicated enough that some bugs would likely occur in implementing it.
The program we debug in this section is a heap sort that works on linked list structures. Heap sorts are usually explained in an undergraduate course in data structures. The data-structure books we reviewed for this example present heap sorts of integer data stored in arrays. See Algorithms in C++ (3rd ed.) [Se98] for an excellent analysis of array-based heap sorts. This example presents a heap sort that works on linked lists, written in C++.
The data-structure books present array-based heap sorts because they can be coded...
