a logo for the course

Matrix Computations

David Gleich

Purdue University

Fall 2018

Course number CS-51500

Tuesday and Thursday, 3:00-4:15pm

Location Forney G124

Extra Credit

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.

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 people, each will only receive of the total points. (So if you collaborate with one other person, you will each receive 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 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.