CSC165 Lecture Week 12

So this is my last SLOG. I wish I could say that I'm sad, but I'm really not.

I actually really liked assignment 3. I finally understand what the point of all those limit proofs were. For the limit of a function as x goes to infinity, if that limit is infinity, then the output of the function can be larger than any given number past a certain breakpoint for the input. For the limit of a function as x goes to infinity, if that limit equals to zero, then the output of the function can be smaller than any given number after a certain breakpoint for the input.

The zero limit also really helped in my understanding of infinity. No matter how small a number I can think of between 0 and 1, there will always be a real number that is smaller than the number I've come up with. I'm also glad, I finally managed actually apply the limits and derivatives that I have spent the past year and a half learning.

After reading some other SLOGs, I've found a couple that have good summaries of computability, which I think was the hardest of the topics that we covered:
http://fromatothis.blogspot.ca/
http://mrbunnyua.blogspot.ca/

CSC165 Lecture Week 10/11

This is technically just for lecture week 10, since we won't be having a lecture week 11 for the Tuesday evening class, but anyway, onto the SLOG.

This week in lecture we learned about computability. First let's talk about a few definitions. A function is considered to halt when it eventually stops. For some functions we can write a function halt(f, n) that can tell us whether or not the passed function f will halt with the given input n, but we cannot write a universal halt(f, n) function for all possible inputs.

A function is well defined if and only if we can tell what the output is for every input in some domain. A function is computable if and only if it is well-defined and we know how to compute the output for every input in some domain. By these definitions halt(f, n) is non-computable.

We can prove that a function is non-computable by using reductions. If a function, f, can be implemented by using another function g, that function reduces to g. If g is computable, f is also computable and by the contrapositive, if f is non computable, g is also non computable.  

CSC165 Lecture Week 9

This is my problem solving session. I will be attempting to solve the Free Lunch problem on the problem solving wiki.

Understand the Problem

You are part of a group of friends who choose which to treat to lunch in the following manner:

1.    They arrange themselves in an (approximate) circle.

2.    They begin reciting the positive natural numbers, in order, in a counter-clockwise direction (viewed from above), starting with the friend at the northern extreme of the circle (who utters "one").

3.    As a friend utters an even number, he or she is eliminated from the counting (and consideration for lunch). The counting "wraps around" so that those who avoided one of the dreaded even numbers on the first round may be exposed on subsequent rounds.

4.    The last person left is treated to lunc.

For example, if there are friends f1, f2, f3, f4, and f5 arranged counter-clockwise, with f1 at the northern extreme, the first round would eliminate f2 and f4. Then f1 and f5 would be eliminated in the next round, leaving f3 to enjoy the free lunch.

If there are n friends, where should you position yourself to get the free lunch? Do you have a technique that will work for any positive natural number n?

This picture helps illustrate the problem. Basically, you don't want to ever say an even number.

Devise a Plan 

Go through the first couple of natural n by hand and see if a patter emerges.

Carry out the Plan

n	Iterations	winner
1	F1	F1
2	F1 f2	F1
3	F1 f2 f3 F1 f3	F3
4	F1 f2 f3 f4 F1 f3	F1
5	F1 f2 f3 f4 f5 F1 f3 f5	F3
6	F1 f2 f3 f4 f5 f6 F1 f3 f5 F1 f5	F5
7	F1 f2 f3 f4 f5 f6 f7 F1 f3 f5 f7 F3 f5	F5
8	F1 f2 f3 f4 f5 f6 f7 f8 F1 f3 f5 f7 F1 f5	F1
9	F1 f2 f3 f4 f5 f6 f7 f8 f9 F1 f3 f5 f7 f9 F3 f7	F3
10	F1 f2 f3 f4 f5 f6 f7 f8 f9 f10 F1 f3 f5 f7 f9 F1 f5 f9 F1 f9	F1
11	F1 f2 f3 f4 f5 f6  f7 f8 f9 f10 f11 F1 f3 f5 f7 f9 f11 F3 f7 f11 F3 f11	F3
12	F1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 F1 f3 f5 f7 f9 f11 F1 f5 f9 F1 f9	F1

Initial observations:

It’s pretty obvious that you don’t want to be an even numbered friend. F1 wins all of the even numbered n except for 6. (Realized that I made an error once I looked back)

Look Back
An obvious pattern has not revealed itself. I will take a look at another possible source of a patter: what number each of the people say.

n	Iterations	winner
1	F1 1	F1
2	F1 f2 1    2	F1
3	F1 f2 f3 F1 f3 4    5	F3
4	F1 f2 f3 f4 F1 f3 5    6	F1
5	F1 f2 f3 f4 f5 F1 f3 f5  6   7   8	F3
6	F1 f2 f3 f4 f5 f6 F1 f3 f5 7    8   9 F1 f5 10 11	F5
7	F1 f2 f3 f4 f5 f6 f7 F1 f3 f5 f7 8    9  10 11 F3 f7 12 13	F7
8	F1 f2 f3 f4 f5 f6 f7 f8 F1 f3 f5 f7 9   10 11 12 F1 f5 13 14	F1
9	F1 f2 f3 f4 f5 f6 f7 f8 f9 F1 f3   f5  f7 f9 10 11 12 13 14 F3 f7 15 16	F3
10	F1 f2 f3 f4 f5 f6 f7 f8 f9 f10 F1 f3   f5  f7  f9 11 12 13 14 15 F1  f5  f9 16 17 18 F1 f9 19 20	F1
11	F1 f2 f3 f4 f5 f6  f7 f8 f9 f10 f11 F1  f3  f5  f7 f9 f11 12 13 14 15 16 17 F3 f7 f11 18 19 20 F3 f11 21 22	F3
12	F1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 F1  f3  f5 f7  f9  f11 13 14 15 16 17 18 F1  f5  f9 19 20 21 F1 f9 22 23	F9

Initial observations:

I actually made one error in finding out who won, so I should really double check my work.

Winner	1	2	3	1	3	5	7	1	3	1	3	9
# said to win	1	1	5	5	7	11	13	13	15	19	21	23

Look Back

Still no obvious pattern. I am out of ideas at this point, and will continue on later and look for more complex patterns.

CSC165 Lecture Week 8

This week the most interesting things that we learned was how to count steps and analyze algorithms. I now know that nesting loops is inefficient. Insertion sort with one nested loop has a worst case time complexity of O(n^2). A maximum slice algorithm with three nested loops has a worst case time complexity of O(n^3). Nesting loops greatly increases the number of steps needed to do something.

I also found it really interesting that for upper bounds you can overestimate them because they're upper bounds. A function is upper bounded by another if it grows no faster than that other function, so if that function happens to grow a lot faster, it doesn't matter because it is still an upper bound. Also, you can underestimate them because they are lower bounds. A function is lower bounded by another function if that other function grows slower than the first one. If the other function grows a lot slower it also doesn't matter because it is still a lower bound.

CSC165 Lecture Week 7

I have always wondered what something like O(nlogn) meant after my brief foray into reading about sorting algorithms on Wikipedia. Now I know. O() is the notation for asymptotic upper bound. Efficiency is very important in computer programming. Computing time takes up money and resources. Asymptotic notation allows us to analyze the efficiency of functions.

When we say running time, we don't actually mean running time. We mean the the number of steps (lines of code) that need to be executed in order to run a function. With asymptotic upper bound, we focus on the worst case scenario. So if you are searching for an something in the list, the worst case scenario is when that thing does not appear in the list at all. This would require the largest number of lines to be run. As well with asymptotic notion, we do not care about constant terms, and only the highest order term matters. So everything from n^2 to n^2 + 3n + 4 to 109352543n^2 + n + 43243 all belong in O(n^2).

CSC165 Lecture Week 6

This week I learned how to prove a statement about a non-boolean function, how to disprove something and how to prove a limit.

    For non-boolean functions, the most important thing for you to do is write down the definition of the function in a logical way. The definition will be used in the proof and it is much easier to use if you have a clear logical statement. To actually figure out the path to the proof, you should try to change the statement to match something in the definitions of the function.

    It seems pretty simple to disprove a statement. All you have to do is prove the negation of the statement. It is of course often easier said than done. You still have to prove some statement. To disprove a universal quantifier, the negation is an existential quantifier, so a single example is needed to disprove it. To disprove an existential quantifier, the negation is a universal quantifier, so you need to prove the negation by using some generic element of the sets in question.

   I am actually still having some trouble with limits. I've have four midterms this past week, but now that they are over I plan to spend some time practicing limit proofs and looking at some more examples. I get the basic gist of a limit statement.

If epsilon is picked first, there has to be a delta for which the implication holds true. I still am a bit confused as to how you are supposed to find a delta in relation to epsilon for which the implication is true. Once again, I'm probably just going to have to practice, practice, practice.

CSC165 Lecture Week 5

I had my first ever university midterm this past week and I think I did well. What really surprised me about this midterm was how easy it was for me to understand the questions. I remember that during my first lecture we were given a Python function that read something like this:

def q0 (s1, s2)

               return all ([x not in s2 for x in s1])

It was so confusing at first. I did have some previous programming experience before taking this class, and I just could not understand how you could write a line like this in Python. If I wrote this in Java or Turing like I’ve been taught previously, it would take many more lines.

               Something similar was on the midterm and now, I can just read that as a simple logical statement. If we define S(x) to mean that x is an element of s2, that line of code can be written as:

for all x in s1, not S(x).

It is much easier for me to evaluate this simple logical statement. I am now starting to see why this course is required for computer science.

CSC165 Lecture Week 4

This week’s lecture has me extremely worried. We started on proofs, and we were given two examples in class. I understand the basic structure of proofs, but they still honestly look like magic to me.

Assume some condition
    Assume P(x)
       Then R(x)
       Then R2(x)
        …
        Then Rn(x)
        Then Q(x)
     Then P(x) implies Q(x)
