Dr. Miracle's Research Presented at Macalester College

May 20, 2019 / By: CISC Department

CISC Assistant Professor Sarah Miracle's research was recently presented at the Mathematics, Statistics, and Computer Science Seminar (MSCS) at Macalester College. The talk detailed joint research conducted by Dr. Miracle, CISC Associate Professor Scott Yilek, and Amanda Streib from the Center for Computing Sciences in Bowie, Maryland.

Since its inception in 2001, the purpose of MSCS has been to enhance classroom learning in mathematics or computer science through lectures by people prominent in these fields. These seminars are open to the public and feature speakers both from within Macalester College and from elsewhere in the country.

 

Title:

Card Shuffling Algorithms Used in Self-Organizing Lists and Cryptography

 

Abstract:

Card shuffling (i.e. generating a random permutation) is a fundamental problem in probability theory. This talk will show how to use shuffling to design and to analyze algorithms in computer science. We will focus on two applications: format-preserving encryption schemes and self-organizing lists.

In a format-preserving encryption scheme, the format of the scrambled or encrypted data is the same as the format of the original data. We present a new algorithm for format preserving encryption based on a card shuffling algorithm.

Next, consider a list of records where each element is requested with some unknown frequency. A self-organizing list organizes the records on the fly by adjusting the ordering each time a record is requested. We use shuffling techniques to analyze the Move-Ahead-One algorithm for self-organizing lists, which moves a record one step forward whenever it is requested.