Week 12 - Hope the course is not in infinity.

    This course is finally coming to an end, not to infinity. Yet the complexity just don't seem to be ending. Introducing this week, is the extension of countable sets and 1 to 1 counting. The week started out decent as the course goes over how countable list are listable. Which I interpret as basically the same thing.  --->

*From my perspective, its pairing elements from a same size set with each other. 

However, the course material gets dirty when Cantor comes into the play. His existence and his proof made my life miserable. Simply, by modifying the numbers in the set by the diagonal, he constantly creates new number and overflow the natural numbers if one tries to match the two.    
However, his tricky technique confused me at first grasp. I wondered how that will differ from natural numbers, since I can do that to a natural number as well. I am just extending the digits in a different direction. Nevertheless, this mindless assumption was quickly put away as I realized that natural numbers can't lead by 0 and it easily result in duplication of numbers. 

Moving on from Cantor, 
Induction is introduced. 
*Well, with MAT135, I cringed

This is something that is completely new to me. However with the amount knowledge in CSC165, it was not too bad of experience. The principle of induction was easy to understand until using it in a real battle. 

As soon as professor Heap put up the problem, I died a little inside. 

Facing this beast, I didn't really know where to start off. I fall back to the principle of induction. In order to prove the claim. I first need to assume that P(n) is true and show that P(n) leads to P(n + 1). Through the guidance of professor Heap, the question turns out to be "slaughtable" with some thinking. 

At last,  formal week of the semester ended in induction.  Cheers
Now comes the exams. 
My opinion towards the exam. 
http://vickieou.blogspot.ca/2014/11/csc165-slog-week-12.html#comment-form

Week 11 - Halt !! Confused again !!

Little did I know that this course will confuse me from the beginning until the end of the semester; it gives me no breathing room to fully understand the different concepts. This week, while I felt a lot confident in my proof techniques and understanding of the Big Oh and Big Omega, I was hit hard in the face by the Halt problem. 

In this concluding week of the course, the course limited computer science by introducing the idea that not all the problem in the world can be solved by algorithm. I struggled to accept this reality for a long time until the example popped up. 

The code in the example measures if  an particular input will cause the algorithm to halt. When I first encountered, I didn't fully anticipate the running time. Therefore, I though it was going to work as expected. Nevertheless, with a longer running time, it is almost impossible to anticipate the result due to the vacuously distinguishing of whether the program is running for ever or halt eventually. 

It all seems reasonable at first, until naval gaze come in. 

It was impossible for me to grasp the idea of navel_gaze with a weak background in programming and coding (only taking CSC108 currently). Particularly when H halts, and how that will effect navel_gaze ; with function in side a function, it twisted inside my mind.  In order to fully understand the definition of navel_gaze, I had to draw out the map of the two function and trace the different input. It took forever to finally to work out that navel_gaze is uncomputable. However, I believe it was definitely worth the time since now I have a better understanding in this material.

*This slog also helped me in grasping the idea of halt. The description is quite logical. 
http://165slog.blogspot.ca/2014/11/week-11.html

The uncomputable program introduces a new technique in proof: reduction. The new technique allows me to prove that many other programs are also uncomputable. The technique is much easier to grasp once I understood the idea behind the halt function. The proving technique uses the fact that one program is uncomputable implies that another program is also uncomputable. Such technique is simple yet powerful in depicting the limit of algorithms. 

The reality that explain this phenomenon was more fascinating. In math, I knew there was always a different between the different infinities. However, I never quite dig into the truth that makes them different. The halting problem also introduces one to one counting. For different sets of infinities, there could be one to too many resulting the phenomenon of the halting problem. This is another point where I struggled during the week, trying to figure out the different sets of infinities : from natural numbers to rational numbers. 

Overall it was a week of hectic. 

Week 10 - That GPA getting limited.

    After two weeks of dreadful weeks of Big Oh's,  the nightmare continues. This week starts off by continuing on the negations of the Big oh.  The problems were not to tackle since they are always based on polynomials. As result, simply by checking the biggest power on the variable in a polynomial, will lead one to the right path in proofing; rather than spending precious time in thinking whether to prove or disprove.

    
