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.
Sunday, November 30, 2014
Friday, November 7, 2014
Counting steps, and lots of Oh's
This has been by far the most confusing part of the course. Only after a few lectures, tutorials and a couple help center sessions do I finally sort of understand this counting steps thing. I mean it's simple enough with one while loop. But when there's multiple ones within each other, the second loop being dependant on the first loop, things start getting out of control.
I don't remember the last time it took me this much time to wrap my brain around something. Maybe when they released tripe chocolate oreos.
From big-Oh we went to big-Omega, which after understanding big-Oh wasn't too hard to grasp. Least steps, Most steps... simple enough. The concepts are pretty simple to understand, it's just the actual counting of the steps in a written algorithm that's a pain to figure out. Hopefully I get better with practice.
Doing big-Oh with polynomials felt a LOT more natural. Hope to see more of these types of questions in the future :
It felt logical and mathematical and less physically straining than counting the steps in an algorithm.
I sure hope we don't have to count steps of an algorithm in our evaluations. Who am i kidding, I'm sure we'll have to count steps of an algorithm in our evaluations.
Tuesday, October 21, 2014
Proofs
Proofs & Proofs
Proofs are gradually becoming more and more difficult and more complex. Gone are the days where we just had to prove that for every odd number, itself + 1 gives an even number. I bet soon we won't even have to prove such things and they'll just be used as if it were prior knowledge as parts of bigger proofs. However, I still haven't run into anything exceptionally difficult contrary to what the upper years had warned me. Being a math kind of person I'm actually enjoying the lack of readings assigned in this course(less memorization for exams/midterms!!!)
Using the definition of floor of x, to prove properties of the floor function took a little getting used to. However, patterns emerged, and once I realized there's only two real parts to the definition proving things about it got easier and easier.
Proofs are gradually becoming more and more difficult and more complex. Gone are the days where we just had to prove that for every odd number, itself + 1 gives an even number. I bet soon we won't even have to prove such things and they'll just be used as if it were prior knowledge as parts of bigger proofs. However, I still haven't run into anything exceptionally difficult contrary to what the upper years had warned me. Being a math kind of person I'm actually enjoying the lack of readings assigned in this course(less memorization for exams/midterms!!!)
Using the definition of floor of x, to prove properties of the floor function took a little getting used to. However, patterns emerged, and once I realized there's only two real parts to the definition proving things about it got easier and easier.
Thursday, October 9, 2014
Midterms, and Proofs, and Assignment 1
Assignment one went fairly well except for the last question where I was to draw two venn diagrams. I thought I was supposed to draw diagrams representing each of the statements per pair, but I was to construct a venn diagram that'd make one false and the other true.
My midterm went faily well I feel. Only thing I wasn't a hundred percent confident about was the second part of the first question where we had to state true or false for what the function would return. i got the true or false part correct but I'm not sure if my reasoning would be accepted as valid or not.
The only challenging thing I found over the past few weeks is proofs. I have a feeling under exam conditions I won't be able to come up with or recognize that one crucial step which is necessary to continue the proof. Then again, this may be something that comes with practice, and after a while it might be a matter of looking for things I've seen before and recognizing them.
My midterm went faily well I feel. Only thing I wasn't a hundred percent confident about was the second part of the first question where we had to state true or false for what the function would return. i got the true or false part correct but I'm not sure if my reasoning would be accepted as valid or not.
The only challenging thing I found over the past few weeks is proofs. I have a feeling under exam conditions I won't be able to come up with or recognize that one crucial step which is necessary to continue the proof. Then again, this may be something that comes with practice, and after a while it might be a matter of looking for things I've seen before and recognizing them.
Friday, September 26, 2014
ANDs ORs and NOTs
I had a pretty easy time this week understanding the lecture material. I think this was mostly due to my prior exposure to using AND/OR/NOT in programming courses in the past, and after how much they drilled the concepts into our heads it was easy to think about them in terms of this logic course.
While I was working on CSC148 exercises, something that Danny said rang very true. After finishing a challenging exercise I felt a rush, and i enjoyed it so much that I immediately went onto the next week's exercise. I went at it for about an hour to no avail, and I should have probably slept on it after that since it was about 3 a.m. I was determined not to fall asleep until I finished it though so i stayed up another two hours until I finally cracked the problem in a way I felt was almost a cheat, but I was just happy that it finally worked. The lack of sleep was definitely worth the feeling of fulfillment that I after successfully coding that. The problem was to write a recursive function to map a function F into all the elements of a linked list and return a new linked list.
While I was working on CSC148 exercises, something that Danny said rang very true. After finishing a challenging exercise I felt a rush, and i enjoyed it so much that I immediately went onto the next week's exercise. I went at it for about an hour to no avail, and I should have probably slept on it after that since it was about 3 a.m. I was determined not to fall asleep until I finished it though so i stayed up another two hours until I finally cracked the problem in a way I felt was almost a cheat, but I was just happy that it finally worked. The lack of sleep was definitely worth the feeling of fulfillment that I after successfully coding that. The problem was to write a recursive function to map a function F into all the elements of a linked list and return a new linked list.
Friday, September 19, 2014
Venn Diagrams , Quantifiers, and Implications
While I've worked with Venn diagrams before, I've not been exposed to them as much as I feel like I will be this course. Its introduction in CSC165 and STA257 has made me re-evaluate the usefulness of Venn diagrams for more than just grade school material. I've brushed up using a couple youtube videos and wiki on its uses for more advanced topics.
The only area I felt a little uncomfortable over the first two weeks was about the empty set, and proving statements about the empty set. It didn't make sense intuitively that one can claim anything about the empty set and have it be true. However, with the acceptance of needing a counter example to disprove universal claims, I've come to accept, and embrace the fact that the claim "All unicorns are blue and purple with shiny eyes" is logically true.
I felt Danny did a great job in explaining implications, in that the best way for me to understand them and convert english to symbolic is to think about when certain statements will be false and work from there. I wish he had expanded on Truth tables as opposed to Venn diagrams when looking at whether /\ and => can be used in an equivalent manner. I found the difference much easier to grasp using truth tables than venn diagrams, but I suppose others might find Venn diagrams easier.
While I've worked with Venn diagrams before, I've not been exposed to them as much as I feel like I will be this course. Its introduction in CSC165 and STA257 has made me re-evaluate the usefulness of Venn diagrams for more than just grade school material. I've brushed up using a couple youtube videos and wiki on its uses for more advanced topics.
The only area I felt a little uncomfortable over the first two weeks was about the empty set, and proving statements about the empty set. It didn't make sense intuitively that one can claim anything about the empty set and have it be true. However, with the acceptance of needing a counter example to disprove universal claims, I've come to accept, and embrace the fact that the claim "All unicorns are blue and purple with shiny eyes" is logically true.
I felt Danny did a great job in explaining implications, in that the best way for me to understand them and convert english to symbolic is to think about when certain statements will be false and work from there. I wish he had expanded on Truth tables as opposed to Venn diagrams when looking at whether /\ and => can be used in an equivalent manner. I found the difference much easier to grasp using truth tables than venn diagrams, but I suppose others might find Venn diagrams easier.
Subscribe to:
Posts (Atom)