Comments

Comments:

http://anadamnjanovic.blogspot.ca/  ---- Week 9

(I really like the way you carried out the contents and material of the week. It really helped me understanding the material better and solve my problems. Moreover,  your blog was very well organized and easy to follow. )

http://ace165.blogspot.ca/  ---- Week 12
I believe you are missing one more mapping, which is correspondance.
Correspondance is the mapping both onto and 1 - 1, meaning no extra values in either set X or set Y.

http://165slogs.blogspot.ca/ --Week 12 (Diagonal)
I was not able to come up with the solution to this worksheet with my partner, we tried drawing some lines and few other methods, but somehow we just can't figure it out. By looking at your solution and explanation, I have finally understood what we were missing and what we had done incorrectly. I appreciate your solution because it really helped me understanding each step of solving this problem.


http://vickieou.blogspot.ca/ -- Week 12
I totally understand your anxiety because I am also experiencing the stress of the upcoming final for this course. In fact, I have been struggling with proofs and logical thinking until I really tried more problems, spent more times thinking, and got supports from my tutor. Moreover, it is critical for you to manage your time wisely. Wish you luck on your final. (I really need some luck too).

Week 7 Worksheet - penny piles

We did a worksheet called "penny piles."

Here was the condition: You are sitting in front of two drawers. The left drawer contains 64 pennies, the right drawer contains nothing. Can you arrange things so that one of the drawers has 48 pennies, using combinations of the following two operations, l and r? 

l : If the left drawer has an even number of pennies, you may transfer half of them to the right drawer. If the left drawer has an odd number of pennies, operation l is disallowed. 

r: If the right drawer has an even number of pennies, you may transfer half of them to the left drawer the right drawer has an odd number of pennies, operation r is disallowed.

Choose another number in the range [0, 64]. 

Starting from the same initial position, can you arrange things so that one of the drawers has that number of pennies?

I started with [0,64] then I divided 64 by 2 then we had 32 and 32, so 64 became 32 and we added 32 to 0. As the result, we had [32,32]. We repeated the process again and again until we had number 1 (i.e: 1, 63)

Are there any numbers in that range that are impossible to achieve?

We could have any number from 0 to 64 because we were given the range [0,64]. From my solution, as it was shown below,  all the numbers from 0 to 64 were covered and achieved.

What about starting with a different number of pennies in the left drawer?

By starting with a different number of pennies in the left drawer, we would receive the same result.

My solution to this worksheet: 

Course Reflection

After three months of hard working in CSC165, I am almost done with this course. I have came a long way since the beginning of September. I am going to say that this course is quite difficult to master. The materials in this course were something that I had never seen before the first lecture of CSC165. I find this course quite challenging because the fact that this course does involved some math techniques, but not entirely like mathematics really annoyed me sometimes. Moreover, I also found the examples and contents in the slideshows given by professor heap were messy and abstract. I believe it is possible for professor heap to simplify the contents of the slideshows even more. My personal experience is that I often found myself lost in his lectures because I didn't have enough time to really understand the content of the slide before he moved on to the next one. However, there were still benefits for me taking this course, by taking this course, not only that I began to learn thinking logically, but also improved my ability to comprehend and analyze various problems.

Furthermore, often I found myself not understanding the materials then I asked for help from my T.A Jason. I frequently asked him questions after the tutorial sections, which he spent extra ten, fifteen minutes explaining the materials, which I really appreciated. 

Week 12

This week was the last week of this course; therefore we covered last thing that was covered in this course.
This week's topics:

1. Explanation of the reason why rational numbers are countable/listable
2. Cantor's example
3. Diagonization
4. Induction

First of all, the term countable is same as the meaning of listable, which then we call this correspondence ( 1 - 1 and onto in one case). 

Next, rational numbers are countable, meaning there is a correspondance. As it is shown below:

For first row in the picture, we listed both positive and negative numbers of the same integer, once we did that then we incremented the integer by one, then repeated the process. For the rest of the rows, as you can see, they are fractions then we incremented the numerators by one the same way we did in the first row. 

As we went down the columns, we incremented individual denominator by one. 

As the result, we assumed that all the numbers listed, then this was the proof of rational numbers were countable. (there were no overlapping combinations of value from set X and value from set Y). 

Following, Cantor's example proved that all real numbers were non - countable. This example basically showed us that the reason why all real numbers were non-countable was simply because the different sizes of infinite. In Cantor's example, we tried mapping all real numbers to natural numbers, which we all knew both sets of numbers were infinite; however, there were always numbers that were greater than the size of the set (amount of numbers) that we assumed at the first place. Therefore, it was impossible for us to prove all real numbers were countable because infinite didn't equal to infinite (in this case; infinite could occasionally equal to infinite, but it varied on different cases) This concept was tricky and it really made struggled a little bit. I am glad I have figured it out eventually.

Moreover, we were also introduced to the idea that there were total of 256 characters in UTF-8 (python was written in UTF-8), all characters could be translated in to different numbers or combinations of numbers. By saying that, it meant each python function was unique and these python functions were countable.

Next, we were given an example of halt and loop behaviours as it was shown in the picture below:

In this case, we interpreted halts as the number 0 and loops as the number 1. The output of the behaviour of different inputting functions was either halts or loops (only two options). As we tried to list all the possible outputs, we realized it was impossible for us to do so because this halt and loop example was non-countable because there were more infinite behaviours than python functions. 

Last but not least, we learned the last new topic in this course, which it was induction. 

We started with the principle of induction as it was shown in the picture below.

We supposed P(n) as a predicate/boolean function of the natural numbers. 

If P started out true, such as P(0) and the truth of P transfers from each number to the next, which this could be written down in one expression. . This showed us that P was true for all natural numbers. However,  could be false. 

