
# Extra Credit

This extra credit consists of two parts. You can choose to do just the first part or the first part along with other parts parts. It is due on Wednesday December 12 by 5am.

Overall note. Do not expect generous partial credit. We expect research-level work on these problems. This is not like a homework problem. Questions will require insight into the problem and methods and we expect to see solutions that go above and beyond the stated requirements.

• 25 - a fully complete solution (unlikely)
• 20 - a mostly compete solution (likely)
• 13 - a "good" but incomplete solution (likely) in a way that failed to investigate some aspect of your method. (e.g. if something looks weird and you didn't examine it, expect to lose points.) A standard homework-level solution would likely fall in here, we are expecting more on this project.

Do not attempt a part unless you intend to complete it fully. We are not interested in incomplete, partial, or "opportunistic" solutions or ideas.

The solutions should be self-contained and self-verifying. That is, you should present all the evidence you can that you have correctly implemented your ideas. We will not run any of your code, but you should provide it for reference and show how you verified that it is correct.

## Project part 0. Collaboration policy

There is a cost for collaboration on this project. First, you must declare collaborations by Wed December 5th at 5pm. Second, if you collaborate in a group of $k$ people, each will only receive $1/k$ of the total points. (So if you collaborate with one other person, you will each receive $1/2$ of the total points.) You only submit one result for the group. You must also declare collaborations as noted above and these cannot be changed afterwards.

## Problem 1.

Develop a matrix approach to determine the expected winner of a random tic-tac-toe game. Consider making your solution work for more than just a $3 \times 3$ grid.

## Problem 2

Develop a matrix approach to determine the expected length of a 2 player Candyland game in the memoryless deck model that we considered in class.