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

Week 8

In the lectures of this week, we expanded bit more on the analysis and proof of worst cases. Also, the second term test would happen next week on Wednesday on proofs of various claims. I would be preparing for it by redoing some examples that we did in lectures and also the past test from last year.

Next, on previous week, we mentioned briefly about why we as computer scientists cared about worst speed. This week, we expanded a bit more on proving worst cases.

First of all, we started with linear search.

 

In the example above, we tried to find the running time of this code by counting steps. We wanted to idealize time of counting the number of steps for a given input. 

Worst Case - Upper Bound and Lower Bound:

 

Upper Bound and Lower bound of a program:

1. tp(x) stood for the time that required to count the steps of the program.

2. C stood for a constant value.

3. B stood for a break point (what we used to determine whether the tp(x) was upper bounded or not. 

U(n) = n^2 because 

U = n, so n(n) = n^2

Therefore,  we could conclude that tp(x) was upper bounded by cn^2 and tp(x) was also lower bounded by cn^2. 

In conclusion, we now knew that:

Big Oh(n^2) meant the set of functions that would grow no faster than n^2

Big Omega(n^2) meant the set of functions that would grow no slower than n^2 

When set of functions that were in both upper bound and lower bound, then we ended up having Big Theta(n^2), which it meant the set of functions grew as fast as n^2

Week 7

This week, I finally understood materials that I didn't fully understand from last week under the helps of my tutor. I learned about sorting, worst case, upper bound, and lower bound. I knew that as a programer, I want to find the worst case/speed of a program. Upper bound meant the case that can't be any worse than it. Lower bound meant the case that was the least worst. That's being said if the shorter the running time of a program was, meaning that more efficient the program was for computer (device) to run; therefore, a better performance. Moreover, the running time depended on how long the program required to count all of its steps. Furthermore, an example of worst case complexity graph was shown below.

The function y = x  represented the given input of the program.
The function y = logx + 1 represented the lower bound (at least as bad) of the program (least time consuming)
The function y = x^3 + x^2 - 1 represented the upper bound (can't get any worse) of the program (most time consuming)

 

 Additionally, we mentioned introduction rules, insertion sort, and selection sort.

We found that steps required for insertion sort and selection sort on list of size n were no more than some quadratic functions of n. All quadratic formulas were varied from substantial constant factors, but we as computer scientists didn't care because all quadratic formulas were the "same" - they were all in O(n^2). 

**** Big Oh stood for upper case and Big Omega stood for lower case ****

Week 6

This week, we talked about proving, non-Boolean functions, disproving a claim, and how to prove different claims.

Non - Boolean functions:
The definition of non-boolean function meant the way it sounded, functions that didn't return true of false as results. Moreover, we are introduced with a new symbol, which was the "floor x" as it was shown below.

 

As  it was shown above,  floor x must be the largest integer that was equaled or less than x, which was same as saying that floor x represents the smallest integer that was less than or equal (<=) to x.

For example, in the lecture during the week, we did various examples of simple proofs that involved floor x in the given definition and the claim. 

Given definition: 

Prove:

We proved the claim step by step by using the given definition (there are various ways of proving a claim):

 

Most of the time, we were asked to prove a claim true with a given definition, but there were occasions when we were asked to prove a claim false. This meant that we would have to "negate" the claim then prove the negation was true, and by doing this, we disproved the original claim.

Next, when proving claims that contained:

1. Conjunction (and) 

2. Disjunction (Or)

Then we would have to prove the claim by breaking the claim into different cases. 

In the following example, we were asked to prove the claim where all n that belong to natural numbers such that n^2 plus n is even. 

Week 5

This week, I reviewed materials that we covered from the beginning of September until now. I studied and tried to understand better on the various topics and concepts that I needed for the term test. I believed I did most of the questions correctly (maybe?). The test was not really complicated, but it did require some thinking and logics to do well in it. Last, but not least, ENJOY YOUR THANKSGIVING BREAK!

Week 4

This week, materials were getting harder and more complicated. 

The following topics were introduced in the past week: Bi-implications, transitivity, double quantifiers, and intro to proofs.

For bi-implication, that's say we had the statement of P <=> Q, which it was equivalent to the following statement: (P => Q) and (Q => P), then we could transform this bi-implication into a conjunction between two disjunctions and a disjunction between two conjunctions, which was shown as the following: 

P <=> Q was equivalent to (P => Q) ∧ (Q =>P).

I applied the distributive law, then I got (¬P ∨ Q) ∧ (¬Q ∨ P) <=>  [(¬ P ∨ Q) ∧ ¬ Q] ∨ [( ¬ P ∨ Q) ∧ P] 

I applied the distributive law again, then I got [(¬ P ∧ ¬ Q) ∨ (Q ∧ ¬ Q)] ∨ [( ¬ P ∧ P) ∨ (Q ∧ P)]

Next, according to the identity law, P ∨ (Q ∧ ¬Q) <=> P which was equivalent to Q ∨ (P ∧ ¬P) <=> Q. 

Then  I  got  [(¬ P ∧ ¬ Q) ∨ (Q ∧ ¬ Q)] ∨ [( ¬ P ∧ P) ∨ (Q ∧ P)] <=> Q ∨ (P ∧ ¬P) 

Finally, by applying distributive law again, I got the result of  [(¬ P ∧ ¬ Q) ∨ (Q ∧ ¬ Q)] ∨ [( ¬ P ∧ P) ∨ (Q ∧ P)] <=> ( ¬ P ∧ Q) ∨ (Q ∧ P). 

Transitivity was simply a description of a relationship between elements in the statement/expression. For example in the following implication:

If A implies B and B implies C, then A implies C too.

This statement could be proved to be true through contradiction. 

If A implies B and B implies C and A doesn't imply C. 

Statement above causes a contradiction;therefore, transitivity is always true. 

As for double quantifiers, we talked about how we could claim that a certain subset of cartesian product ( for example M*M) was not empty. Moreover,  we also talked about ways to prove that entire cartesian product got to have some property.

Lastly,  professor heap briefly talked about the steps and format of proof. He also came up with a discussion about the importance of assumptions and indentations.

Example of proof from the lecture:

Week 3

In week 3, we came to the end of the beginning stage of this course where we were actually going to dig deeper into the realm of logics. Also, this was the week when the assignment 1 was assigned. At first, I thought the assignment was going to be difficult because I had not gotten all concepts and ideas from the previous lectures; however, I was lucky that I was able to work in groups with my friend who knew the materials much better than I did. Anyway, we went through the assignment and various materials together. It was really helpful for me because not only I was working on the assignment, but I also got to review some critical terminologies and concepts. Nevertheless, we were stuck on the last question because we could not find a better way explaining either statement #1 was implied by the statement #2 or implied statement #2. It was unfortunate that we couldn't make it to the office hours to ask professor heap for a better way explaining our answers due to some private reasons, but we were still quite positive that our answers were good enough to earn full marks.

Moreover, we learned about various laws: commutative, associative, distributive, and De Morgan's law.

I knew these laws were important because I will need to know them enable to identify my steps as I went through questions that wanted me to prove either two statements were equivalent or not. 

For example: 

(P ⇒ Q) is equivalent to [(P ∧ (¬Q)) ⇒ (¬P )]

• ⇐⇒  ¬(P∧(¬Q))∨(¬P)  --> Implication 
• ⇐⇒  (¬P∨¬(¬Q))∨(¬P) -->De Morgan's 
• ⇐⇒  (¬P∨Q))∨(¬P) --> Double negation 
• ⇐⇒  (¬P ∨¬P))∨Q --> associative and commutative 
• ⇐⇒  ¬P∨Q --> idempotency
• ⇐⇒  P⇒Q --> implication 

