Recently I visited a branch library with my sons and checked out a large number of books for them, using the self-checkout. On leaving, we set off the alarm, because at least one book had not been correctly scanned. A librarian seized the pile of books, and proceeded to determine the offending book by binary search using the alarm (his algorithm may not have worked completely if more than one book was unscanned, so he performed a final check on the original pile, after scanning the one he found). His colleague was amazed and said that everyone else uses (in effect) sequential search of the receipt, checking it with the books in hand. I was amazed: both that someone that clever was working as a librarian, and that I had finally found a real-life application of an algorithm "in the wild". I try to give many such examples when teaching algorithms courses, but they always have a slightly contrived feel to them. Of course the game of Twenty Questions is a good motivating example.
Another two questions were raised in my mind. This librarian was clearly an immigrant from East Asia. Perhaps the education system there is so much better than ours as far as algorithms are concerned. Or perhaps our immigrants are underemployed.
For more on binary search, covered in our courses COMPSCI 105 and COMPSCI 220, see this Wikipedia article.
No comments:
Post a Comment