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.