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.  

Midterm Experience

I am extremely frustrated this week!  I did not get question 3 correct after spending half of the exam working on it!  Within the first two minutes of starting the question I thought I solved it with two sets that were the same for P and Q, but I didn't explicitly tie it together with D and then I ended up changing my answer.  From this point I tried everything I could think of from two empty sets, one empty set, two different sets etc.  However again I came under the syndrome I talked about in my previous blog post, the more I thought about the question the more confused I made myself and the further from the answer I got.  It ended up becoming a mad scramble with the last 10 minutes being a blur and then me scribbling down an answer.  I may have been better off just writing "I cannot solve this question", but there is no going back now, live and learn.  Unfortunately spending all that time on question 3 also prevented me from checking questions 1 and 2 over, which should have been a priority because I answered them quick.  Next test I am going to do a much better cost benefit analysis of marks vs time.

After reading several of the blogs for this week it is clear that everyone is discussing proof format and generally they are terrified to actually begin proving things.  I have to admit I am somewhat in that category as well, but that is not what I was going to mention in this blog.  Several people are discussing the format, but not including any comments in their work.  Comments are very important and should not be forgotten!  Remember beside your assumptions and introductions you should have those #'s!  (ie. domain assumption, antecedent etc)  That is all I have to say for now,  good luck this week to everyone in CSC148!

So Begins the Midterms

It's time for another weekly blog post, sandwiched nicely between a linearly algebra assignment and calculus review.  I had a great tutorial last week that cleared up a lot of the issues that I was having.  For example one of the biggest issues being how to tackle statements that involved many sets.  I was previously trying to think about what was going on intuitively, to picture it in a Venn diagram or use a truth table.  However the issue with this is that Venn diagrams become too complex to draw, truth tables become rather large and thinking about things intuitively just won't work when you are dealing with many sets.  It all just clicked for me when my TA said that you should understand the arithmetic rules with two sets but once you add more it is impossible to think about things intuitively so you should just apply the rules.  Although I somewhat figured as much through problem solving, hearing this cleared my head and made me feel like I understood how to tackle large statements with many sets.

I have to agree with Andy L (http://andylslog165.blogspot.ca/) when he says that he almost certainly would not be able to do an Epsilon Delta proof without previously seeing one in calculus.  I think that Professor Heap did a good job explaining what the statement was saying when he said if e is chosen first by your worst enemy you can find a d to make the statement true, however if d were chosen first your opponent could easily disprove it with an e.  The only problem is I wouldn't naturally draw a connection between the statement and limits, so I wouldn't prove it that way.  Although seeing as the term test is this week after heavy review I may feel differently.

Me and my partner both found that while doing assignment 1 the more we continuously talked about a question without taking a break the further from the answer we got.  For example we had thought we figured out 5d by thinking about which statement was the subset, and at the time thought statement d included 0 so S2 must be the subset.  In the end with fresh eyes we realized that 0 wouldn't be a part of statement d because it is divisible by odd prime numbers so both statements implied the same sets when all possible values of T were considered.  So it was S2 if and only if statement d.  We are using this as a lesson to take breaks while thinking about questions in the future.

Week 3

This week the material has definitely been more challenging than the previous two weeks.  I am still wrapping my head around how to implement a lot of the symbols correctly, so it has been difficult to fully understand lecture this week.  I did not get the quiz question correct, but I learned a lot in the tutorial and from my mistakes, so I am not very concerned about it.  My answers to the questions in the exercise before the tutorial were not very well developed, but redoing the questions after my answers were much better syntactically and semantically.  I was previously falling victim to doing things like x>1 when referring to a prerequisite, thinking that it meant there was more than one prerequisite when in fact it means nothing at all.

By taking mathematical expression at the same time as calculus and linear algebra, I am seeing a lot of overlap in the principles of mathematical writing.  However, mathematical expression has taken this subject much further than the other two courses mentioned which gives me a great background when writing in symbols for them.  Another benefit is mathematical expression gets you used to interpreting math notation which is very common in my linear algebra and calculus textbooks.

To practice this weekend I am going to work through proving that the arithmetic laws that can be transferred to logic are in fact true.  I found it very useful when Professor Heap was using Venn diagrams in his explanations, so I will try to devise the proofs in the same way.  As well I intend to start the assignment.

Logic Problems

On the first weekend of this semester I enjoyed going through the logic problems in chapter 1 of the course notes, although some of them I found quite frustrating.  The first problem that I came across was the infamous Monty Hall problem renamed 3 Boxes in the course notes.  It is my understanding that when this problem was first presented even PhD's in mathematics could not agree on a solution.  My reasoning behind the solution is that if you had a higher chance of selecting an empty door on your first choice, then it is more likely the game show host has shown you the location of the other empty door, thus giving you free probability.  Therefore you should switch doors.  It certainly isn't an entirely new problem with new parameters when the host shows you the empty door as some people have suggested, and running computer simulations confirm this.  The next problem that I chose to tackle was the 2 Labelled Boxes Surprise.

Solution:
The problem provides the reader with two explanations that appear to be foolproof yet don't yield the correct solution.  They almost form a mental block when you are trying to reason your way through the problem on your own because you are constantly thinking back to them.  The first step you must take in solving this problem is realizing that the box labelled "the prize is not here" must be true in order to have not been lied to.  From here I reverse engineered a solution that will mean the boxes have not lied to you.  The solution that I came up with is that the box that says "exactly one statement on the boxes is false" is in fact a false statement because both statements are true.  This box being true because the statement itself is false, it is circular reasoning, but it is what I came up with.  This solution is before I have learned all the techniques taught in 165 so it may not be a perfect explanation or even correct.  Does anyone else have a better explanation?

The course work up to the end of the second week hasn't been very difficult, for me it is mostly just a matter of learning all of the terminology.  This weekend I am going to make a conscious effort to review notation because it has been a while since I have taken a formal math course.  Having written the GMAT and scoring very well I am used to logic problems to some degree.  Although most of the logic problems on the GMAT just related to whether a solution could be obtained with statements presented and not what the actual answers were.  So this course will take my logic abilities further.