Sorting and Efficiency

Why is sorting a huge deal in computer programming, one may ask. Let’s make an analogy that would make much sense:

You enter your room, and it’s a mess. Like a complete mess: clothes on the desk, laptop in the closet, mouse in your backpack which is under the bed, your bedsheets are in a box and you don’t even know why and etc. Oh and wow, in 40 minutes your date will come over, so you have to clean up your room completely and at the same time, you don’t want to stink. So you have to organize your cleanup in a such way so you would be able to clean your room completely and be able to take a shower. Here comes different approaches which would result in different amount of time that would need to clean up your room. So basically, you need to finish within 40 minutes and still save enough time to be able to take a shower. You think of different ways of cleaning up your room: first collect all clothes from everywhere and fold them vs break your room into squares and clean every single square one by one… (I do not even want to ask you to assume that your room is 100 times bigger than usual and the mess is also multiplied. I just do not want you to feel bad)

The same thing is with the sorting algorithms. They all work in different ways and achieve different results in time consumption.

There are different sorting algorithms (which include insertion, merge, bubble, quick and etc.) each of them take different amount of time because of the algorithm’s way of working. If there are a lot of loops,m that would keep checking every single item in the list, the time basically would get bigger (really simplified version of explanation of complexity).

So, what is big-Oh. Big-O basically is a way of comparing algorithms in their way of working in time consumption. Saying that an algorithm is in O(n^2), means that depended on the input n, the time that it will take to make the algorithm work will grow exponentially, which is undesirable. On the other hand, saying that an algorithm is in O(logn) means the time will grow only logarithmically, which is pretty acceptable.

The main reason of simplifying algorithms in terms of time, is to find another algorithm with would give the same result but in a reduced time.

I think it is almost the best way to explain complexities and sorts and unfortunately it is my last sLOG post. To be honest, i was a bit skeptic about this blog, but it was pretty fun writing stuff and explaining all what i learned to myself again and again and i’m hoping i will be able to make use of this knowledge sometime in the near future.

Assignment 2, part 2

In spite of the workload of this week, somehow, I was able to manage to finish the assignment within one day and submit it before the deadline. However I wouldn’t say that the assignment was confusing. It just had too many special cases which I had to consider, which pretty much made me to spend more time than i was supposed to. Every single time I had to make up new tests and see whether or not my code works. I’m guessing this assignment was more focused on making right test cases just to test the code, so we could learn a proper way of debugging. I’d say there were a lot of loops where you did not expect them to be bundled with all those if/else statements. Unfortunately my code looked ugly in the end, because i did not enough time to make it prettier. However i am pretty happy that i was able to make it work (well at least for the cases that i made up). Desperately looking forward for the grade and for the next midterm and while writing this also realizing that this is one of the last blog posts. I would say so far, CSC148 journey was pretty fun and i’m happy that i was able to learn this much stuff so far.

Exercise #3

