Discuss: Tutorial 12
Quick entry as placeholder. I am writing from the Launch of the code::XtremeApps:: 2008 competition. See details at
http://www.itsc.org.sg/codeXtremeApps2008.html
In T12 (last tutorial, no Q-problems, yeah!) we addressed your replies to the Fun Question (about the surprise visitors to lectures on 7th April) -- and the hidden and slightly censorted version of the replies. We talked about TM programs and ran through some examples. In the process, we worked thru the idea of abstraction, yes, abstraction even with TM programs.
Through one of the Q' problems, we talked about algorithms for "increment" and in so doing, we abstracted out the very simply rule that almost wrote itself as a TM program (scan left-to-right to the end, then move back right-to-left, change 1's to 0's and when you see a 0, convert to 1 and STOP).
Finally, one last item to end the course, and I proposed one of two things: (a) non-computability of the halting problem, or (b) zero-knowledge proofs. However, it was a no-brainer choice as the tag-line for (b) was "Amazing, fascinating, mind-boggling" and so that was what we did. For Zero-knowledge proof, I used the example of graph 3-colouring as illustration since it tied in well with the earlier mini-lecture on the Tourist Problem (remember?). I hope that the actual presentation did NOT disappoint and lived up to the tag-line.
Last tutorial, and we won't meet again till 30-April.
I will call for a meet-up after your exams and chill-out period so as to talk about what to do with the projects that you guys have worked on.
OK, guy! Your turn.