Hello, world. I'm posting this blog post after exams, so this post is not really an entry for the course SLOGs.... it's more like a Dear Diary entry where I pour out the contents of my aching heart. A soliloquy of my despair.
I'm currently in a state of panic. I went into the exam feeling fairly confident. I mean, I was able to answer all of the questions from the 2010/2013 exams, how bad could it possibly be? As long as I got over 40%, I'd still end up with a mark in the 70s. I prepared so much for it. My cheat sheet was crammed full of all of the possible questions from the assignments, tests, and lecture notes.
*echoing* Prepared so much for it. Prepared so much for it. Prepared so much for it *echoing*
On a scale of 1-10, I bombed that exam with a 100. I don't think I could have possibly messed up more than I did on that exam, besides like.... not showing up for the exam at all. All of the questions I thought would be on the exam, all of the questions that I prepared for.... were not on the exam. No halt (!!) , no generic big-Oh, no conversion of statements (Not all, Any). Nope. Nope. Nope.
I pretty much threw a course worth of achievements (I was so, so proud of my grade in the course... a mark in the high 90s) into a pile of feces.
I was expecting delta-epsilons to be on the exam, but I wasn't expecting TWO such questions to be on the exam. And they weren't ones I was familiar with. As soon as I saw the two, my mind went blank. Then I realized I couldn't solve both. I entered this state of complete and utter panic. I started sweating. My mind went blank. I'm actually fairly certain I was shaking at one point.
All of the questions I successfully answered, I somehow managed to misread the questions, and actually answer the wrong question. You're not reading that wrong. All of the questions that I SHOULD have gotten right, I somehow managed to prove something... that didn't even answer the question they asked. So I bombed the exam. Thoroughly.
How does one do this? How does one throw away a semester's worth of efforts in the matter of 3 hours. I failed that exam, without a matter of a doubt. We will be receiving our marks before Christmas, but I already know the result.
I went into the exam with high 90s, and now I'm not going to meet the minimum requirement for passing the course. I am going to have to repeat this course. I don't think words exist to describe how sad I am right now.
What is life.
Friday, December 12, 2014
Tuesday, December 2, 2014
That last minute struggle
After creeping and commenting on people's SLOGs over the course of this semester, I have to say that it's remarkable how people have gone from 2 posts all semester long (and this was the case for most people's SLOGs even 2 weeks ago!!!), to walls of texts. Oh, University, how is it that you are able to bring out the procrastinator that lies deep within all of our hearts.
Overall, I feel that the SLOGs are an excellent way of proving to yourself that you know what you're talking about. It's one thing to understand a concept, and another to demonstrate that you actually do understand the concept that you claim to understand. Was that statement extremely convoluted? Yes. But you know what I mean.
Throughout this semester, I've often gone from assuming that I understood a concept-- to realizing that I didn't. This was helped in part by reading SLOGs. I found it helpful to utilize other student's SLOGs to gain a better understanding of certain concepts. You often learn more from people who are also learning the material themselves. Good times.
Another thing that I have noticed is that I have spent a disproportionate amount of time in this course convincing others to realize why their proofs are insufficient or wrong. I'm not normally a confrontational person, but it can be a little exasperating at times when you're arguing with group members. You cannot prove a statement by restating it -- and you also cannot prove a statement by cleverly manipulating your proof so that it proves your statement, but only in certain cases. I'm not telling you that my answer is correct, but I'm most certainly pointing out why your proof cannot be correct.
After spending a semester taking CSC165, I have come to the realization that, although I have difficulty actually proving proofs, I have a strong foundation -- I can almost always tell when a proof is insufficient or wrong. I have also done enough practice proofs and studying to ensure that I am able to write proofs for the vast majority of proofs I should encounter in the exam. Hopefully this statement holds true for the actual exam. I also hope that, in the future, I will be able to devise proofs to problems with which I have not had prior experience with. Perhaps hone my intuition and induction skills?
Overall, it's been a great run. I can honestly say that this is most probably the only kind of course in which I would hear two students arguing over office hours with interjections of "BUT MY PROOF IS MORE ELEGANT" <-- legitimately, this was screamed aloud during Larry's office hours. Oh, UofT, you really, truly amaze me sometimes.
Anyways, I would 10/10 take this course again, and I would highly recommend it to any student - regardless of their major. Informative, educational, and enjoyable. Unfortunately, this SLOG will be seeing its imminent demise after the due date tomorrow, but it's been a great run.
Adieu!
Overall, I feel that the SLOGs are an excellent way of proving to yourself that you know what you're talking about. It's one thing to understand a concept, and another to demonstrate that you actually do understand the concept that you claim to understand. Was that statement extremely convoluted? Yes. But you know what I mean.
Throughout this semester, I've often gone from assuming that I understood a concept-- to realizing that I didn't. This was helped in part by reading SLOGs. I found it helpful to utilize other student's SLOGs to gain a better understanding of certain concepts. You often learn more from people who are also learning the material themselves. Good times.
Another thing that I have noticed is that I have spent a disproportionate amount of time in this course convincing others to realize why their proofs are insufficient or wrong. I'm not normally a confrontational person, but it can be a little exasperating at times when you're arguing with group members. You cannot prove a statement by restating it -- and you also cannot prove a statement by cleverly manipulating your proof so that it proves your statement, but only in certain cases. I'm not telling you that my answer is correct, but I'm most certainly pointing out why your proof cannot be correct.
After spending a semester taking CSC165, I have come to the realization that, although I have difficulty actually proving proofs, I have a strong foundation -- I can almost always tell when a proof is insufficient or wrong. I have also done enough practice proofs and studying to ensure that I am able to write proofs for the vast majority of proofs I should encounter in the exam. Hopefully this statement holds true for the actual exam. I also hope that, in the future, I will be able to devise proofs to problems with which I have not had prior experience with. Perhaps hone my intuition and induction skills?
Overall, it's been a great run. I can honestly say that this is most probably the only kind of course in which I would hear two students arguing over office hours with interjections of "BUT MY PROOF IS MORE ELEGANT" <-- legitimately, this was screamed aloud during Larry's office hours. Oh, UofT, you really, truly amaze me sometimes.
Anyways, I would 10/10 take this course again, and I would highly recommend it to any student - regardless of their major. Informative, educational, and enjoyable. Unfortunately, this SLOG will be seeing its imminent demise after the due date tomorrow, but it's been a great run.
Adieu!
Computability
I promised, and I shall deliver.
When we disprove the existence of a working halt function, what we are doing is claiming that not only has a working function not been written, but that a halt function cannot possibly exist. The disproof outlined in the coursenotes uses proof by contradiction.
First, assume that the halt function exists.
In this example, the author has cleverly constructed a function, confused, where if confused is passed itself as an argument, one can deduce that there will be two cases here: that the function confused(), when passed itself as an argument confused(confused) will either halt, or it will not halt. Now, this is where things were a little confusing. To completely the paradox, one must pass confused as an argument on itself. Not just any two functions will do. By doing so, we arrive at a contradiction.
Case 1: Assume confused(confused) halts:
Then halt(confused,confused) returns True.
Then confused(confused) goes into an infinite loop.
So, confused(confused) halts ==> confused(confused) does not halt.
Case 2: Assume confused(confused) does not halt:
Then halt(confused, confused) returns False.
Then confused(confused) halts.
So, confused(confused) does not halt ==> confused(confused) halts.
From this, we can conclude that confused(confused) halts <==> confused(confused) does not halt.
Thus P <==> not P. This is a contradiction. Therefore, the halt function is non-computable.
_________________________________________________________________________________
Reductions are a way to prove the non-computability of a function.
In a reduction, we first assume that our function is computable, and derive a proof by contradiction. By doing so, we prove that if our function is computable, then the halt function is computable. Since we have already proven that the halt function is not computable, we arrive at the contrapositive of our derived implication: that our function must be non-computable. The trick is to create a function f_prime() that utilizes the function f(i) within its body in a cleverly constructed way. If we are able to reduce halt to the meaning of life, we have produced a valid implementation of the halt function using our function. i.e we are able to utilize our function with arguments f_prime and i to determine whether or not a function halts on an input i. We know that this is not possible.
A function f is computable iff it is well-defined and we can tell how to compute f(x) for every x in the domain. In general, a function that remarks on the behaviour of another function will be non-computable.
When we disprove the existence of a working halt function, what we are doing is claiming that not only has a working function not been written, but that a halt function cannot possibly exist. The disproof outlined in the coursenotes uses proof by contradiction.
First, assume that the halt function exists.
In this example, the author has cleverly constructed a function, confused, where if confused is passed itself as an argument, one can deduce that there will be two cases here: that the function confused(), when passed itself as an argument confused(confused) will either halt, or it will not halt. Now, this is where things were a little confusing. To completely the paradox, one must pass confused as an argument on itself. Not just any two functions will do. By doing so, we arrive at a contradiction.
Case 1: Assume confused(confused) halts:
Then halt(confused,confused) returns True.
Then confused(confused) goes into an infinite loop.
So, confused(confused) halts ==> confused(confused) does not halt.
Case 2: Assume confused(confused) does not halt:
Then halt(confused, confused) returns False.
Then confused(confused) halts.
So, confused(confused) does not halt ==> confused(confused) halts.
From this, we can conclude that confused(confused) halts <==> confused(confused) does not halt.
Thus P <==> not P. This is a contradiction. Therefore, the halt function is non-computable.
_________________________________________________________________________________
Reductions are a way to prove the non-computability of a function.
In a reduction, we first assume that our function is computable, and derive a proof by contradiction. By doing so, we prove that if our function is computable, then the halt function is computable. Since we have already proven that the halt function is not computable, we arrive at the contrapositive of our derived implication: that our function must be non-computable. The trick is to create a function f_prime() that utilizes the function f(i) within its body in a cleverly constructed way. If we are able to reduce halt to the meaning of life, we have produced a valid implementation of the halt function using our function. i.e we are able to utilize our function with arguments f_prime and i to determine whether or not a function halts on an input i. We know that this is not possible.
A function f is computable iff it is well-defined and we can tell how to compute f(x) for every x in the domain. In general, a function that remarks on the behaviour of another function will be non-computable.
Thursday, November 27, 2014
CSC165 - Using CSC165 outside of CSC165
I have created an account with ProjectEuler (https://projecteuler.net) in order to utilize the skills that I have learned in CSC165. Attempting to solve challenging mathematic and computational problems outside of the curriculum is actually almost therapeutic and relaxing. Although the algorithms that I have been implementing have been primitive, at best, it has been an educational experience. I hope that, as I progress through the problems, that my inductive reasoning skills will be honed. Endurance! Perseverance! Euler!
On a side note, I have actually come to understanding the halting problem and computability. Huzzah! I will update this blog with a heartwarming tale of an underdog overcoming all odds in order to achieve her dreams. Or, I'll update this blog with an explanation of the halting problem and computability. One of the two. 'Till next time. Adieu!
On a side note, I have actually come to understanding the halting problem and computability. Huzzah! I will update this blog with a heartwarming tale of an underdog overcoming all odds in order to achieve her dreams. Or, I'll update this blog with an explanation of the halting problem and computability. One of the two. 'Till next time. Adieu!
Friday, November 21, 2014
CSC165 - Bless office hours
We have learned about the halting problem this week and, for the most part, everything has gone in one ear and out the other. Even referring to the course notes and reviewing the lecture notes did not really give me the confidence that I was actually comprehending what I was incessantly studying.
After I requested a last-minute office hour with one of the professors for the course (thank you thank you thank you thank you!!), I can now confidently say that I may or may not understand reductions and computability (haha). Okay, but no, seriously. I now have a much clearer understanding of the halting problem, and what we're trying to prove when we prove that halt is non-computable. I'm also more confident about reductions; where we prove that another function, F, is non-computable by reducing halt to the aforementioned function. In essence, we prove that a function is not computable by implementing a valid implementation of halt using the function F.
In disproving the the halting problem, we perform a proof by contradiction by assuming that the halt function is computable. After we construct a function that contradicts the halt function, we can use proof by cases to show that there exists a function that contradicts itself by halting when it doesn't halt, and doesn't halt when it's supposed to halt.
---Update--
Sadly, despite his excellent explanation and step-by-step guidance... I have come to realize that I still do not understand the halting problem.
After I requested a last-minute office hour with one of the professors for the course (thank you thank you thank you thank you!!), I can now confidently say that I may or may not understand reductions and computability (haha). Okay, but no, seriously. I now have a much clearer understanding of the halting problem, and what we're trying to prove when we prove that halt is non-computable. I'm also more confident about reductions; where we prove that another function, F, is non-computable by reducing halt to the aforementioned function. In essence, we prove that a function is not computable by implementing a valid implementation of halt using the function F.
In disproving the the halting problem, we perform a proof by contradiction by assuming that the halt function is computable. After we construct a function that contradicts the halt function, we can use proof by cases to show that there exists a function that contradicts itself by halting when it doesn't halt, and doesn't halt when it's supposed to halt.
---Update--
Sadly, despite his excellent explanation and step-by-step guidance... I have come to realize that I still do not understand the halting problem.
Thursday, November 13, 2014
Under-estimating and Over-estimating
We have been covering big-oh notation over the past couple of weeks, and I feel that I'm starting to finally understand the basic concepts behind it. Progress? Maybe?
I think the most important realization was that when given a f(n) >= cg(n), that you should approach the problem by "under-estimating" the right and "over-estimating" the left, and ultimately meeting in the middle. Then, choose a c that makes the right-side an upperbound.
To under-estimate (Right Side)
- remove a positive term
- multiply a negative term
To over-estimate (Left Side)
- remove a negative term
- multiple a positive term
We're trying to simplify the function without changing the highest degree.
Progress has been made, folks.
Saturday, November 8, 2014
Search methods, Sort methods, Big-O
We have been learning about big-oh notation in the last couple of weeks. More specifically, we have been learning about three sets of notations: including O, omega, and theta. These sets encompasses the sets of function that either grow no faster, no slower, or as fast as various base functions f(n).
Looking up the graphical representations of these functions was actually a refresher; as I have not taken any true math courses for quite a while. Review will be necessary.
It was interesting to think of functions not in run time, but in growth. Rather than assessing a function for its capacity to run within seconds, we look towards the growth in the steps as the input increases, as a means of testing the efficiency of a function. This is certainly a new approach to measuring run times, as someone with limited exposure to programming. I look forward to broadening my knowledge in this area over the course of the next few weeks.
Subscribe to:
Posts (Atom)