In C programming,

Given the game tic-tac-toe on nxn board, write a recursive program that runs the game using two-synthetic players. A sample skeleton of the program is shown below

main()

{

X-player()

Print the score (i.e. is X the winner, O the winner or a draw)

}

X-player()

{

check if game is over

select a play

update the board

O-player()

}

O-player()

{

check if game is over

select a play

update the board

X-player()

}

10pts a) Write and execute the above algorithm. The board can be of any size.

3pts b) Execute you program for different values of n=2 to 100. Record the execution time of your algorithm. Make sure to exclude I/O operations.

3pts c) Write a recurrence equation for the asymptotic complexity of your algorithm. Think of the remaining options after each play. Are you evaluating all the possible options when you select a play? Solve the recurrence to find the asymptotic complexity of your algorithm.

4 pts d) Write your report and submit your findings. Discuss how you implemented select a play. How can you improve it. Discuss your time complexity. How does it depend on your implementation of select a play.