.po +0.75i
.EQ
delim $$
.EN
.so /home/u8/skiena/local/macros
.SZ 11
.nf
.ce 4
.ft B
CSE 214 - Data Structures
Fall 1997
Program #1
.sp
Due: Monday, September 15, 1997
.ft R
.sp
.pp
Anyone who has played poker or any other card game is familiar with
the idea of shuffling the deck to mix it up after the game.
A perfect shuffle splits the deck into two equal halves and then interleaves
the cards, one from each half.
Perfect shuffles are good for mixing up the deck, or are they?
.pp
To be precise about what we mean by perfect shuffle, let us define
what happens to the $i$th card in a deck of $2n$ cards.
We will only consider the case where the deck has an even number of
cards, to avoid ambiguity about where to split it.
If $1 <= i <= n$, the card will go to the $2i-1$st position after shuffling,
since the first half of the deck all goes to odd positions.
If $n+1 <= i <= 2n$, the card will go to the $2(i-n)$th position.
For example, consider the case of $n=4$, with a deck of eight distinct
cards represented by the numbers 1 to 8.
What happens when we repeatedly shuffle the deck:
.sp
.nf
		1	1	1	1
		2	5	3	2
		3	2	5	3
		4	6	7	4
		5	3	2	5
		6	7	4	6
		7	4	6	7
		8	8	8	8
.fi
.pp
After only three shuffles, we are back to where we started from,
despite the fact that there are $8! = 40,320$ permutations of the
cards.
What about a normal deck of $52$ cards, which corresponds to $n=26$?
The amazing fact is that eight consecutive perfect shuffles always
take you back to the starting point.
.pp
Your first program in CSE 214 will compute and print a table of the
number of perfect shuffles necessary for a deck of $2n$ cards
to return to its initial configuration, for $1 <= n <= 100$.
A deck of cards can be represented by an array of size $2n$ whose
values are the integers between 1 and $2n$.
The shuffle operation is described above.
You should have a Modula-3 procedure ``shuffle'' which accepts a deck
consisting
of an array and a count of the number of cards in the array and which
returns the shuffled array.
.pp
You are to hand-in the electronic copy of your program files using
\fIhandin\fP.
You are also responsible to turn in a printed copy of your program, including
the output of the program, which will be a table of the number of shuffles
as a function of $n$, for $1 <= n <= 100$.
As you can verify by hand, this table begins:
.nf
	deck size	shuffles
	--------- 	--------
           2               1
           4               2
           6               4
           8               3
.fi
.pp
Note that your programs will be graded for style and clarity as well
as correctness.
Document your program to make sure the algorithm is understandable.
.sp
.ce
\fIChallenge Problems\fP
.pp
Each assignment will contain one or more extra credit problems for
students who want a challenge, or to pursue the subject in greater depth.
NOTE THAT THESE PROBLEMS ARE NOT REQUIRED.
Sometimes they will require mathematical or programming expertise
which go well beyond the class prerequisites.
In this case, important ideas can be found by studying modular arithmetic
and the cycle structure of permutations.
.np
Can you develop and implement an algorithm for determining the
repetition number without actually simulating the effect of shuffling?
How does the time your program take for $n=500$ compare with the two
programs?
.\".np
.\"Can you prove that the initial configuration always repeats after less
.\"than $2n$ perfect shuffles of a deck of $2n$ cards, for all integers $n$?
.np
Can you devise a fairly simple shuffling-like strategy which takes significantly
longer to repeat than just repeated perfect shuffles?
How long does it take to repeat for the conventional deck of 52 cards?
.lp
.sp
.ce
\fIRules of the Game\fP
.np
The main purpose of this assignment is to establish that each of you
are proficient enough with Modula-3 and the CS UG environment to ensure
that you will be ready to meet the challenge of the more demanding
programs to come.
.np
Make sure you understand the exact definition of the perfect shuffle
operation.
If you don't, there is not the slightest chance that your program will
work.
Work through the example above carefully.
.np
Debugging a program such as this is tricky without knowledge that shuffle
is working correctly.
Don't be afraid to print out the contents of the deck in an intermediate
program.
Also, don't be afraid to test it on small values of $n$ before running the
complete table.
.np
The extra credit problems are just that - extra credit.
The amount of credit you will receive for working on these problems will
be fairly small, so interest and curiousity should be the motivation instead
of greed.
It is not required or expected that you work on the extra credit problems
in order to received an A or any other grade.
.np
Include the line (without quotes) 'source ~cse214/login' in your .cshrc
file on the UG machines
This should set up you account so you can use the handin program.
.np
Don't forget to write out and sign the pledge.
``On my honor as a student I have neither given nor recieved aid on this
program.''
Your program will not be graded without it.