It's Been a Fun Year!

CSC148 is coming to a close end. It's been fun. Tons of ups and downs; a rollercoaster of a ride.

Personally, I really enjoyed this course. It gave us (my fellow students and I) a great feeling for complexity. Prior to this class, I felt like I was in elementary school learning addition. This class felt more like the beginning of university.

On the downside, while I did want the course to be challenging, there were lots of dumb mistake I made here and there. Unfortunately, CSC148 isn't exactly that easy 4.0GPA CSC108 was. But that's no big deal; computer science is fun no matter what.

With that being said, CSC148 was probably my favourite course so far and I can't wait to see what future CS courses are like!

A Fresh Start

When I tried the first LinkedList lab, I found it quite difficult. I had no idea how to even design the new query. My trouble wasn't helped by the fire alarm nor the fact I (nor my partner) saw the hints. I sat there, with my lab partner, for the whole lab, typing random nonsense to no avail.

Surprisingly, when I tried the LinkedList lab next week, I knew exactly what to do--kinda. I'm still not entirely sure if we implemented it the way Dan wanted (we didn't keep an index of the older/newest items), but we implemented it nonetheless.

I'm not sure why it was so much easier the second time (it's not like I was thinking about it outside the lab), but it was. It's great to see what a nice long break and fresh start can do.

List Comprehension...

Yesterday's practical was great! I went in there, not knowing anything about list comprehensions, and leaving with a--good--understanding of them.

While it wasn't necessary to entirely understand list comprehensions to finish the lab, it was useful. The lab encouraged me (and my lab partner) to read the (lecture?) slides about list comprehension, filter, and any. Had it not been for this lab, I probably would have finished CSC148 without knowing how comfortably use list comprehension.

Thanks to this lab, I can now use list comprehensions, filter, and any in future projects. They, admittedly, make life a lot easier.

Now, you may be wondering, why did the chicken cross the road? I have no idea. But hey, why not check out my lab partners SLOG? He's kinda a cool guy...sort of...maybe.

Euclidean Algorithm - The Recursive Way

Last week I posted about various forms of the Euclidean Algorithm. This week, what with recursion being a topic in CSC148, I thought I'll implement the subtraction method using recursion (division next week).

First, just to quickly restate, Euclidean Algorithm tells us that, if x > y then gcd(x, y) = gcd(x - y, y). In class we implemented this using an iterative method (involving loops, etc.). Here is how we could implement it recursively:

def gcd(x, y):
    if x == 0:
        return y
    elif y = 0:
        return x
    elif x > y:
        return gcd(x - y, y)
    elif y > x:
        return gcd(x, y - x)

Quick explanation of code: You can probably guess why the first two if's are there; they're there because gcd(x, 0) = x and gcd(0, y) = y. But what about the last two if statements? Well we know if x > y then gcd(x, y) = gcd(x - y, y), thus we can evaluate and return this simplified expression. In the process of evaluating it, it may have to evaluate a further simplified gcd. It will keep doing this until one of the expressions contains a parameter that equals 0; when the function can return a value to the previous function.

Okay, that last paragraph was a mouthful; hopefully everyone understood what I was trying to say. If not, feel free to ask in the comments!

Euclidean Algorithm - Subtraction vs Division

Just a quick recap first: On Friday's lecture (January 10th) we utilized Euclidean algorithm. As mentioned in the class, the basic principle of said algorithm is that the GCD(Greatest Common Divisor) of two unique positive numbers is the same as the GCD of the greater number minus the lesser and the lesser number. For example, GCD(10,9) = GCD(10 - 9 = 1, 9). This means one can find the GCD of two unique positive numbers by continuously subtracting the lesser number from the greater until they are equal; once they are equal you know the GCD (since the GCD of x and x is x).

For those of you who took Mathematical Proofs(MAT102), you will remember Euclidean's algorithm being slightly different. In MAT102, the main principle was that the GCD of two numbers in the same as the GCD of the remainder (when dividing the greater number by the lesser) and the lesser number. You can thus work it down to when the remainder becomes 0 and thus determine the GCD (the now lesser number).

Interestingly, the method used in MAT102 is more efficient. As proven by Gabriel Lamé in 1844, it will never take more iterations than five times the number of digits. This means it will take a maximum of 15 iterations to determine GCD(100, 1) while the prior method would take 100 iterations.

I'm not entirely sure why Euclidean subtraction seemsto be used more in CS (in the CSC108 textbook and CSC148 lecture), but I thought the difference was rather interesting. If someone wants to shed some light on why the prior algorithm appears dominant, I'd be more than happy to know in the comments. My best guess is the prior one is simpler to understand and that neither CSC108 or 148 are math-oriented courses.

Important Information Pertaining to This SLOG

This SLOG is a duplication from Google+ (https://plus.google.com/113418820623626814392/posts). While posts are visible on both, comments will only be read if they are posted on the Google+ version of each post. 

There are various reasons for doing this, including but not limited to:

• ensuring posts won't "disappear",
• verification of this Google+ page, and
• another service in case a viewer finds Google+ hard to use.

Note: This post is different from its Google+ counter-part. This is the only post that will be different.