Time Complexity

The concept of time complexity was covered a few weeks ago. However, I did not want to record anything of it until I deeply understand the concept properly. Time Complexity is an quantifier of time taken of an algorithm. This is mostly used by the computer scientist to create the most efficient computer program. The chapter started with an example of recursive binary search. My first intuition about this algorithm was much focused into the code rather than the bigger picture. I had hard time to understand the lecture because I was trying to understand the code while my professor was looking at the bigger picture. From this, I learn that the detail about the codes do not really matter much in terms of time complexity. I have to look at the bigger picture where the recursion is happening and the condition of the recursion. For example, in this recursive binary search example, we assume that the array is sorted. We check the upper half recursively if the array at mid point is greater than a target. We check the bottom half recursively if the array at mid point is smaller or equal to the target. No matter how long the stopping point, the time complexity of a stopping point is one in general because only one or two lines are being executed. In order to find the big oh, the worst case, we take the maximum of the recursive functions. The maximum will return the most time taken to achieve the target given an array size.

Second thing I learned from this chapter is unwinding. Unwinding is expending or rewriting a recursive algorithm until it can be expressed as a closed form. Usually, the unwinding happens until number of steps reach the size of the input, n. The algorithm is usually simplified to a closed form, an expression in finite number rather than a recursive algorithm. When I tried the unwinding the first time, I kept expending until I found a pattern. However, this was a mistake. It is much crucial to expend to a a simplified form. For example, unwinding a Fibonacci sequence can generate a pattern of pascal's triangle;

F(n) = F(n-1) + F(n-2)

        = F(n-2) + 2F(n-3) + F(n-4)

        = F(n-3) + 3F(n-4) + 3F(n-5) + F(n-6)

        ....

It is true that there is a pattern but the pattern can hardly be implied to a closed form. Therefore, the following unwinding would be much easier to handle closed form;

F(n) = F(n-1) + F(n-2)

       = 2F(n-2) + F(n-3)

       = 3F(n-3) + 2F(n-4)

       = 5F(n-4) + 3F(n-5)

                 ....

At nth step, the first unwinding is so huge that it would be hard to compute. On the other hand, the 2nd unwinding has just two terms so it is much easier.

From this, I learn that sometimes finding a pattern is not really it. I have to think if this can be implied to a closed form. If it is impossible, I have to go back and find another pattern.

Term Test One Evaluation

After the Friday's lecture, the class had their term test one papers back. The term test consists of three questions.
The first question was about using a mathematical induction to prove a statement. The question was very similar to the tutorial question so the proving was extremely simple to write out. However, I lost a mark for not stating P(n). I thought that P(n) is basically the research question so I did not state the P(n) for this question. Unfortunately, the thought was wrong. I was right that P(n) is not equal to the research question but  P(n) comes from the research question. It was a basic mistake but taking off a mark out of 5 is too much. I admit that I deserve a mark deduction but losing 20% of a question is too much for a question when the question is about proving. From now on, I write out my P(n) before proving anything even though it is so obvious from the question.
The second question was about proving that a non-empty binary tree at height n has at most 2 to the power of n - 1. Like the first question, it was dealt during a tutorial so writing out a proof was an easy part. However, I lost another mark from stating P(n). For this time, I stated P(n) but I restricted the domain of the P(n). At first, I couldn't accept this deduction because the domain I stated is correct anyways. I asked my professor and the answer I got from him was kind of ambiguous to me. He first mentioned that I should never restrict the domain of P(n) because the domain is restricted later stating the P(n). However, logically, restricting twice, inside of P(n) and outside of P(n), does not change the statement. It would be inefficient but the statement would still be correct anyways. Second, he told me that a statement 'for a positive integer n' is equal to 'for all positive integer n' in this course so stating more than one 'n's is wrong. I still  could not understand this because 'a' and 'all' are different in the first place and we are not learning a so-called 'new English' for proofs. I think this is one thing that I need to accept anyways even though it does not really come to my mind because it is like a rule in order to show a proof. I will make this sure in my mind and never make this mistake again.
The third question was about the structural proof. I knew that it was in the midterm topics but did not expect this to come out because we did not have any tutorials dealt with this proof. Unfortunately, we had this proof and I got a bad mark on this one. For the next midterm and the final, I will cover everything that is in the topic list.

Post Term Test

On October 10 Wednesday, there was a term test for the CSC236 morning class. In order to prepare for it, I reviewed all the lecture notes and read through the course textbook. The term test covered mathematical induction, complete induction, well-ordering induction, and structural induction.
For the mathematical induction, its proof was extremely straight forward. From my point of view, mathematical induction proves a minimum case and proves the next number over and over. This implies to all the natural numbers starting from a base case. This type of induction did not surprise me at all because the concept was very simple. I found difficulty when it came to finding the base case. Not all questions start with zero. In this case, I was to find the base case. However, I found very difficult to find if the base case is really the base case. Throughout some trials, I realized that I can find a base case using inequality. Then, I should also try numbers below them until the case fails because sometimes the base case found by the inequality is not the real base case. From this, I learned that it is best to try out the real examples rather than reading a textbook to realize how the proofs work.
One disadvantage of using the mathematical induction is that you cannot use its induction if 'n' is not sequential natural numbers. This flaw could be overcome by Complete Induction. Complete Induction proves a statement by testing the previous cases and use a further step to prove that its P(n) is true. In the first place, I found very hard time understanding the concept of the Complete Induction. I wondered how the previous case work for the current cased. In this logic every case should work if and only if the base case work. After reviewing some tutorial notes, I realized that it was not just about proving the base case. It was about proving the previous case and apply that previous case to the current case by stating another statement to one previous case. I think the concept would have been a lot easier if the lecture slide describes the concept much specifically. From this trouble, I learned that I should never rely on the lecture slides all the time because the slides are extremely summarized so sometimes it misses key concepts.
Well ordering states that there is a smallest element if P(n) is true. It was a very obvious concept but it was too obvious to apply to the proof. For the well-ordering, all I learned is that we need to prove a statement  by contradiction. I wish there was a tutorial just for this so I can learn from the examples. It was very disappointing that we did not have a tutorial for this concept.
I learned structural proof and read the textbook. However, I still do not understand this concept. I tried to  understand the lecture examples and online examples, but its concept did not come to my mind. I think I will have to stop by an office hours so I can at least understand this concept. From this chapter, I learned that I need to take advantage of office hours if there are concepts that I do not understand.

First Challenge, Assignment 1 Q1

The reading of the assignment started last night. I like to read assignment questions before I go to bed because if I keep thinking about the questions I eventually bring them into my dreams and solve a portion of them. Apparently that did not work quite well this time. I rather had a nightmare and woke up with a bad mood. I reread the questions and  the understanding was not quite as hard.

The first question was about a ternary tree. Throughout my life, I never dealt with ternary tree. Ternary tree refers to a tree which one parent node may have up to three children. Since I had a knowledge about binary tree, understanding this concept was quite easy. This question was quite difficult because I tried to approach in a way that I learned in the csc236 lecture. It did not work out. At this point, I realized that even though two questions look similar approaching to their proof might be different. I made some scratch notes and figured out that using inequalities and some definitions, the problem could be solved. From this question, I learned that a shortcut (e.g. two problems that look similar could be solved in a same way) does not work sometimes when it comes to proving. Next time, I will try to approach different ways before I take the shortcut.

I will do one question per day, so tomorrow I will be doing question number two.