The Final Blog

What a semester it has been!  CSC165 has actually changed the way I think about problems.  I never knew how to properly prove something before this course.  From the very introductions in logic to computability I feel I have a much better understanding of how to think in the computer world.  Logic helped me decipher complex statements in a computer program, big O helped me understand how to analyze the efficiency of a computer program, and computability helped me realize the limitations of computers.  I look forward to this courses older brother, CSC236.  Good luck on the exam everyone!

The Halting Problem

This week I am going to be talking about the halting problem, its definitely an interesting problem.  For anyone struggling with what it is trying to say, they should try using youtube.  I have found it a great resource for all of my courses really.  Computerphile and Numberphile are great channels to subscribe to.  They are filled with loads of interesting information.  For example Numberphile does a great infinite prime proofs.  They essentially do the proof by contradiction by saying that if there were a finite amount of primes they could be expressed in a list.  However if you took all the elements in that list, multiplied them together and added 1 you would get another prime, that isn't included in the list.  Hence there must be an infinite amount of primes.

The most amazing thing about the halting problem was that is was discovered before modern computers even existed.  Alan Turing was an absolutely brilliant mathematician and it is such a shame what happened to him.  He truly is the father of theoretical computer science.  I guess the halting problem also indirectly proves that through careful analysis results can be concluded even if there is no physical capability to test them.  Theoretical physicists everywhere should rejoice.  I heard my TA in my lab Monday tell an interesting story about how in the 1950's a software company noticed it was spending a lot of time debugging code and was trying to determine whether there was a program that could automatically debug code for them.  It turns out this is essentially the same as the halting problem and cannot be done.

In my simplest explanation of the halting problem I can say this:

To begin with assume that halt works.

Have 1 function composed of 3 functions.  One arbitrary function at the top, the halt function, and then a negation function that if halt returns true will get stuck and if halt returns false will return true.  Now try and feed the function into itself.

Case 1
So if the arbitrary function doesn't halt, halt will return false and the negation will return true.
Case 2
If the arbitrary function does halt, halt will return true, but then the negation function will get stuck in an infinite loop.

Therefore halting implies the function doesn't halt, and not halting implies the function does halt, which is a contradiction.

I am trying to explain what can be found in this video:
https://www.youtube.com/watch?v=92WHN-pAFCs

There are still a few hazy details for me, but I think that is a good explanation.  Hopefully there are no typos.

Fall Break

This past week we have continued to expand our knowledge of big O and big Theta.  The proofs do not seem very hard when you think about what is actually happening.  I find it very useful when Danny makes a diagram showing what the proof is actually trying to say because after all understanding what you are trying to prove is the most fundamental step.  The way I think about big O is that it is the most practical way to compare the efficiency of algorithms.  It is more about categories than being precise.  Since larger exponents overpower smaller ones by such a large amount, regardless of the constants, it is all that you really have to look at.  This fact can be seen in other places of mathematics as well such as evaluating limits going to infinity.  I think the truly hard task would be calculating the average efficiency of algorithms, I am not even sure how it would be done.  In fact my TA told our class that there are a few professors at U of T who have devoted their entire careers to studying average efficiency.  Stealing from some of the ideas of business you know that the overhead or fixed cost would stay constant, its just a question of how you would calculate the total variable costs.  Perhaps we will learn more about this in CSC236.

Week 9 - Calculus Problem

Greeting Again!  This week I have a special treat!  I will write up my problem solving episode with the last question from my calculus exam.  To be honest I didn't get perfect on it because I completely forgot how to eliminate factorials, but I did get 7/8.  Not a bad result considering most people probably got close to 0 because it was marked strictly.

Question:

Understanding the Problem:
Goal: Take the 35th derivative of this function.
Input: Function
Process: Differentiation, but there must be a pattern to recognize due to time constraints.
Output: Function, by inspection I suspect the 35th derivative will involve factorials because the exponent on some of the x variables is 35 if you were to expand the numerator.