Then P(x) implies Q(x) for some condition

This basic proof structure, for the most part, makes sense to me. I can see that we are simply just linking two statements together in a neat and organized manner. It's the actual proofs that really stump me. It's like having to learn trig identities all over again, only it's even worse this time. There were only so many trigonometric identities to choose from. Now I have to choose from what seems like every theorem to ever exist in mathematics. I just find it really difficult to jump from one thought to another.

I eventually did learn how to prove trig identities and now I'm actually pretty good at them. That came with pages and pages of practice, so I guess I'm just going to have to practice, practice, practice.

CSC165 Lecture Week 3

I was always told that university would come with a lot of new challenges, and I think I faced my first one this week. In high school I grasped most topics very quickly and very easily. The only thing I really struggled with were proofs in math, but we didn't have to know them for tests, so I am ashamed to say that I pretty much just ignored them. Now that I actually have to learn this stuff, I have to figure out how to approach these problems. The tutorial exercise for this week took me two hours to do and I had to have a lot of outside help. Hopefully, in the future I will get better at this kind of problem solving.

Question 2 from the tutorial:

To help me solve answer this question, I first went to the CS help centre. I got two bits of information that helped me. First the x on the left and within each set of brackets is not necessarily the same x, but they could be the same x. I also figured out from looking at the online notes that (a) and (b) are actually laws and they are called quantifier distributive laws.

I then Googled quantifier distributive laws to see if I could get a different perspective that would help me. This website http://goose.ycp.edu/~dbabcock/PastCourses/mat235/lecture/lecture06.html, gave me concrete definitions of the predicates, which helped me to finally solve the problems. Let D be the set of people. Let P(x) mean x likes pie and Q(x) mean x likes cake.

Three things to keep in mind:
1. An implication can only be proven false if the antecedent is true while the consequent is false.
2. Or (V) is true when one statement is true and false when both statements are false.
3. And (^) is true when both statements are true and false when one statement is false.

And now my answers to the questions:
(a) is true in both directions. Translating it into English makes it obvious. Everybody likes pie and cake, therefore everybody likes pie and everybody likes cake. Everybody likes pie and everybody likes cake, therefore everybody likes pie and cake.

(b) is always true from left to right. When someone likes cake and pie (proving the right true), that same someone likes pie and that same someone likes cakes, so the left cannot be false. The other way however is sometimes false. Let's say person A likes pie and person B likes cake (proving the left true). There does not have to exist a single person C who like both (proving the left false). The antecedent can therefore be proven true when the consequent is false.

(c) is always true from right to left. Everyone likes pie (proving the left true), therefore everyone likes pie (proving the right true). The other way is false because everyone likes pie or cakes could mean that, for example, half of everyone likes pie while the other half only like cake (proving the right true), therefore there may exist some person A who does not like pie and some person B who does not like cake (proving the left false).

(d) is true in both directions. It's the same as saying: someone likes pie/cake therefore someone likes pie/cake, which makes both sides true.

These are, of course, not formal proofs and I can't Google around for answers on assignments and test, but I'm hoping that this was a decent first step. I learned some new strategies for understanding problems (rewording into something I understand, coming up with concrete examples) so I'm getting better at this.

Now I shall move onto my next challenge of learning to do laundry because I cannot take it home this weekend.

CSC165 Lecture Weeks 1 and 2

This is my first post for CSC165, so just a quick housekeeping note. This used to be a physics blog for physics class, but from this point forward all posts will be dedicated to CSC165.

Learning about mathematical expression and reasoning or logic is pretty much the same as learning a new language. Instead of learning new words we are leaning new symbols such as ∀ for universal quantification and ∃ for existential quantification. Instead of learning grammar, we are learning new, more precise ways to interpret the English language. Surprisingly, I am actually really enjoying this course, which is odd since I hated those years where I was forced to learn French.

The first week’s topic was very intuitive for me. Universal quantifiers like ‘all’ and ‘every’ can only be proven by looking at every element in the set, and can be disproven by one counter example. Existential quantifies like ‘some’ and ‘there exists’ can be proven by one example and disproven only by looking at all the elements of a set. I think this duality is really elegant and really makes sense in everyday English.

On the other hand, the topic from the past two weeks that I have found most interesting is the vacuous truth and it seems very counter intuitive. It’s pretty weird to think that a statement such as, ‘If the sun does not rise, then pigs will fly’, is true. In everyday English, this whole sentence is absurd. None of these things will ever happen, so it would seem as if this sentence where completely false. Although, once I think about it, the fact that this statement is true starts to make a lot more sense. If P, then Q implications can only be proven false if there is an example where P is true but Q is false. In the case of the statement above, P is never true, so this statement can never be proven false, and is therefore true. I really like how precisely this the rules for implication are defined. It definitely trips me up sometimes, but I do often find everyday English to be too loose and ambiguous, so maybe that’s why I’m liking this course.