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!

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.

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. 

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. 

Hmmmm......

Well, after reviewing the blogs of my fellow classmates, I feel less guilty about not updating my blog more frequently. I have greater than one blog entry. That's a start! What? What's that you say? I shouldn't be comparing myself to others, and the assignment outline details that I should be updating at least once a week? Rubbish!

Just kidding. Please don't hurt me.

Anyways, the midterm is fast approaching, and proofs will be the death of me. Upon reviewing last year's assignment and midterm, I feel fairly confident. But proofs with multiple quantifiers still confound me. Unfortunately, the assignment this year is one that I find (personally) more difficult to parse than last year's version.  My way of approaching proofs with multiple quantifiers, with variables appearing in the statement out of the order in which they have been quantified, is to first pray that it's an epsilon delta proof, and then to assess which variable comes first (epsilon or delta). Whichever variable appears second "wins". That is my only approach. THE END.


... Okay clearly that will not help me. But one can dream.

Claim 1.2 appears to be very similar to a delta epsilon proof. However, the quantifiers are placed out of order, so I'm a little lost

I will update as soon as I figure out what I am doing with my life.

Proving a Proof

Tips and tricks!

Whenever you introduce a let statement in a proof (when you pick a variable), conclude the end of that margin with an existential.
Whenever you introduce a generic variable , conclude the end of that margin with a universal.

Brief review of floors:
- The floor of x is the largest integer that is less than or equal to x.
- The floor of x is not a variable. It is a function, and quantifiers only apply to variables, so you cannot use a quantifier directly on floor.

Definition of floor:
Assume y is an int. Then y is less than or equal to x. Among all ints that are less than or equal to x, y is the LARGEST.

Note that the symbolic definition of floor and the english definition of floor are equivalent; one is just simpler to parse as a native english speaker.

Encountering failure.

" So why do I talk about the benefits of failure? Simply because failure meant a stripping away of the inessential. I stopped pretending to myself that I was anything other than what I was, and began to direct all my energy into finishing the only work that mattered to me. Had I really succeeded at anything else, I might never have found the determination to succeed in the one arena I believed I truly belonged. I was set free, because my greatest fear had been realised, and I was still alive, and I still had a daughter whom I adored, and I had an old typewriter and a big idea. And so rock bottom became the solid foundation on which I rebuilt my life.

You might never fail on the scale I did, but some failure in life is inevitable. It is impossible to live without failing at something, unless you live so cautiously that you might as well not have lived at all – in which case, you fail by default."

- J.K. Rowling

It's odd to discuss failure in a CSC165 post given that my grade in the course is currently above 99%. (This is not gloating-- as I am wholly aware that this mark will plummet after I encounter what is next to come. Guaranteed. This becomes more obvious as this post goes on.) However, I live in perpetual fear that I will be discovered to be a "fraud". I am impossibly bad at math, and it is a constant, pulsatile reminder; that I am attending a university revered for it's difficulty, in a faculty renowned for its focus on computation, mathematics, and logic. Today, a post on the UofT Computer Science FB page further perpetuated this fear. To hear that the difficulty of Computer Science rises disproportionately each year was a shock in and of itself. A friend at Waterloo's program had said that he had found his first few years in Computer Science to be the most difficult. Whether or not the difficulty of the program increases as the years progress, regardless of my weaknesses in math, I will continue to press on -- to learn more about the things that I am passionate about. Life is a continuous struggle to reach the goals we set for ourselves. I am finally learning things that I am passionate about. Although I am at a disadvantage in terms of my learning background, and the years that I have had away from my math, I am confident that I am well versed in the art of Try-Harding. I spent so much time being disinterested in the things that I-did-not-want-to-do, that my second time around in a post-secondary institution has been all about spending all of my time studying-the-things-that-i-want-to-do. Even so, I ultimately decided to drop MAT223 this semester. This is the first time in my academic career that I have ever dropped a course. My first true encounter with failure. However, it made me realize that my desire to do well, and my efforts to do well, were not entirely realistic. Majoring in a field completely void of the mathematics, and working in a hospital for a year and a half is not conducive to writing algebraic proofs. We're not in Kansas anymore. It's time to start from square one in terms of math. To learn from the beginning, and to learn it well. At first, I was ashamed. Now? I am determined.

It is currently 3 AM. Further updates will be made this week as I pursue the dread mathematical proofs and the big-Oh(my god).