Devise A Plan:
First I will begin by simplifying the expression as much as possible, and putting it in a format that will make it easy to differentiate.  I will start by expanding the denominator and seeing if it can be simplified.  Ideally I will eliminate the division because differentiating + or - is much easier than x or /, but worst case I will rewrite the fraction as a product and rewrite the denominator as a term to a negative exponent.  From this point I will try to collect like terms if possible.

Once I have the original function simplified as much as possible I will begin to differentiate.  It is guaranteed that there is a pattern given time constraints.  Also I remember similar examples from class that used this pattern technique.  I will keep taking derivatives until I recognize said pattern, and then apply the pattern to figure out the 35th derivative.  At this point I will have solved the question.

Executing the Plan:

Once I got to the final line in step 1 I knew the function was simple enough to begin differentiating.  The first derivative helped me solve the last two terms of the 35th derivative because I knew the x raised to the power 35 would just end up equaling 35! because the power decreased once per differentiation.  Furthermore I knew the x raised to the power 34 would be 0 because the 34th derivative of this would be constant, so when you differentiated again it would be 0.  I took the second derivative to help me figure out how to solve the first term.  Because the exponent was negative it would get more and more negative each differentiation.  Also the term in from of (x+3) would alternate between negative and positive, being negative on odd differentiations and positive on even differentiations.  Since 35 is odd I knew that it must be negative.  Finally I knew the number at the front would have some sort of factorial, but not go all the way down to 1 because it started at 3.  So in order to eliminate the x2x1 you divide by 2!.

Looking Back
The key to questions like this really is to not lose your cool.  Any type of problem like this has to have some pattern in differentiation and their has to be a trick to simplifying the function.  I could check the result by taking all 35 derivatives manually, but this is too time consuming especially for a test.  I do not think this question could have been done any differently given time constraints; using the product or quotient rule would have made it way to complicated.

Week 8 - Another Proof Example

I have took some time this morning to read over a few blogs, and it seems like most people have been making good progress, even though there are a lot of "dead" blogs out there.  Most people seem to have found week 3 very tough and the beginning of proofs very difficult.  These things do seem very intimidating when you are first learning them.  Also  as a side note I haven't been naming my blogs with the week number in the title, I hope this isn't a problem.  Today I am going to be doing tutorial 6 question 4.  Funny enough when I was actually doing this tutorial I didn't even know that there was a question 4, I just looked at the first page.  When we took this one up it was a long one, so I will try and recreate it now:

Proof Example

Greetings I am back!  Finally a week without a midterm!  I only have the assignment for this course and a linear algebra problem set to do this week, this is practically a week off at U of T.  Do you want to know something scary?  One of my friends has yet to write any blog posts, and I am not even sure if he has set up blogger!  Yikes!  In this post I will be writing a nice proof of our quiz 5 question.  Last week I did not attend my usual tutorial time because of a time conflict so I got the chance to see another TA do proofs.  I can say that for the most part both TA's did proofs the same, but there were a few subtle differences.  Anyway, without further ado:

I answered this a bit differently on the quiz by leaving the j variable blank at first and then setting it after I had solved, but I think this way is cleaner and more logical.  I have noticed that I am pretty good at algebraic proofs like this one, but still have some trouble with epsilon delta style proofs.  Another proof is incoming this week! Until then!

Busy Week

This is going to have to be a very short post because I am in the middle of studying for calculus and linear algebra midterms that are back to back over the next two days, and I also have a Jewish culture essay due Wednesday.  I just want to say that I really like the way U of T marks in computer science courses because it appears that they truly want to give you credit if you have shown you know something.  I feel like in calculus they are actively trying to find ways to take marks away, for example generally the last question on the calculus midterm is out of 8 and it has a disclaimer that it is marked very strictly and unless you have the correct solution you will receive little to no marks.  Also I like the concept that if you really don't know a question you can skip it and write that you cannot answer it to prevent you from spending too much time on questions you don't know.