PLEASE:

Create a Pseudo code first, then USE JAVA and provide 2 versions of the code: Recursive and Iterative. Also, please provide the complexity of both codes (answers to a and b)!!

Thank you!!

What's the question?

In this programming part you are asked to implement phase-1 of a game called #tictactoe. #tictactoe game consists of one row of any number of squares, where some of the squares store noughts and crosses (i.e., Os and Xs), and the remaining squares store the character "#". The squares storing the "#" character each hide their actual content which must be either an X or an 0. In this programming assignment, you will design in pseudo code and implement in Java two versions of #tictactoe game phase-1. A program that takes as input your game row of any length of random number of squares with X and O, and hidden squares with "#", and finds all possible rows of noughts and crosses that can be constructed by replacing the hidden squares (storing "#") with either X or O. Version 1: In your first version, you must write a recursive method called UnHide which reads the row (and any other parameters; e.g., length, start index and end index of row, etc., if needed) and generates ALL possible combinations of that rows without the hidden "#" square. For example; given: a) A row [XOXX#00#XO), the method UnHide will display something like: XOXXOOOOXO XOXXOOOXXO XOXXXOOOXO XOXXXOOXXO b) A row [XOXX#00#XOXX#O##] the method UnHide will display something like: XOXXOOOOXOXXOO00 XOXXOOOOXOXXOOOX XOXXOOOOXOXXOOXO XOXXOOOOXOXXOOXX XOXXOOOOXOXXXOO0 XOXXOOOOXOXXXOOX XOXXOOOOXOXXXOXO XOXXOOOOXOXXXOXX XOXXODOXXOXXO000 XOXXOOOXXOXXOOOX XOXXOOOXXOXXOOXO XOXXOOOXXOXXOOXX XOXXOOOXXOXXXOOO XOXXOOOXXOXXXOOX XOXXOOOXXOXXXOXO XOXXOOOXXOXXXOXX XOXXXOOOXOXXOO00 XOXXXOOOXOXXOOOX XOXXXOOOXOXXOOXO XOXXXOOOXOXXOOXX XOXXXOOOXOXXXOO0 XOXXXOOOXOXXXOOX XOXXXOOOXOXXXOXO XOXXXOOOXOXXXOXX XOXXXOOXXOXXO000 XOXXXOOXXOXXOOOX XOXXXOOXXOXXOOXO XOXXXOOXXOXXOOXX XOXXXOOXXOXXX000 XOXXXOOXXOXXXOOX XOXXXOOXXOXXXOXO XOXXXOOXXOXXXOXX You will need to run the program multiple times. With each run, you will need to provide a random generated row size with a hidden" # tail in an incremented number from 2, 4, 6, up to 100 (or higher COMP 352 - Winter 2021 page 2 of 3 value if required for your timing measurement) and measure the corresponding run time for each run. You can use Java's built-in time function for finding the execution time. You should redirect the output of each program to an out.txt file. You should write about your observations on timing measurements in a separate text file. You are required to submit the two fully commented Java source files, the compiled executables, and the text files. Briefly explain what is the complexity of your algorithm. More specifically, has your solution has an acceptable complexity; is it scalable enough; etc. If not, what are the reasons behind that? Version 2: In this version, you will need to provide and alternative/different solution to solve the same exact problem as above). This second solution must be iterative and not recursive, and can use any linear data structure such as array, stack, queue, list. etc. a) Explain the details of your algorithm, and provide its time and space complexity. You must clearly justify how you estimated the complexity of your solution. b) Compare the complexities between version 1 and version 2 b) Submit both the pseudo code and the Java program, together with your experimental results. Keep in mind that Java code is not pseudo code. See the full details of submission details below. In this programming part you are asked to implement phase-1 of a game called #tictactoe. #tictactoe game consists of one row of any number of squares, where some of the squares store noughts and crosses (i.e., Os and Xs), and the remaining squares store the character "#". The squares storing the "#" character each hide their actual content which must be either an X or an 0. In this programming assignment, you will design in pseudo code and implement in Java two versions of #tictactoe game phase-1. A program that takes as input your game row of any length of random number of squares with X and O, and hidden squares with "#", and finds all possible rows of noughts and crosses that can be constructed by replacing the hidden squares (storing "#") with either X or O. Version 1: In your first version, you must write a recursive method called UnHide which reads the row (and any other parameters; e.g., length, start index and end index of row, etc., if needed) and generates ALL possible combinations of that rows without the hidden "#" square. For example; given: a) A row [XOXX#00#XO), the method UnHide will display something like: XOXXOOOOXO XOXXOOOXXO XOXXXOOOXO XOXXXOOXXO b) A row [XOXX#00#XOXX#O##] the method UnHide will display something like: XOXXOOOOXOXXOO00 XOXXOOOOXOXXOOOX XOXXOOOOXOXXOOXO XOXXOOOOXOXXOOXX XOXXOOOOXOXXXOO0 XOXXOOOOXOXXXOOX XOXXOOOOXOXXXOXO XOXXOOOOXOXXXOXX XOXXODOXXOXXO000 XOXXOOOXXOXXOOOX XOXXOOOXXOXXOOXO XOXXOOOXXOXXOOXX XOXXOOOXXOXXXOOO XOXXOOOXXOXXXOOX XOXXOOOXXOXXXOXO XOXXOOOXXOXXXOXX XOXXXOOOXOXXOO00 XOXXXOOOXOXXOOOX XOXXXOOOXOXXOOXO XOXXXOOOXOXXOOXX XOXXXOOOXOXXXOO0 XOXXXOOOXOXXXOOX XOXXXOOOXOXXXOXO XOXXXOOOXOXXXOXX XOXXXOOXXOXXO000 XOXXXOOXXOXXOOOX XOXXXOOXXOXXOOXO XOXXXOOXXOXXOOXX XOXXXOOXXOXXX000 XOXXXOOXXOXXXOOX XOXXXOOXXOXXXOXO XOXXXOOXXOXXXOXX You will need to run the program multiple times. With each run, you will need to provide a random generated row size with a hidden" # tail in an incremented number from 2, 4, 6, up to 100 (or higher COMP 352 - Winter 2021 page 2 of 3 value if required for your timing measurement) and measure the corresponding run time for each run. You can use Java's built-in time function for finding the execution time. You should redirect the output of each program to an out.txt file. You should write about your observations on timing measurements in a separate text file. You are required to submit the two fully commented Java source files, the compiled executables, and the text files. Briefly explain what is the complexity of your algorithm. More specifically, has your solution has an acceptable complexity; is it scalable enough; etc. If not, what are the reasons behind that? Version 2: In this version, you will need to provide and alternative/different solution to solve the same exact problem as above). This second solution must be iterative and not recursive, and can use any linear data structure such as array, stack, queue, list. etc. a) Explain the details of your algorithm, and provide its time and space complexity. You must clearly justify how you estimated the complexity of your solution. b) Compare the complexities between version 1 and version 2 b) Submit both the pseudo code and the Java program, together with your experimental results. Keep in mind that Java code is not pseudo code. See the full details of submission details below