In the four tables below, we found one table that violated the expression. The third table (counting from left) violated the expression because when n = 1 and P(n) was true; therefore,  when n = 2 and P(n) should be true. Next, many of us believed that the fourth one violated the expression too; however, in fact this table was true. During the lecture, I thought this was false because I believed when n = 1 and P(n) = false then when n =2 and P(n) should be false (they should be consistent). 

Basically, the reason why fourth table was true was because we could choose a number (variable: k in this case) and used it as a restriction of the inout numbers. The expression that made the fourth table true :. Therefore, we believed P is true for all natural numbers when n was greater or equaled to k. 

Next, we did some induction examples, which we came up with the following steps to solve general induction problems. 

Step 1: Write base case(s) & prove they are true 

Step 2: Assume P(n) is true (Inductive Hypothesis)

Step 3: Show that P(n+1) is true, then transform one side of the equation so that you can use the Inductive Hypothesis to solve the problem.

Week 11

We finished the topics of proving and disproving Big Oh, Big Omega, and Big Theta from last week.

This week's contents:

1. Algorithm  
2. Some terminologies (new vocabularies) 
3. Reduction 
4. Infinite does not always equal to Infinite
5. 1 - 1 and onto 
6. Countable

First of all, most of us interested in computer because we want to solve problems in a systematic and logic ways. Enable for our devices to implement our solutions/programs, it will need algorithm to perform the tasks. Algorithm is defined as sequences of executable steps. Alan Turing,  a British computer scientist, who was widely known for his concepts of algorithms and computations, invented the first general purpose computer model which is called Turing machine. Moreover, Turing came up with the proof that there would be uncomputable problems  on any reasonable computing models/devices. In modern times, we realized that even using different modern programming languages, such as Python, C++, Java, and etc., to implement the problems would not work.

Secondly, we learned some new terminologies from following example.

 

Computable: a program/problem that can be solved by algorithms. 

Noncomputable: a program/problem that can't be solve by algorithms. 

Following, reduction was introduced. Let's start with an example: assume I know function f is non-computable, but I was given well defined function g. What I can do next is to extend (by adding some extra executable steps) the function g then build function f, which this step can be shown as an implication ( g computable => f computable). Next, we say f reduces to g, using the rule of contrapositive (not P => not Q), which we have f non computable => g non computable.

Next,  infinite does not always equal to infinite. Here's the reason why,  sets A and B have infinitely many items if they each have more items than any finite number. However, having more than any number isn’t the same as saying they have the same size as each other.  Basically, it means two sets (either finite or infinite) have the same size (same amount of numbers /items). By matching them up(by counting) in two ways ( 1 - 1 and onto). 

Furthermore, 1 - 1 and onto are terms that we use when we describe a function. 

In  1 - 1, it simply means that no two elements in x are mapped to the same element in y. 

On the other hand,  the term onto means when every element in y is covered (even if there is/are extra value(s) in set X. Additionally, there is also an occasion which we call correspondance when onto and 1 - 1 both exist in the case.  

Lastly, we were introduced with Cantor's diagonal proof, commonly known as diagonization. By doing a diagonal proof, it allowed us to know the fact that not all sets are countable. All rational numbers are countable. All real numbers are not countable. (More details were introduced in week 12).

Week 9

This week nothing new was taught really because we did our term test on Wednesday, which I believed I did quite poorly on it... (need to work harder)

Anyway, due to the test, so we spent this week on proving and disproving more Big Oh, Big Omega, Big The Theta examples/statements,  just so we could get more familiar with methods to solve these type of questions and also memorizing the individual definition of Big Oh, Big Omega, and Big Theta.

Week 10

This week we ended the topic about analyzing bounding a sort and linear search. We focused on proving the worst cases (both upper bounds and lower bounds). More importantly, I have finally understood how to analyze (finding steps) of codes during the tutorial section with Jason.

Following picture was an example that we did in tutorial section:

Furthermore, we did some proof exercises:
During the lecture, we were given an example of big Oh. 

In this case, n^2 was the function.
f : N -> R^>=0 : the function that takes in a natural number and return a non-negative real number.
The rest of the function basically told us that n^2 or f(n) was upperbounded by cn^2 (beyond the breaking point B).

Next, we learned to disprove this Big Oh example by negating it then proving it true.
So the negation of n^3 <= c3n^2 to n >= B and n^3 > c3n^2.
We chose a value for n, but before that we have some logical steps to write down.
We broke n^3 down into n times n^2. Since n^3 > c3n^2, then we could comment that n > 3c so n^3 > c3n^2 was true. Now, we introduced ceiling. Ceiling was a symbol that had the opposite meaning of floor. When we used floor, for example, floor 3.249 ( a random number I picked) then we got the answer of 3 because floor meant the largest integer that was less than or equaled to x. On the other hand,  ceiling 3.249 then we got the result of 4 because ceiling meant that we rounded up the number in the first digit by 1. Therefore,  we came up with the result that n >= ceiling 3c + 1 and n > 3c at the same time. Then we got n >= B and n^3 > c3n^2.

In addition, Big Omega was introduced, which we were given with this example.

As you could noticed, this example was very similar to the Big Oh example. There were two differences, first one was that we changed the symbol of Big Oh (O) to the symbol of Big Omega (Ω) and second one was that we changed from ≤ to ≥ between f(n) and c(function - differed in different cases)

Following, we were introduced with a new bound, which it only happened when the functions were bounded above and below by the same function. 

 

In this case, we combined two concepts into 

 

Last,but not least we were introduced how to prove a non-polynomial example.

General procedure of solving: 

1. Prove the limit of using some rules we learned in calculus. For example, L' Hospital Rule 

2. Translate the limit into its definition with c and n' 

 

3. Relate this definition to the definition of Big-Oh.

then we got