Exercise 1. (50 points) Bounded 2D Random Walk In this problem we will write a program to simulate a 2D random walk. Imagine a random walker starting at the origin (0,0) and with equal probabilities goes up, right, down and left. For example, when the walker is at (x,y), with equal probability 1/4, his next location is at (x,y  1),(x + 1,y),(x,y + 1), or (x  1,y). Given a positive integer n, a square is defined by the following four points: (n,n),(n,n),(n,n), and (n,n). We are interested in knowing on average, what fraction of points within this square the walker visits before he touches one of the edges of the square, given he starts his walk from (0,0). One extreme example is n = 1. When the walker starts from (0,0), after one step, he will touch one of the edges of the square. There is only 1 point inside the square and the walk visits this point before he touches one of the edges. Therefore, this faction is 1 for n = 1. In the starter code 2d-random.c, implement the following function double two_d_random(int n) This function should return the fraction mentioned above. n is the integer mentioned above to define the square boundary. In the function, we first allocate memory for all the integer (x, y) coordinates inside the square boundary. This is because we need to keep track which coordinates have been visited. Allocate just one memory block and figure out how we map between (x, y) to the index of the array(we can treat this allocated memory block as an integer array). We can write a function for this mapping if needed. When deciding which way to go for the next step, generate a random number as follows. r = rand() % 4; and treat r = 0,1,2,3 as going up, right, down and left respectively. The random walk should stop once the x coordinate or y coordinate reaches n or n. The function should return the fraction of the visited (x,y) coordinates inside (not including) the square. Reminder: Do not forget to free the allocated memory block before the function ends. 

#include #include

double two_d_random(int n) {

//Fill in code below //You are fee to write some other functions this function //Allocate memory for all the integer (x, y) coordinates inside the boundary //Allocate just one memory block //Figure out how to map between (x, y) and the index of the array //We can treat this allocated memory block as an integer array //Write a function for this mapping if needed.

//When deciding which way to go for the next step, generate a random number as follows. //r = rand() % 4; //Treat r = 0, 1, 2, 3 as moving up, right, down and left respectively.

//The random walk should stop once the x coordinate or y coordinate reaches $-n$ or $n$. //The function should return the fraction of the visited $(x, y)$ coordinates inside (not including) the square.

//Do not forget to free the allocated memory block before the function ends.

}

//Do not change the code below int main() { int trials = 1000;

srand(12345); for(int n=1; n<=256; n*=2) { double sum = 0.; for(int i=0; i < trials; i++) { double p = two_d_random(n); sum += p; } printf("%d %.3lf ", n, sum/trials); } return 0; }