Homework Assignment 1

Magic of Perfect Shuffles

In one card trick, the magician pulls out a new deck of cards and asks for a volunteer from the audience, whose name turns out to be Susan. She shuffles the deck several times, chooses one card, then shows it to the other spectators. She reassembles the deck and hands it back to the magician. The magician shuffles the cards several times, and the tells Susan that her card is the fifth card from the top. How did he do this magic trick?

In this assignmnet you will discover the mathematics of the perfect shuffle.

Credit to Ivars Peterson MAA Online

Objectives:

Part I:

You are to implement a Java class 

public class PerfectShuffle
that simulates shuffling a deck of n (even-!) cards. Each card is labeled with a number from 0 to n-1. A perfect shuffle is performed by splitting the deck into a top part and a bottom part and then (starting with the bottom part) repeatedly taking the bottom card from each part and placing them on top of a new deck. The process called an in-shuffle is shown for a deck of 8 cards below. 
initial deck:       0 1 2 3 4 5 6 7

shuffled deck:      4 0 5 1 6 2 7 3
This process of shuffling is repeated until the original order is reproduced. Repeatedly shuffling a deck of size 8 produces the following: 
     Shuffles                Deck Order
	0		0, 1, 2, 3, 4, 5, 6, 7
	1		4, 0, 5, 1, 6, 2, 7, 3
	2		6, 4, 2, 0, 7, 5, 3, 1
	3		7, 6, 5, 4, 3, 2, 1, 0
	4		3, 7, 2, 6, 1, 5, 0, 4
	5		1, 3, 5, 7, 0, 2, 4, 6
	6		0, 1, 2, 3, 4, 5, 6, 7

Thus six in-shuffles are required to bring the cards back into their original sorted order.

Similarly, we introduce an out-shuffle - in which we interleave cards starting with the top part. Here is an out-shuffle for a deck of 8 cards: 

initial deck:       0 1 2 3 4 5 6 7

shuffled deck:      0 4 1 5 2 6 3 7
This process of shuffling is repeated until the original order is reproduced. Repeatedly shuffling a deck of size 8 produces the following: 
     Shuffles                Deck Order
	0		0, 1, 2, 3, 4, 5, 6, 7
	1		0, 4, 1, 5, 2, 6, 3, 7
	2		0, 2, 4, 6, 1, 3, 5, 7
	3		0, 1, 2, 3, 4, 5, 6, 7

Thus three out-shuffles are required to bring the cards back into their original sorted order.

It turns out that an ordinary deck of 52 cards is returned to its original order after eight out-shuffles.

The PerfectShuffle class must have the following class members:

  1. only one instance variable 
    private int[] deck;
  2. a constructor for deck initialization (in sorted order) that accepts an input parameter for an original deck size

  3. a method 
    public int[] inShuffle(int[] input)

    that performs a single in-shuffle on a given array of integers in a prescribed above fashion. The method does not change the input array.

  4. a method 
    public int[] outShuffle(int[] input)

    that performs a single out-shuffle on a given array of integers in a prescribed above fashion. The method does not change the input array.

  5. methods 
    public int perfectInShuffle()

public int perfectOutShuffle()

    that returns the number of shuffles required to take the deck to its original state.

Part II

In this part we will discover the magician trick described in the lab preliminaries. As it turns out it's possible to move the top card of a deck to ANY location by using the right combination of in- and out-shuffles.

To move the top card to any position in the deck, express that position as a binary number. Starting from the left, perform a perfect shuffle for each digit in the binary number: an out-shuffle for 0 and an in-shuffle for 1.

For example, to move a card into position 14 (15th card from the top, since we count cards starting with 0), express 14 as a binary number: 1110. Three in-shuffles and one out-shuffle, in that order, bring the top card into position 14.

In the magician card trick, position 4 (5th card from the top) is 100 in binary, so the magician performs one in-shuffle, followed by two out-shuffles.

You are to implement a method 

public int[] moveTopCard(int pos)
that takes a deck (instance class variable deck) and moves the top card into a specified position. The method returns a new deck and does not change the original deck.

Hint. use Integer.toBinaryString(pos) for converting an integer to a binary string.

Starter Code:

Download The following files

What to Submit:

You FTP the following java files Do not submit anything else like zip files, folders, desktops, class files. Make sure you do not use packages in your java files as well. Failure to do so will result in a 10 point penalty.

Grading:

Your assignment will be graded first by compiling and testing it. After that, we will read your code to determine whether appropriate method/classes were used, as well as judge the overall style and modularity of your code. Points will be deducted for poor design decisions and un-commented, or un- readable code..

Here is the point breakdown: