I'm going to start this post with the halting problem even though it's the last thing we learnt, since it is by far the hardest thing I've faced this semester. Tracing through the halting problem wasn't too difficult, but figuring out how to reduce a given function to the halting problem is what I found specially challenging.
It took me a couple videos in addition to the lecture to really understand the logic behind the halting problem:
https://www.youtube.com/watch?v=fsE1bFWXlJQ
https://www.youtube.com/watch?v=macM_MtS_w4
Thank God for Numberphile.
Even after the assignment for which we simply duplicated the steps from the course notes to suit our needs, I'm still a bit stuck on how to reduce functions to the halting problem to prove incomputability.
On the other hand, I couldn't be more comfortable with big-oh,omega, and theta. I feel the assignments have been the greatest help in truly grasping concepts by forcing us to work through somewhat challenging problems. Having an assignment due before each major evaluation has greatly contributed to my success on the midterms so far, and hope this is a trend that will continue on to my exam.
Good Job!!!!
ReplyDelete