In this exercise, we write code to simulate the spread of contagious diseases. In particular, we assume: 1. There are m hosts of a certain contagious disease. 2. These hosts are located on a two dimensional grid. 3. There are three different types of hosts: (a) susceptible hosts - have not been infected by the disease (b) infected hosts - have been infected by the disease and have not yet recovered (c) recovered hosts - have recovered from the disease (Note: recovered hosts will not be infected by the disease any more) Initially there is a single infected host located at (0, 0), and the rest of the m 1 hosts are susceptible hosts, and they are randomly located on a 2D grid with edges that warp around (like Pacman). The center of the grid is at (0, 0), and the four corners are at (k, k),(k, k),(k, k) and (k, k), respectively. When a host moves outside of a border, they will appear on the opposite side. For example, if a host at (x, k) moves up, they will appear at (x, k), where k x k. The hosts move according to a 2D random walk. Use rand() % 4 to generate a direction according to the following mapping: 0 - up 1 - right 2 - down 3 - left When a susceptible host is at the same location as one or more infected hosts, the susceptible host becomes infected and will be contagious at the next time step. An infected host will become a recovered host T time steps after they are infected. As time goes by, the number of infected hosts will eventually drop to 0. When this happens, the number of susceptible and recovered hosts will not change any more. The simulation will be stopped at this moment. In the end, we print out the proportions of hosts which are susceptible, infected, and recovered. Hint: the number of infected should always be zero at the end of the simulation! We use a structure Host to describe a host. Note how we use enum in the code. enum TYPE {S, I, R}; typedef struct Host { int id; int x, y; int t; TYPE type; } THost; 1 Here, id is the id of a host, (x, y) is the coordinates of a host, t is the duration since a host became infected, and type is the type of a host. To speed up the simulation, we implement a hash table to save the location information of all the infected nodes. The hash table is implemented as an array of linked lists. The size of the hash table is N. In each round of the simulation, for each infected host, a copy of this host is inserted into the hash table according to the hash value calculated based on the coordinate of the host. To insert an infected host into the hash table, we first map its (x, y) coordinate to an integer. We then apply a hash function (that is given in the code) to the resulting integer. A modulo operation is applied on the result to ensure it fits into the range of the index of an array of size N. The infected node will be inserted into the front of the corresponding linked list. For each susceptible host, we apply the same mapping and hash function to look up the corresponding linked list and see whether there is an infected host with the same coordinates. If there is, this susceptible host becomes an infected host. Below is the main() function for this program. Note how we use command line arguments. Note k is the grid size parameter; m is the number of hosts; T is the duration parameter for an infected host to recover; and N is the size of the hash table. int main(int argc, char *argv[]) { if(argc != 5) { printf("Usage: %s k m T N ", argv[0]); return 0; } int k = atoi(argv[1]); int m = atoi(argv[2]); int T = atoi(argv[3]); int N = atoi(argv[4]); assert(k >= 0 && k <= 1000); assert(m >= 1 && m <= 100000); assert(T >= 1); assert(N > 0 && N <= 100000); srand(12345); //initialize hosts THost hosts[m]; hosts[0].id = 0; hosts[0].x = 0; hosts[0].y = 0; hosts[0].t = 0; hosts[0].type = I; 2 for(int i = 1; i < m; i ++) { hosts[i].id = i; hosts[i].x = rand() % (2*k + 1) - k; hosts[i].y = rand() % (2*k + 1) - k; hosts[i].t = 0; hosts[i].type = S; } //initialize linked lists node *p_arr[N]; for(int i = 0; i < N; i++) { p_arr[i] = NULL; } node *r = create_node(hosts[0]); int index = hash(idx(hosts[0].x, hosts[0].y, k)) % N; add_first(&(p_arr[index]), r); //simulation while(one_round(hosts, m, p_arr, N, k, T)); return 0; } Below are outputs from a few sample runs. We can use these outputs to check our code. $ time ./epidemic 150 100000 10 100000 S I R 0.015700 0.000000 0.984300 real 0m2.991s user 0m2.988s sys 0m0.000s $ time ./epidemic 150 100000 10 10000 S I R 0.015700 0.000000 0.984300 real 0m2.765s user 0m2.764s sys 0m0.000s $ time ./epidemic 150 100000 10 1000 S I R 0.015700 0.000000 0.984300 real 0m3.424s user 0m3.420s sys 0m0.000s $ time ./epidemic 150 100000 10 100 S I R 0.015700 0.000000 0.984300 3 real 0m5.868s user 0m5.864s sys 0m0.000s $ time ./epidemic 150 100000 10 10 S I R 0.015700 0.000000 0.984300 real 0m27.748s user 0m27.744s sys 0m0.000s $ time ./epidemic 150 100000 10 1 S I R 0.015700 0.000000 0.984300 real 2m49.609s user 2m49.604s sys 0m0.004s The above outputs show how the size of the hash table N affects the time needed for the simulation. Note the simulation times range from 2.765 seconds to 2 minutes and 50 seconds. The longest time corresponds to using a single linked list, while the shortest time corresponds to using a hash table of size 10, 000. Note when we further increase the hash table size, the performance starts to drop. Think why this is the case. This is the starter code: #include #include #include enum TYPE {S, I, R}; //TODO: Implement idx //idx returns an integer to be used for hashing //this integer should be unique for every x, y pair in your grid int idx(int x, int y, int k) { } typedef struct Host { int id; int x, y; int t; enum TYPE type; } THost; typedef struct node_tag { THost host; struct node_tag * next; } node; //create a node whose value is a specific host //return a pointer to the created node node * create_node(THost host) { } //add_first() should add to the beginning of a linked list //note the type: 'node **head' //note that it does not return a value void add_first(node **head, node *newnode) { } //remove the first node from the list //note the type: 'node **head' //return a pointer to the removed content node * remove_first(node **head) { } //remove all the nodes in the list //and free all the allocated memory void remove_all(node **head) { } //location_match checks whether a linked list contains //one or more hosts in the same location as 'host' //return 1 if there is a match, 0 if not int location_match(node *head, THost host) { } //hash function included for your convenience :) unsigned hash(unsigned a) { a = (a ^ 61) ^ (a >> 16); a = a + (a << 3); a = a ^ (a >> 4); a = a * 0x27d4eb2d; a = a ^ (a >> 15); return a; } //summary prints out the proportions of different host types. //It returns 1 if the number of infected hosts is not 0. int summary(THost hosts[], int m) { int S_n, I_n, R_n; S_n = I_n = R_n = 0; for(int i = 0; i < m; i++) { S_n += (hosts[i].type == S); I_n += (hosts[i].type == I); R_n += (hosts[i].type == R); } if(I_n == 0) { printf(" S I R "); printf("%lf %lf %lf ", (double)S_n/(S_n + I_n + R_n), (double)I_n/(S_n + I_n + R_n), (double)R_n/(S_n + I_n + R_n)); } return I_n > 0; } // one_round int one_round(THost *hosts, int m, node *p_arr[], int n_arr, int k, int T) { //S -> I and I -> R for(int i = 0; i < m; i++) { if(hosts[i].type == S) //Note the use of enumerator S { //finish the following line of code int index = hash(idx(hosts[i].x, hosts[i].y, k)) % n_arr; if(location_match(p_arr[index], hosts[i])) { //TODO: fill in what should happen here (not long) } } else if(hosts[i].type == I) { //TODO: fill in what should happen here (not long) } } //TODO: fill in code below //reset all linked lists for(int i = 0; i < m; i++) { int r = rand() % 4; //finish the follow code //0: up, 1: right, 2: down, 3: left //TODO: update locations for all hosts switch(r) { case 0: hosts[i].y = case 1: hosts[i].x = case 2: hosts[i].y = case 3: hosts[i].x = } //buid linked list for I hosts if(hosts[i].type == I) { node *r = create_node(hosts[i]); int index = hash(idx(hosts[i].x, hosts[i].y, k)) % n_arr; add_first(&(p_arr[index]), r); } } return summary(hosts, m); } int main(int argc, char *argv[]) { if(argc != 5) { printf("Usage: %s k m T N ", argv[0]); return 0; } int k = atoi(argv[1]); int m = atoi(argv[2]); int T = atoi(argv[3]); int N = atoi(argv[4]); assert(k >= 0 && k <= 1000); assert(m >= 1 && m <= 100000); assert(T >= 1); assert(N > 0 && N <= 100000); srand(12345); //initialize hosts THost hosts[m]; hosts[0].id = 0; hosts[0].x = 0; hosts[0].y = 0; hosts[0].t = 0; hosts[0].type = I; for(int i = 1; i < m; i ++) { hosts[i].id = i; hosts[i].x = rand() % (2*k + 1) - k; hosts[i].y = rand() % (2*k + 1) - k; hosts[i].t = 0; hosts[i].type = S; } //initialize linked lists node *p_arr[N]; for(int i = 0; i < N; i++) { p_arr[i] = NULL; } node *r = create_node(hosts[0]); int index = hash(idx(hosts[0].x, hosts[0].y, k)) % N; add_first(&(p_arr[index]), r); //simulation while(one_round(hosts, m, p_arr, N, k, T)); return 0; }