Wow, that was a long proof for T(n) for merge sort! I understood each step of it but there's no way I could re-prove everything on my own. I would never think of the monotonicity portion of the proof on my own. Well, I would, but it would definitely take a while and not within the time limits of a test. Luckily Prof. Heap says he does not like to post test questions where students are required to regurgitate proofs so yay!
I find CSC236 to be much more interesting than other courses. Perhaps it is the way it is presented or the frequent "10 minutes to try out the example" interactivity that makes the 3 hour night course far less boring than other 3 hour courses. The surplus of room allowing for a comfortable seating space does not hurt either.
Subscribe to:
Post Comments (Atom)
1 comment:
I'd be happy if students could remember the top level steps in this proof --- proving the special case where n is a power of 2, proving monotonicity, and then extending to non-powers of 2. I certainly wouldn't require a student to put all this together under time pressure.
Post a Comment