Project 4

Last revision:  March 17 1998

Author: YourNameGoesHere

Part A (Individually Pledged):  Rats

The diagram below shows a maze with eight rooms.  The lines represent tunnels that lead between rooms.

A rat is put into room 8 and begins a search for food that's located in room 3.  From any room the rat has equal chance of going next to each of the rooms connected by a line.  So starting from room 8 the rat has a  1 in 5 chance of going to each of the rooms 1,2,4,5,7.

If the rat goes to room 1, then it has a 1 in 4 chance of visiting each of the rooms 4,6,7,8 as its next stop.

(a) Write a function nextStop[] which randomly selects the next room that the rat will visit if it is currently the room given by the argument.  (For instance, nextStop[8] should have a 1 in 5 chance of outputting each of 1,2,4,5,7.)

There is one exception:  Once the rat gets to the food she stays there so "nextStop[3]=3".  In designing your function, you might want to use the definitions of "roomList" given below.  For each room "i", "roomList[i]" gives the list of possible next rooms.  "nextStop[]" should select one of these rooms at random.

(b) Use the function "FixedPointList[]" to see how long it takes the rat to get to the food starting from room 8.  Compute an average over 100 trials.

(c) Find the average time it takes the rat if it starts in room 2.

(d) Compute averages starting from each of the 7 rooms (not including 3) to decide from which room the rat is likely to get to food most quickly.

(* supplied code *)
roomList[1]={4,6,7,8};
roomList[2]={4,6,8};
roomList[3]={3};
roomList[4]={1,2,6,7,8};
roomList[5]={7,8};
roomList[6]={1,2,4};
roomList[7]={1,3,4,5,8};
roomList[8]={1,2,4,5,7};

Part B (Individually Pledged):  Polynomial Operations

Write a set of four functions for manipulating functions as if they were polynomial coefficients, as shown in the following examples:

polyform[{1,2,3,4},x] returns 1+2x+3x^2+4x^3
polyadd[{1,2,-3},{4,-2,6,7,8}] returns {5,0,3,7,8}
polysub[{1,2,7,4},{3,1,4,4}] returns {-2,1,3}
polymult[{1,2,4},{a,b,c}] returns {a,2a+b,4a+2b+c,4b+2c,4c}.

Note that zeros at the end of a list should not occur, unless the list is a single zero ("{0}") and that coefficient lists of different lengths can be used by any of the functions.  Use pattern restrictions; do not simply convert to polynomials, perform the designated operations, and extract coefficients!