On Monday, our group mainly focused on finishing the very last question of A2. Like I wished, there was a question on the run-time complexity, so I was the one who mostly in charge of that question. It wasn't very hard to derive the formula from the steps, but proving that T(n) in Theta was very difficult, even considering it as a bonus. I had to search my memory back to CSC165 where I had learned bigO and omega stuff, but couldn't really figure out how to. Fortunately, with help of TA, I could write at least something down, but I was not really sure, if i will be able to earn bonus or not. Hopfully, the prof. will be generous on marking the bonus.
On this week's lecture, we continued to learn the proofs of correctness of algorithms. The concept of iterative correctness was introduced and I found the iterative case much difficult than the recursive case, mainly because of the invariants.
I will spend my time over this week to review the usage of loop invariants to iterative cases, so I can fully understand the concept.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment