The researchers at a medical center wish they had taken a computer programming course way back when they were at medical school. These days, in addition to attending their research, they find themselves entangled with having to learn the R and Python languages in order to wrangle, visualize and model data collected from patients. 1,2 They simply have no time and no patience for R or Python! So they have decided to hire you as a programmer to assist, providing you with a bit of background information and a clear description of your task. The researchers have discovered that, when certain cells are introduced into a new environment, the cells quickly form colonies. To study the effectiveness of a drug they are developing, they need to figure out the size and number of the colonies in the environment. Fortunately, they can map the environment onto a grid of Os and 1s that might, for example, look something like this: 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0 1 1 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 The locations on the grid each have a row and a column coordinates. A 1 or 0 at a location indicates, respectively, the presence or absence of a cell at that location. Colonies are formed by neighboring cells. Two cells are considered neighbors, if their locations are adjacent either horizontally, vertically, or diagonally. Thus, the maximum number of neighbors a cell can have is 3 for a corner cell, 5 for a cell on a single border, and 8 for a cell not on the borders. Given this background information, you are tasked with developing a ColonyExplorer program that explores and labels the colonies (if any). For example, using the grid above, your ColonyExplorer should produce the following information: AA - AA- B B B - ccc - c D - - - - - - - A - - - ccccc D - - A - - A A DDD - - A - A - E - CC D D D - A A A - F - - E -C- CC - C A: 14 B: 3 C: 20 D: 8 E: 2 F: 1 The information shows that there are six colonies labeled A, B, C, D, E, and F on the grid with size 14, 3, 20, 8, 2, and 1, respectively. (a) In this programming assignment, you will be developing your ColonyExplorer program (i.e., class) in two versions. Both versions must implement an algorithm named Explore AndLabel Colony. In version 1 of ColonyExplorer, the ExploreAndLabelColony algorithm is recursive. In version 2 of ColonyExplorer, the Explore AndLabelColony algorithm is non-recursive. This version is allowed to use a linear data structure such as a stack, queue, list, or vector. Both versions are required to be designed in pseudo code and implemented in Java. (b) Starting from a given location on the grid, ExploreAndLabelColony explores the grid, expanding and labeling all of the cells in a single colony originating from the starting location. Taking as input a grid, the coordinates of a starting location, and a label, Explore AndLabelColony will either label that location and all its neighbors or do nothing, depending on the presence or absence of a cell at the given location, respectively; either way, Explore AndLabelColony is required to return the size of the labeled colony. (c) ColonyExplorer is responsible for ensuring that Explore AndLabelColony is called start- ing at every location on the grid storing a 1. The reason is that Explore AndLabelColony locates only a single colony. For example, using the first grid above and calling ExploreAndLabelColony for the first time on the location at the top row and forth column will modify the grid only at the locations labeled A, leaving all the other locations intact. Once every grid location storing a 1 has been colonized, ColonyExplorer freezes the grid by replacing the Os on the grid with -s (dashes). (d) ColonyExplorer is responsible for creating an initial grid of random number of rows and columns in the range [5-20), and for filling the grid randomly with Os and 1s. (e) ColonyExplorer is responsible for generating the labels for Explore AndLabelColony to use during exploration. Use the alphabet letters A... Z and a ..- z as labels (in that order). For simplicity, cycle through and reuse the same labels if necessary. (f) Briefly explain the time and memory complexity for both versions of Explore AndLabelColony. Write your answers in a separate file and submit it together with the other programming submissions. For version 1, describe the type of recursion used in your implementation and its time and memory complexity? Justify your answer. Also explain whether a tail-recursive version is possible. If yes, you can earn bonus marks by submitting such a version. For version 2, justify your choice of the particular data structure and why you chose it over the other available structures (e.g., why you chose a stack and not a queue, etc.). Explain whether your choice has an impact on the time and memory complexity. (8) For each version provide test logs for at least 20 different initial grid configurations. The researchers at a medical center wish they had taken a computer programming course way back when they were at medical school. These days, in addition to attending their research, they find themselves entangled with having to learn the R and Python languages in order to wrangle, visualize and model data collected from patients. 1,2 They simply have no time and no patience for R or Python! So they have decided to hire you as a programmer to assist, providing you with a bit of background information and a clear description of your task. The researchers have discovered that, when certain cells are introduced into a new environment, the cells quickly form colonies. To study the effectiveness of a drug they are developing, they need to figure out the size and number of the colonies in the environment. Fortunately, they can map the environment onto a grid of Os and 1s that might, for example, look something like this: 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0 1 1 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 The locations on the grid each have a row and a column coordinates. A 1 or 0 at a location indicates, respectively, the presence or absence of a cell at that location. Colonies are formed by neighboring cells. Two cells are considered neighbors, if their locations are adjacent either horizontally, vertically, or diagonally. Thus, the maximum number of neighbors a cell can have is 3 for a corner cell, 5 for a cell on a single border, and 8 for a cell not on the borders. Given this background information, you are tasked with developing a ColonyExplorer program that explores and labels the colonies (if any). For example, using the grid above, your ColonyExplorer should produce the following information: AA - AA- B B B - ccc - c D - - - - - - - A - - - ccccc D - - A - - A A DDD - - A - A - E - CC D D D - A A A - F - - E -C- CC - C A: 14 B: 3 C: 20 D: 8 E: 2 F: 1 The information shows that there are six colonies labeled A, B, C, D, E, and F on the grid with size 14, 3, 20, 8, 2, and 1, respectively. (a) In this programming assignment, you will be developing your ColonyExplorer program (i.e., class) in two versions. Both versions must implement an algorithm named Explore AndLabel Colony. In version 1 of ColonyExplorer, the ExploreAndLabelColony algorithm is recursive. In version 2 of ColonyExplorer, the Explore AndLabelColony algorithm is non-recursive. This version is allowed to use a linear data structure such as a stack, queue, list, or vector. Both versions are required to be designed in pseudo code and implemented in Java. (b) Starting from a given location on the grid, ExploreAndLabelColony explores the grid, expanding and labeling all of the cells in a single colony originating from the starting location. Taking as input a grid, the coordinates of a starting location, and a label, Explore AndLabelColony will either label that location and all its neighbors or do nothing, depending on the presence or absence of a cell at the given location, respectively; either way, Explore AndLabelColony is required to return the size of the labeled colony. (c) ColonyExplorer is responsible for ensuring that Explore AndLabelColony is called start- ing at every location on the grid storing a 1. The reason is that Explore AndLabelColony locates only a single colony. For example, using the first grid above and calling ExploreAndLabelColony for the first time on the location at the top row and forth column will modify the grid only at the locations labeled A, leaving all the other locations intact. Once every grid location storing a 1 has been colonized, ColonyExplorer freezes the grid by replacing the Os on the grid with -s (dashes). (d) ColonyExplorer is responsible for creating an initial grid of random number of rows and columns in the range [5-20), and for filling the grid randomly with Os and 1s. (e) ColonyExplorer is responsible for generating the labels for Explore AndLabelColony to use during exploration. Use the alphabet letters A... Z and a ..- z as labels (in that order). For simplicity, cycle through and reuse the same labels if necessary. (f) Briefly explain the time and memory complexity for both versions of Explore AndLabelColony. Write your answers in a separate file and submit it together with the other programming submissions. For version 1, describe the type of recursion used in your implementation and its time and memory complexity? Justify your answer. Also explain whether a tail-recursive version is possible. If yes, you can earn bonus marks by submitting such a version. For version 2, justify your choice of the particular data structure and why you chose it over the other available structures (e.g., why you chose a stack and not a queue, etc.). Explain whether your choice has an impact on the time and memory complexity. (8) For each version provide test logs for at least 20 different initial grid configurations