Week has started with me starting to deal with the binary trees (for exercise #3, of course). The first part, in all honesty, wasn’t even that hard. I figured out that, the only thing I have to do, is recursively go through the in-order and post-order list at the same time, call the make_tree function, check if it in-order list has any items from the left and right sides that hasn’t been checked from the post-order list and keep making the tree that way. I’m not quite sure if I worded it correctly, but the function looks to be working correctly.

The fun now is to focus on Assignment #2, p2 and the second part of the exercise. Unfortunately, as of this date, i’m not able to find a proper way of storing the longest road and the biggest sum at the same time, and whenever I try, ‘comparing two with the same longest roads’ ends up being computed incorrectly.

With all these midterms and assignments, my life looks ‘beautiful’.

Trees and Assignment #2

Last week was pretty fun in regards to the material that I learned. Binary trees, traversals, actual meaning of the making children classes and how useful they can be in your code and a lot more.

I’ve never coded trees and made use of them in the past, so learning an Abstract Data Type that could solve a lot of types of problems (I’m looking at you, Regex’s). Like being able to easily find arity, ‘height’ and etc. attributes of the said ADT, only lets us solve more and more problems. I’m pretty sure i’ve heard about graphs in the past, and from my understanding, trees are kind of restricted graphs, so i’m looking forward to working with the graphs themselves.

And about making superclass and a couple of child classes. It decreases the amount of your code significantly, and unfortunately i’ve never been able to do this in the past. Well, now I’m pretty happy that I know how to do it.

What is Recursion?

My second post was about the recursions, but I left quite a few details. Like, how exactly I imagine recursion in my head. Let’s go for direct Wikipedia explanation of recursion:

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion.

This Wikipedia definition does not explain the way how we use Recursion in computer science though. The next question that pops up is “Then how exactly recursion is useful in computer science?”

Let’s say there’s a really hard problem (I’m looking at you, Towers of Hanoi), which solution really depends on the input. What I mean is, the bigger the input is, the longer it takes to find the exact solution. However, you know solution for the basic input – like when the input is a small integer – 0 or 1. A recursive solution is a solution, where you keep using the simpler solution to find solution for harder inputs. Confusing, I know, but let’s try it in action.

Fibonacci numbers

Fibonacci numbers are the numbers in the following sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21 and etc. By definition, the first two numbers in Fibonacci sequence are 0 and 1, and every next number is the sum of the previous two. So, the ultimate question is, you want to find Nth number in this sequence. And this is where the recursion comes in hand.

You know your first two numbers – 0 and 1, and you know how to get 3rd number – 0 + 1 = 1. You can easily get 4th – 1 + 1 = 2. But what about 788th?

We define a function fib(n), and write a simple condition. When n (the nth number that we’re trying to find) is bigger than 1, it will call the function fib(n – 1) and fib(n – 2) until we get to two base cases – 0th and 1st integer of the sequences – 0 and 1 respectively.

So let’s just look at the function:

def fib(n):
if(n > 1) return(fib(n – 1) + fib(n – 2))
else:
if n == 0:
return  0
else:
return 1

The function will keep calling itself until it gets to the point where it knows the solution to the problem (solution on the base inputs). So the function will keep going and going and going and going… and find the desired Nth number in the end.

Towers of Hanoi

How long it took me to solve the assignment? Way too long. Way more than I actually expected it to take. The problem wasn’t even in the recursion part, it was pretty straightforward (finding the i and making use of it), but the problem was to understand how I am supposed to solve the problem with 4 “stools” or “pegs” as in the real problem itself.

It took me a while to google it, and to understand the Frame-Stewart Algorithm. And I will be honest, I did not understand it quite well, so I had to go the other way around and shorten the amount of moves as much as possible without changing the given recursion functions for 3 stools.

What’s next? Assignment #2. Gotta start doing it as soon as possible, so I wouldn’t struggle as much as I did with the #1.

Assignment? Assignment… Assignment…

Didn’t expect the first assignment to be this twisted and by twisted I mean complicated. Too many functions and it’s quite tiresome finding the right function to fill. And it’s harder to figure out with what I am supposed to fill it with. I get the recursion, I get all of those function calls and I pretty much understand every single concept that might be needed to finish this assignment, however switching between multiple files without full information and trying to fill multiple functions is quite hard. I’ll be honest, the assignment would probably be easier if we would given a direct problem and we would’ve needed to write the ‘application’ by ourself (except the GUI part).

This week’s lab was quite interesting though. As I understand recursion more proficiently, I was able to resolve the problems which i wouldn’t be able to resolve in the past (recursion for the win).

I guess, done for this week, meet you in the upcoming week!

Exceptions and Recursion

Another week of Python programming has passed by. To be honest, even though I had a general experience with Exceptions and Recursion, I never tried to go deeper. Well, now I can proudly say that I totally understand exceptions and the way they work. It reminds me of childhood, when I was playing any game with a ball, and when I failed to do an action (catching the ball, when I was the goalkeeper or not appropriately kicking the ball while playing soccer). Whenever I tried to do an action and failed, I found an excuse for myself. Just like exceptions in coding.

You try an action, if you fail, you decide how to cope with the failure. So you pop another action, “to cover it”. Even though the analogy is not great, I am able to find the similarities between those two.

Second Exercise was pretty easy, once again, but I’m still looking forward to something harder. I feel like the first assignment and it’s huge dependence on recursion will force me to keep digging… and digging… Google actually helped me a lot in understanding the recursion even more.

So far, labs are nice and I totally can feel the difference between CSC108 and CSC148 labs. Wouldn’t say that they’re way more complicated, but they’re not easy enough to finish it within two minutes (not even trying to brag about my non-existent coding skills, just stating the obvious fact).

Back to coding, I guess! Next week’s going to be fun.

Hello World! or should I say, Hello OOP?

// General Ranting

It has roughly been 5 months since I moved to Toronto and started my long-awaited university life. And I took my first real programming course (CSC108). Yes, I have had experience with programming, coding, therefore it was too easy for me. Because, I was able freely code any web application whenever I needed and that was a part of my pocket money back in high school.

And now, back to the point. What is OOP?

Object-oriented programming (OOP) is a programming paradigm that represents concepts as “objects” that have data fields (attributes that describe the object) and associated procedures known as methods. Objects, which are usually instances of classes, are used to interact with one another to design applications and computer programs – Wikipedia

I am probably not supposed to cite Wikipedia, but that’s exactly how one is supposed to imagine OOP. In other words, OOP resembles the real life objects. One could ask, how?

Let’s think of a car. We all know that there are different kind of cars in real life. Every car has its own color, height, width, type, model and etc. And we call them attributes of a single car. However all cars can move, because it’s the most basic reason why people buy a car.

Now let’s transform the real life Car, into the programming life Car. Our class, is a blueprint for our future cars (just like in real life, when we think of a Car, we imagine a prototype of all cars). If we want a specific car, we will create it. So, basically we’re creating a new Car from our blueprints. However, the blueprints are not enough to create our desired car. Therefore, to create our own desired car, we will assign the attributes of our dream car to the said blueprints.

In other words, blueprints will not tell us which color and which model of the car is going to be created, that will be our choice. And that’s how pretty much OOP words in the programming life. We create classes, which are prototypes or blueprints of the objects, and then we create new object(s) from those blueprints, while assigning our own desired attributes to them (we have to keep in mind that those blueprints contain the functions of our cars, but if needed, we can create a new blueprint which will be similar to our first blueprint, but with additional functions (inheritance)).

And, that’s all for today. That’s how I imagine OOP and I’m looking forward to do more OOP in Python, because I never really had much experience in it.