Google Trends: Designing Data Structures

Data Structures

Linked list creation and manipulation; simulation of card deck shuffling

Students start with the implementation of a basic linked last class and selected functionality designed to force them to thin through the issues of modifying lists without destroying list integrity. Following this then they use the list to model a standard deck of cards, and implement a Monte Carlo simulation to determine the required number of times the deck must be shuffled in order to ensure a random ordering.

Duration: 2 weeks

Background: The student must be familiar with basic C++ syntax, C++ classes, and basic C++ memory management. There is no assumption of a statistical background: relevant statistical tools (chi-square) is explained at high-level in the documentation and is provided as a code library.

John Karro, William Brinkman

code, runtime-analysis, short-answer prose

Two Weeks

reading, writing

Implementation, hash tables, complexity analysis, linear data structures

Workplace Scenario
You have been hired by a major Casino chain to verify the Bayer-Diaconis theorem, which purports to prove how many times a 52-card playing deck must be riffle-shuffled in order to completely randomize it (that is, make sure that, when done, each card could be anywhere in the deck with equal probability – regardless of where it started.). It is extremely important to the Casino that, before each deal at the Black Jack table, a deck be shuffled enough to make the order random. Failure to do so could lead to potential biases that a player might exploit. But Bayer-Diaconis is an analytic proof – a logical deduction from first principles. Your employer wants empirical evidence that Bayer-Diaconis is correct. One possibility is to have you shuffle the desk for a few billion years and track where the cards end up, but that is impractical. What is practical is to run a simulation and apply a basic statistical tool to establish the actual bound.

Importance: Using simulation to study the behavior of complex systems is one of the primary functions of Computer Science, and this project will expose you to some of the basic principles of the area. At a lower level, it will also require you to work with linked lists – arguably one of the two most important data structures we use.

You will also be asked to read investigate the linked-list data structure and discuss aspects of the reading. In reality, you will often need to pick a data structure appropriate to your problem, frequently choosing between established structures you are unfamiliar with. This will involve a certain degree of research: reading and understanding papers or text on the options, and possibly defending your decision to a colleague, boss, or client. The questions in this assignment are intended both to test your understanding and to make sure you can coherently explain what you have learned to another party.

N/A