Week 2

In week 2, we learned about negation, disjunction, conjunction, intersection, contrapositive, implication, converse, and vacuous truth. 

I understood that implication was simply a statement: If P then Q, which P was the antecedent and Q was the consequent. Reading from left to right, this is one way/ direction. In converse/ other direction, the implication worked also because both P and Q were consistent. In inverse/contrapositive, the implication P => Q then became ~Q => ~P (~ is an alternative symbol of negation symbol)

For example:

Statement: If I walk around, then I am bored. (=>)
Converse: If I'm bored, then I walk around. (<=)
Contrapositive/Inverse: If I'm not walking around, then I'm not bored. (adding "not")

Moreover, vacuous truth simply meant that if we had an implication and there was no counterexample then it was true (no matter how ridiculous the implication statement was). 

For example: 

"If the sky turns red tomorrow then I will be the tallest man in the world."  (thanks to vacuous truth. This is true because there is no counterexample to this statement.)

Week 1

At the first few lectures of first week of CSC165, I had to admit that I was kind of lost, not only because my native language WAS not english, but also because my brain couldn't get the logics that professor mentioned in lectures. I tried catching up and understanding different terminologies such as some, not some, all, not all, any, not any, counter example, qualifiers, universal claim(∀), existence claims(∃), and many others. By the end of first week, I found myself starting to understand the materials progressively as I was able to connect some topics from CSC165 to what I learned in CSC108.

For example: 

def q0(S1,S2):
    return not all{x in S2 for x in S1}

Here are some notes that I took in various lectures and tutorial:

"Some" means at least one or more.
"Not Some" can mean all or none (nothing).
"All" means everything.
"Not All" means anything more than 0.

any({...}) returns True if the set has one or more True elements

all ({...}) returns True if the set has True elements

I understood there were various methods that would help me when I drew venn diagrams.

All False -- > give one solution (counterexample)

All True --> give all solutions to prove the function 

Some False--> give all solutions to prove the function

Some True --> give one counterexample 

While drawing venn diagrams (four regions in total):

Cross - "X" means this region must be empty. 

Circle -"O" means this region must be occupied. 

Emptiness - "    " means this region doesn't matter.