In the last three or four weeks, Professor Heap talked about proving the recursive and iterative Binary Search algorithms. I found them confusing because we never had a chance to really work on the any problem since we had a midterm was on Monday instead of the tutorial, and the next tutorial was Reading Break, and the tutorial exercises and quiz for today's tutorial were about the new topic: Automata and Formal Language, which I will talk about in the next post.
The way the material was presented in class was good enough, although the professor did't really do anything much except going through the proof, and the students get to ask questions--which was probably the way it should be. However, sometimes I feel like I don't know what to ask because I knew nothing about the topic when it was introduced. Perhaps I should try to spend some time trying to understand some of the material like the motivation or the introduction of the topic and going through the slides before each class. That way, I should be able to come up with good questions to ask in class and have a better grasp of the material at the end of the class.
I personally don't think learning to prove the recursive or iterative algorithms will be very useful later (in later years or when working in the CS field). I mean the techniques for proving the correctness of algorithms, recursive or whatever, is crucial, but there is too much format in what we are doing here. For example, we need to prove the pre-conditions and the post-conditions in our Proof by Induction, and we need to also show that the pre-conditions imply the program termination. As for the iterative algorithm proof, we need to show the partial correctness (i.e. everything is correct at ith iteration). But in reality, I don't think proving the correctness of algorithms will really follow these patterns.
No comments:
Post a Comment