For instance, 

    
                          claim:     n^3 not in O(3n^2) 

    

    From first glance, it is obvious that n^3 will not be bounded by 3n^2 since it is obvious that n^3 will grow much quicker than n^2, and the 3 multiplier can be ignore as it will not matter too much as the numbers grows toward infinity.  

    
    To prove the claim, simply prove the negation of that n^3 is in big O of 3n^2 by choosing a breakpoint, by which n^3 will grows bigger than 3n^2.

    Through the weeks,  a new problem was introduced. The problem abruptly increases the complexity in proving Big oh. The problem is to prove a claim that compares two functions that is beyond polynomials. Therefore, it includes other functions like 2^n. 
     Well, for each new enemy, there is always a new weapon. Time to bring out the new weapon: the limit technique. The mechanics allow me to tackle the enemy in a completely new way. 
     
Taking this claim as an example:
                                 
                                     2^n is not in O(n^2)
    

    To approach the problem, I first express the claim as an limit that as n goes to infinity 2^n/ n^2. By using L.Hopital's rule, The limit evaluates to infinity. Then I am safe to state that if I choose an nc to defeat the c that the enemy hands me and defeat the problem.
     In addition to the week, I struggled upon the introduction of Big Omega. It differs only letter from Big oh as it allows me to choose a breakpoint -B- in which allow the claim to be true. However, that big difference took a way a large chunk of time. To fully understand the concept of the Big omega and its difference with Big oh, I used graphing calculators to interpret different graphs. It definitely helped as I can visualize the easier function and understand how Big omega is applied to it. 

Week 9 - The Big oh continues.

After a week in the introduction of the big-Oh, things starting to get sort out. In week 9,  we started with the counting step of the algorithm. It gets confusing at first with the different variables and loops. However, with more practise and blank staring, it gets easier.

*I had to admit, even with CSC108, I struggle in doing the general counting of steps that involves n and i. 

 Regardless, the addition loops always make the algorithm more complex and more time consuming.  I also noticed that with the increase of inner loops in an algorithm, the number of steps also increases exponentially. However, with loops on the outside, the steps remain linear and no where close to a exponential growth. 

Taking this code from the lecture as example, 

The inner loops make the steps for the worst case increase from a single power n to a second power n^2. It consumes more time and result in higher complexity. Moreover, it also takes more organizing skills to sort and analyze the algorithm. 

In addition to this week, I learned to prove that some function is within the big-Oh of another function. The introduction of Big Oh allows me to check whether a function will lead beyond upper bound. It is sometimes challenging to imagine the different graphs to visualize whether a function will be trapped under another. As a result, it helps me in understanding how different run times and functions interact with each other. It also allows for optimizing the run time for an algorithm by solving the Big oh proofs. 

The proof structure of the problems are quite similar to the proof that was done earlier. Moreover, I consider them to be easier than the once that were proved before since mostly they involve around polynomials which mostly is done by modifying the powers of the 
variables and the comparison. 

Interestingly, I found a slog that expresses a similar feelings towards the introductions of Big Oh. 
http://mengjiayan.blogspot.ca/2014/11/csc165h1-week9.html#comment-form

Overall, the week were sunk in abundant of examples of proofs.

Week 8 - Counting steps, worst case, and Big Os

    This was a fresh week that introduced new topics - algorithms.  The word scares me. I always imagined them to be some high level magic that will solve every problem in existence. I see them being used in stock markets, Amazon, and even in worst ever TCC. 

The introduction class definitely opened up my views on the functions I wrote in CSC108 class, adding a more analytical view to the mechanical typing. It is fascinating to see how each of functions I wrote is a algorithm its own that solves a problem. 

Moreover, in this class I learned that algorithms range from all possible of complexity. In this weeks class we worked on a simple algorithm that does a linear search. Through the example, we learned analyzing the algorithm; finding the steps it take to complete a search. However, the loops throws me off as I need to consider how it react through in the worst condition. To counter the problem, I wrote out a simpler loop and traced the steps and used different outputs. I quickly understood the concept.

It is quite unique that we have to always consider the worst case. It is the one that consumes the most time. By the end of the week there was also the introduction the idea of Big Os. It is the maximum time to go through the algorithm in the worst time possible. It also bounds the maximum and minimum steps. 

Not too bad a week.