Sorting And Efficiency

If I were given a list of numbers from 1-10, in mixed order, what could I do with the list?

For one, I could sort it if I had nothing better to do. I would easily skim through the list until I found the smallest number, and place that in the far left side of the list.

[10, 4, 2, 3, 9, 8, 1, 5, 6, 7] would become [1, 10, 4, 2, 3, 9, 8, 5, 6, 7]

I could sort this entire list in mere seconds and not give it anymore thought, moving on with more important things in my life such as procrastination. But I were to find myself given another list, this time with numbers ranging from 1-1000000, would I even bother to sort it?

If I had dedicated more attention for the previous list, would that have helped in sorting a list, especially with a large range of numbers?

It turns out it would, and I could determine whether sorting a list of a million numbers would be worth the extra 3% on my final grade, or taking that time to studying for the upcoming exam.

Almost at the end of the first iteration
of sorting a list of a million elements,
Timmy decides he should probably start studying
 for his exam tomorrow instead.

In order to sort the list posted above, I took the smallest number and moved it to the far left, then moved everything else one to the right.

Sorting the list this way, I'd have to check every element, find the smallest, move it to the left, then shift everything else to the right.

Once I discovered that it takes approximately n² steps to sort the list using my method, and each step takes me ¼ seconds to process, a list with 10 elements would take me 25 seconds to sort.

With a list of a million elements, it would take me approximately 7927 years. Good thing we have computers and good thing there are more efficient sorting methods.

Finally, time to earn that 3% in CSC148.

"It's helpful to see how an algorithm's run-time grows."

Big O, big omega, big theta, all of which can be utilized to model the run-time of code, showing just how long it would take to complete for any size input.

But is it really helpful? I'm just over here with my simple list shifting numbers to one side, also mixed up in all of this recursion and trees and linked lists and more trees.

Or the greater question, is this the stepping stone? Can I no longer mindlessly crunch blocks of if-statements? Is it no longer appropriate to write if some_variable == True?

I think I'm starting to get the picture, the slightest taste of the realm of computer science and it's not fun and games like I thought it would be. There is great potential to be found within, not just for self accomplishment and not just to secure a job at some start-up company, but to propel advancement, and our capability to evolve as a civilization.

Coming across the problem P=NP, it really demonstrates how much computer science is interconnected with contemporary society. Soon we'll be able to figure out what is worth researching, how fast we can make discoveries, and by then robots will have taken most if not all of our jobs.

Recursion

The definition of recursion (from Google) is as follows: the repeated application of a recursive procedure or definition.

That doesn't explain too much, so what is it exactly, and what is its purpose? Is it something that provides us with another means to insult our peers?

While some may choose the path of impertinence, the role recursion plays in the world of coding is quite significant, almost vital to the entire process.

It is something that can be written in a simple line of code, yet capable of complex output. Who would have ever thought to call a function inside a function? Someone who probably didn't want to repeat several blocks of code. So then is recursion the product of laziness and apathy? Absolutely not. It is in fact, fundamental to computer science, providing a powerful means to control algorithms and approaches the possibility of self-automation robots similar to the ones in the film I, Robot. Just imagine what would happen if a computer possessed the potential to solve all of its own problems.

Since a recursive function calls upon itself infinitely many times, they require a 'base case', where the code is able to step out from a never-ending loop.

In this instance, the base case lies within "else x". Without the base case, the function would execute repeatedly, until eventually the program ran out of memory.

It's similar to two mirrors facing one another, and without a base case, you'd end up with infinite reflections reaching to the point where they become so minuscule, they are no longer visible.

At some point, you would need to step out.

It is interesting to ponder if the base case itself was a recursive function, for a recursive function defined within another recursive function. Being able to manipulate the concept of infinity is something far more sophisticated than making a 'yo mama' joke, but tracing recursion and trying to figure out how to implement it can often be difficult. Sometimes we just need to step back and crack a joke to realize what we were aiming for all along.

An Introduction to Object Oriented Programming

When talking about programming, terms and definitions can get quickly overwhelming, especially if you're a first year student studying at UofT. I've always heard people discussing these topics that even today, still scramble my head. Just hearing the words subclass, module, or encapsulation, are enough to make me nod my head, and pretend everything is fine as the lecture continues. After much fiddling with simple loops, functions, and if-statements the previous semester, I wonder, what's the ultimate objective of programming? For money? For problem-solving leisure?

[Let this creepy stock image represent my
dismay during the CSC 108 assignments]

Well it turns out there's a greater truth that lies beneath all of the books and online slides. It's called Object-Oriented Programming. In the simplest terms, its a way to manipulate organized information. A slightly more rigorous definition would be a type of programming that allows organized information to be perceived as an object. An object can contain attributes (descriptions of the object), it can carry out procedures (instructions for a task), and it can also establish connections with other objects (sharing attributes and procedures).

 A bare example of an object in Python looks like:

[A simple class in Python]

And I thought, wow neat! Actually I didn't, I lied and I don't think anyone else would have said the former. If they did, kudos to them for having the motivation. When I'd first seen a class in Python, it sort of just brushed by and I never gave it much thought. But as the lectures started to reveal more and more of what they were capable of, it got me thinking--we call it an object, although it's something we can't hold in our hand. It is purely conceptual, intangible. It's similar to when we say, a hydrogen atom, yet you'd never think of holding a hydrogen atom in the palm of your hand. But it too, is an object, much like anything else in the world.

Actually, the idea of object-oriented programming is applicable to the the entire universe. If we view the universe as a very-very large program, the idea of object-oriented programming applies. A quark, an elementary particle, can be an object and inherit from a hadron, another object that inherits from say, a proton, also an object which inherits from an atom, then to a molecule, and so on until it eventually reaches you, a person an object, then to a planet, and to a galaxy and it goes on, all inheriting from the few fundamental superclasses, chemistry, physics, and biology. However, the universe is much more complex than the internet browsers we run on our computers.

While it's cool to think about, the question still stands, what is the point of object-oriented programming? Sure it can be about the money if that's what you're aiming for, or would it be more convenient and efficient to use when trying to solve a problem, but I like to think of it simply as another dimension in programming. Whereas procedural programming is sort of like a 2D plane, object-oriented programming is 3D, it opens our minds to completely new directions. It can be utilized whether you want to make business apps for clients, or design a gaming engine, or a mine a few bitcoins, the ultimate goal of OOP is to allow of these things, and help technology advance to a future with endless possibilities.