I wish I had found a better problem for the previous post. Initially I wanted to find a solution to the 2-player game where you have n columns, and m_i rings in the ith column, and each player can take as many rings as s/he wants from any one of the colums (but is not allowed to touch more than one column, and must take at least one ring). The player who takes the last ring loses. I tried to prove it using some sort of nested induction, but I failed. I did manage to solve it for the special case n=2, but then again, that is probably not very hard to do.
Anyway, later I found out that the game is called Nim, and I read it's solution and proof in wikipedia. It is safe to say I could have never solved it within the end of this semester.
Overall, I would say this was a very nice course. Regular expressions, CFG's, FSA's, and PDA's were of much greater interest to me than I thought they would be (which is not to say that I thought they would be boring). I'm definitely going to pick up a more advanced book on the subject to study during the summer. Either that or a book on computability (if anyone reading this has any suggestions, it would be nice if you told me in a comment).
I did think that the tests were marked a bit too harshly and marks were taken off for fairly trivial things, but that's ok.
No comments:
Post a Comment