The disappearing yellow pages
For years, students taking their first steps into data structures in my class got to watch a macabre ritual: the sacrifice of a yellow pages book in the altar of binary search trees. The ritual demonstrates the efficiency of binary search trees and explains their mechanism.
I hand the yellow pages book to a student, with a task list:
Open the book at a random page; ask me if the entry I am searching for is in the left or the right part of the book; cut the book in two and keep the part that contains the entry; repeat.
To ensure integrity, I write down the target entry and I hand the information in a folded piece of paper to another student. It takes about ten repetitions before we converge to the target page. Chicago’s massive phone books are very helpful in demonstrating the efficiency of binary search trees. By the time the phone book is dumped, ceremoniously, in the classroom’s recycling bin, students have already an idea about the left/right search pattern.
My neighbors know about this trick and every time a yellow pages book is deposited at their doorstep, they bring it to me. One-third of my garage’s structural integrity comes from the stacks of yellow pages books waiting to illuminate the next generation of data structures students.
Younger students are decreasingly familiar with printed directories and dictionaries. Their experience, searching for entries, is purely electronic: type something, press enter, get an answer. Or ask Siri/Alexa/Cortana. It’s a matter of time before I walk into a classroom full of students with no idea about printed phone books. Those books holding up my garage may never fulfill their destiny on their way to the great blue bin.
