**
**The 2010 Case Lecture

###

Gaps in my Education:

Mailboxes, Libraries, and How to Insert or Delete in an Array

**Dr. Michael Bender**

SUNY Stony Brook

You just graduated. You are now working at a successful company that is hiring vigorously. At your company, M maintains the mailboxes. The mailboxes consist of trays arranged in linear order and bolted to the wall. The names on the mailboxes are alphabetized. M is grumpy with each hire because a linear number of names on the mailboxes need to be shifted by one each time a new employee comes aboard.

At SLU, S maintains the mailboxes. Each time a student matriculates, S makes room for the new mailbox using the same technique as M. However, S only needs to shift names until an empty mailbox is reached, one that belonged to a just-graduated student. S finds that he does not need to shift many names before reaching an empty mailbox.

Both M and S are implementing variants of Insertion Sort, one of the first algorithms we learn about in Computer Science. But M suffers from the poor running time of Insertion Sort, while S doesn't.

These examples illustrate what I love about computer science. Basic CS algorithms model common experiences in our daily lives. Moreover, a deep dive into these basic algorithms, can reveal a wealth of exciting ideas.

The examples above are modeled by the problem of how to insert or delete elements in an array when the array elements needs to be maintained in sorted order. I show that by interspersing a small number of gaps in the array, only a handful of elements need to be moved on an insert or delete, even in the worst case. This idea transforms the complexity of Insertion Sort. It also has applications in databases, file systems, and more advanced data structures.

The presentation of awards will follow the talk at approximately 5:15.