This week we started one of my favourite concepts from last year; proving correctness of algorithms! It involves proving preconditions, loop invariants, post-conditions, and termination for different algorithms, and this week we did binary search. We learned how to prove these for both iterative and recursive binary search algorithms, and once again, recursive is more complicated than iterative.
Also, our second assignment was due this week, and I know I didn't do as well on this one because after I submitted the assignment, I learned that we were not supposed to use the master theorem to answer the last question. I thought the question was rather easy if we used master theorem to prove it, but at the same time I don't see reason to learn a concept if we can't use it in the course. I guess since the master theorem is a shortcut, it is considered "cheating" to use it in certain proofs.
This week's quiz involved the master theorem, so I found it fairly easy. I lost marks on last week's quiz since I made some mistakes. I need to be more careful in avoiding making silly mistakes that cost me marks. I should also start working on the problem we're supposed to solve as part of this slog assignment.
No comments:
Post a Comment