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.