7 Sources and Resources
\(\newcommand{\la}{\lambda} \newcommand{\Ga}{\Gamma} \newcommand{\ra}{\rightarrow} \newcommand{\Ra}{\Rightarrow} \newcommand{\La}{\Leftarrow} \newcommand{\tl}{\triangleleft} \newcommand{\ir}[3]{\displaystyle\frac{#2}{#3}~{\textstyle #1}}\)
From the start of my graduate work until after my promotion to full professor, my research was based in algorithms and complexity, and I wrote no programs for it. The design and analysis stayed on paper. In the first few years of the twenty-first century, I became interested in functional programming and the mathematics behind it. The conferences I now attend and the papers and monographs I now read are in the area of programming languages. This became a new lens through which to view topics I had known for decades. I didn’t ask to teach data structures, but when I was offered the opportunity, I thought it might benefit from a fresh look.
There are two major textbooks often used in data structures courses. Robert Sedgewick’s "Algorithms" was first published in 1983. It has been through many editions, and currently exists in two versions, one with this title that uses Java as the implementation language, and one called "Algorithms in C++" that has some material not in the other version. Thomas Cormen, Charles Leiserson, and Ronald Rivest’s "Introduction to Algorithms" was first published in 1990; the current fourth edition has author Clifford Stein added. I occasionally consulted these books to confirm my impression of "conventional" treatments of data structures material.
If I were required to teach a conventional course in data structures, I would probably not opt to use either of these books, but I must admit that thousands of students successfully learn from these books every year. I would probably use one of the books by Mark Allen Weiss, which seem to me to be better suited to a wider range of students, and to the way students actually use textbooks these days.
Donald Knuth’s "The Art of Computer Programming" is a canonical reference which I used to confirm certain facts presented here, but it is rather difficult to read casually, or even systematically. Many major results are given as exercises with high difficulty ratings. Learn where it is in the nearest technical library so that you can dip into it when you want a sense of the context surrounding some result.
Two books played a greater role in my preparation of this material. The book "Purely Functional Data Structures" was published in 1998, and is a version of author Chris Okasaki’s PhD thesis from 1996. I have drawn from this book for some of Chapters 2 and 3, but Okasaki goes much further than I do here (as you might expect of PhD thesis material). My title "Functional Data Structures" is a clear homage to Okasaki’s work, but I would suggest his book as optional supplementary reading after FDS, with a warning that the focus is narrow and deep rather than broad. Because of a considerable emphasis on lazy evaluation, Okasaki uses an imaginary extension of Standard ML that does not exist anywhere, with Haskell code in the appendix.
The treatment of string algorithms in Chapter 5 is partly based on material from the book "Algorithms on Strings, Trees, and Sequences", by Dan Gusfield, published in 1997. This book has an emphasis on computational biology and is aimed at graduate students and researchers. While the material I have covered can be found in many references, the advantage of the Gusfield book is its sustained and coherent treatment, and in the sheer volume of interesting material. Like the Okasaki book, there have been no updates since its initial publication.
Beyond these two books, I looked at many conference and journal papers, from the 1950s to just a few years ago. Rather than give full citations, I have listed authors and publication date in the text, which should help with Web searches if you wish to look at the originals. Many formal publications are still behind academic paywalls, but there are an increasing number of open-source journals, as well as authors exercising rights (or simply asserting them) to put their own publications on their own Web pages. University technical reports often contain early versions, or versions with more detail than conference publications with page limits, and early full papers posted at sources such as arxiv.org are another good source of information (though these early versions are not peer-reviewed and often contain small mistakes).
Anyone doing such Web searches will rapidly discover that my work here is far from comprehensive. There is much more material, some firmly situated within the functional programming literature, some ripe for a fresh perspective. Drop me a line and tell me what you discover!
7.1 Acknowledgements
I would like to thank the students of CS 240E in spring 2017 and winter 2018 for their patience in dealing with the rough cuts of this material, and the Cheriton School of Computer Science at the University of Waterloo for providing me with the opportunity to teach the course. Abel Nieto, Ifaz Kabir, Peilin Wang, and Ben Hicks offered detailed and helpful critiques of presentations, lecture summaries, assignment questions, and exams.