In this lecture, we solve the chinese ring puzzle. This lecture is not just about presenting a solution to the mentioned problem but the thing one learns here is how you can approach such problems. Here is what we do in this lecture...

- Model the problem in mathematical terms.
- Come up with the solution algorithm by thinking recursively(that is, by thinking like, can we solve for n rings if we had solution for n-1 rings)
- Creating recurrence relation for the complexity from the algorithm
- Notice that we can not solve it with *repeated substitution technique*(though there are other techniques, but only this technique has been covered till now), so we try to make a guess by looking at T(1), T(2), T(3).....
- We form a conjecture based on the pattern and then prove the conjecture with induction
- Then we reduce the original complex recurrence relation into a very simple recurrence relation that is solvable easily with repeated substitution techniue.
- We make other important observations like the pattern in the binary representation of T(1), T(2)... that immediately fits a pattern in the first look, so the moral is that one can try looking at alternate representations of the same thing to get different interesting perpectives... explore!
- Then we make a note that the sequence generated by chinese ring configurations is also a gray code sequence that is the next configuration in the sequence differs from previous only by one bit.

Here are my notes...

## No comments:

## Post a Comment