CS 30, Winter 2008 HW 5.
This homework is due Thursday February 21 at 11:59 pm. No late homeworks will be accepted.


0. First, run program deal.c several times, choosing each time to deal a hand of 5 cards. 
Next, modify program deal.c by commenting out the line with the srand command, and
inserting a line with srand(5000), to initialize the random number generator. 
Run the modified program several times, choosing to each time to
deal a hand of 5 cards. What do you observe and did you learn from these runs? How is what you
observed helpful in writing and debugging programs that use random numbers?
Write you answers in a file called random and submit it via handin to cs30a directory p5,
i.e., with the command: handin cs30a p5 random

1. Write a program to solve problem 13 stated on page
153 in the book. It is helpful to review the program drunk.c on the class website.

The description of problem 13 leaves one aspect of the problem ambiguous. It is
that when a proposed move is not possible (because it goes out of the array or to
an already marked cell in the array), the description just says ``try moving in another direction". 
That is a bit vague and instead here are more explicit instructions. Before doing any move,
check that there is some legal move possible. If there is no legal move possible, then the program
must terminate. Otherwise, continue (iterate) the following until a legal move is generated: 
generate a random number and find its remainder when divided by four (as described in the problem description),
and check if that remainder specifies a legal move.
When a legal move is generated, make the move.

Note added Feb. 19:
To make the instructions more concrete (which is needed to make two programs produce the same output),
use the following correspondence between the numbers 0, 1, 2, 3 
and the legal moves in program walk.c: 0 corresponds to up, 1 to left, 2 to down and 3 to right.


Also (note added Feb. 18) since there are 100 cells in a 10 by 10 array, it is possible for the program, as
presently described,
to make more than 25 moves, using up all the capital letters. So, change the instructions to say that if
Z is printed, the program should stop. 

An executable of walk can be run on any csif machine by using

~gusfield/cs30w08/walk

In order for you to compare your results with ours,
we will also post a second executable, called walk5000, that initializes the random number generator using the
statement srand(5000). You should also write two programs that differ only in the way the random generator
is initialized. One program, whose source code you must call walk.c, should initialize the random number generator
by using time, as in drunk.c or deal.c, and the other program, whose source  code you must call walk5000.c, should use
srand(5000) to initialize the random number generator.

An executable of walk5000 can be run on any csif machine by using

~gusfield/cs30w08/walk5000
 
Your program walk5000 should produce EXACTLY the same output as our program walk5000, **when it is run on a csif machine**.
It is possible that your output on a different machine will be different.

Submit walk.c using handin cs30a p5 walk.c
submit walk5000.c using handin cs30a p5 walk.c
submit two scripts (one for walk.c and other for walk5000.c) that lists the source code, compiles it,
and runs it. Call the first script scriptwalk and the second script scriptwalk5000


2. Look at program  deal1.c posted on the class website. It modifies deal.c only in that it produces
information about the number of cards that have been selected in order to deal a hand. Run the
program and see roughly how the number of cards selected is related to the number of cards needed in 
a hand. There is nothing for you to hand in on this part.

Now we want to develop a method, and write a program, that we can use later to deal a hand, or multiple hands, based on first
efficiently finding a random shuffle of the cards. So the program in this assignment will produce a random ``permutation" of 
the integers 1 through 52. To do this, create a one-dimensional array of size 52 called card, and (using a for loop) initialize card
to have values 1 through 52 in order.  Then for i from 0 through 51, do the following: {generate a random number j between 0 and 51 inclusive;
switch the values of card[i] and card[j]}  

When the for loop is finished, the program should print out the generated permutation.

You must figure out how to switch the values without loosing either of them. It may not be obvious, but the resulting permutations
(the values in array card), is a `random' permutation. That is, each possible permutation is generated by this method with the
same probability.

When that is finished, print out the values in array card.

An executable can be run on any csif machine by using

~gusfield/cs30w08/permute

In order for you to compare your results with ours,
second executable, called permute5000, initializes the random number generator using the
statement srand(5000). It can be run on any csif machine by using

~gusfield/cs30w08/permute5000

You should also write two programs that differ only in the way the random generator
is initialized. One program, whose source code you must call permute.c, should initialize the random number generator
by using time, as in drunk.c or deal.c, and the other program, whose source  code you must call permute5000.c, should use
srand(5000) to initialize the random number generator.

Your program permute5000 should produce EXACTLY the same output as our program permute5000, **when it is run on a csif machine**.
It is possible that your output on a different machine will be different.

Submit permute.c using handin cs30a p5 permute.c
submit permute5000.c using hanin cs30a p5 permute5000.c
submit two scripts (one for permute.c and other for permute5000.c) that lists the source code, compiles it,
and runs it. Call the first script scriptpermute and the second script scriptpermute5000