REVIEW - Algorithms + Data Structures = Programs


Title:

Algorithms + Data Structures = Programs

Author:

Niklaus Wirth

Publisher:

Prentice-Hall (1976)

Pages:

388

Reviewer:

Paul Floyd

Reviewed:

March 2024

Rating:

★★★★★


Verdict: Highly recommended.

Just a couple of days after I finished reading this book, I was very sad to read that Professor Wirth passed away at the age of 89. [1]

I’m somewhat biased and a big fan of Wirth, so there was not much question of me not giving this a five star rating. The book is long out of print, so if you are interested in getting a copy then you’ll have to scour the 2nd-hand book sites. Printed in 1975, I imagine that’s before many readers were born. I’m a bit of an oldie, but even still I was only in primary school and hadn’t yet even seen a computer.

This book doesn’t describe the Pascal language, but it does use it for all of the examples. Pascal was the first (and only, as far as I can remember) language that I’ve ever been taught. Since the language is fairly simple and similar enough to C you shouldn’t have too much difficulty following the code. If you want to try out the code then there are some compilers available ([2], [3]).

The first thing that I liked is that the book starts by stressing the importance of using the appropriate data structures. I had a good chuckle early on reading this:

We will assume that adequate computing systems provide a warning in the case of such mistaken access to a non-existent array component.

C and C++ are not adequate by that measure.

The book does show its age in a few places. No IEEE 754 floating point and one of the examples is reading and breaking into sign, mantissa and exponent the 60-bit CDC 6600 floating point data type. That’s the kind of thing that we take for granted. In a similar vein, there are several explanations of low level details like what a pointer is and how records get laid out in memory that tend to get ignored these days.

There is a chapter on recursive functions. Again for context, common compilers at the time such as FORTRAN did not support recursion (FORTRAN didn’t get standardized recursion until Fortran 90).

The chapter on dynamic data structures. With a bit of what I imagine is a compiler-writer’s perspective Wirth makes a clear distinction between records with fixed cardinality (that is, the set of all possible values) and ones with limitless cardinality. That leads us to lists, trees and hash tables. The example used for balanced binary trees is the AVL [4] tree. The paper describing RB [5] trees wasn’t to be published for another 3 years. The section on sorting I thought was OK, but I’ve read better explanations. Step-by-step diagrams would have been clearer rather than putting lots of arrows for all steps of the sort on single diagrams. The order of the steps is not obvious.

The last chapter is about compiler writing. A mini-language called PL/0 is used. The compiler is about 10 pages long.

Overall, I had good fun getting a feel for some of the challenges of computing from about 50 years ago.

References

[1] Niklaus Wirth, obituary: https://www.theregister.com/2024/01/04/niklaus_wirth_obituary

[2] Online Pascal compiler: https://www.onlinegdb.com/online_pascal_compiler

[3] Free Pascal compiler: https://www.freepascal.org

[4] AVL: tree named after the two inventors, Adelson-Velsky and Landis, see https://en.wikipedia.org/wiki/AVL_tree

[5] RB: red-black trees: see https://en.wikipedia.org/wiki/Red%E2%80%93black_tree






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.