Sorting and Efficiency

The topic about efficiency is what I've been looking forward to for a long time. I feel like I always subconsciously want to make my program run as efficiently as possible with the fewest codes as possible. Usually I'd just sit there for a long time thinking of an efficient method. If I spend too much time, I'd just give up and use the less-efficient method that comes with lots of code.

But I'm pretty sure this applies to most computer scientists. It's as if we're naturally lazy. We want to find the best way to do things, with the least amount of effort. And so, this causes us to come up with methods to code efficiently. I'd be pretty surprised if someone told me recursion wasn't created because of laziness. I mean we could be using loops and nested loops, but we'd have to write a lot of codes and the program could end up being slow. This method is inefficient. Someone must of said "This is enough", and went on and founded recursion.  Recursion can drastically cut down the length of your codes.

In computer science, efficiency is measured using Big-Oh. This gives you an upper-bound of the runtime of an algorithm. For example, my problem (before taking this course) would usually be having too many nested loops. The algorithm of a single loop would be O(n). If another loop is nested inside, the algorithm would change into O(n^2). For m number of loops that are all nested within each-other, the algorithm would be O(n^m).
So if n represents the number of items in a list, then as the list doubles, the runtime for the O(n) case will also double. Yes, it may not sound like a problem now but lets go to the O(n^2) case. In this case, the run time would quadrapole as the list doubles.  For O(n^3), the run time will be 9x longer. And so for O(n^m), the run time will be 2^m times slower as the list doubles! 

As you can see, the more nested loops you have, the longer the runtime. Moreover, your codes would look messier and will be harder to read. Thus your program is inefficient. Both these reasons, especially the latter, is what motivates me in paying attention to the efficiency of my program.

Efficiency appears to mostly discussed and highly relevant with sorting. For a list of 100 items, the sorting run time difference between O(n) and O(n^2) can be a maximum of 99x slower! This is for a hundred items in a list, but it is not uncommon to have to sort between thousands, or even millions of items between a list. And so a difference of one order can make a huge difference in the efficiency of your program!

There are many sorting methods such as selection sort, which gives an efficiency of O(n^2).

When working with efficiency, especially with sorting, it's best to follow this hierarchy below and aim for the smallest Big-Oh algorithm.

O(1) <= O(lgn) <= O(n) <= O(n^2) <= O(n^3) <=.... <= O(2^n) <= O(n^n)

Assignment 2

Hey, sorry for not posting last week. I forgot :P

I've been busy for the past few weeks and will continue to be busy. I've already finished my assignment, so I can get it out of my way.

It took me much longer than planned to finish it. Implementing the is_regex() function seemed difficult at first but I tackled it by making it work with the "0", "1", "2" and "e" first and work my way upward.

I spent most of my time with the permutation function. I probably could solve it with less trouble with loops rather than recursion but I had a feeling we were expected to use recursion. I also had efficiency in my mind while doing this. After many hours of futile efforts, I eventually ended up using the per() function given in one of the lectures as a helper function.

The regex_match function isn't so bad as expected. I tackled it the same way as I did with the first function.

Finally, the last function was pretty easy to make. I based the codes of the is_regex function and make some small changes.

Recurssion

Hello, welcome to my fifth post.

I mentioned recursion a few times before. Mostly, I've been talking about how I'm looking forward to receiving new computer science skills like recursions. I have many programming experience but since these experiences were obtained by coding myself, I lack the computer science skills such as proper style and better, more efficient methods in implementing solutions.
So basically, even though I have programming experience, my ability to think like a good computer scientist isn't as good as it should be, which is why I took this course.

I mentioned recursion briefly in one of my previous posts. What I basically said us that I found recursion mind-bending, even though I finally got some experience with it. I also didn't see the point of tracing, but that was mostly because I misunderstood its role. Within the past few weeks since I said that, I thankfully got some more practice with recursion.  Moreover, I was able to use tracing to help me with recursion. I now know its purpose and how useful it can be. Recursion got so much easier for me now. It's not as mind-bending as it was a few weeks ago and thats mostly because of the use of tracing.

I still feel like I need more practice with recursion. But I'm pretty sure that this course will continue to give me the practice I need. What's in my mind the most is when I should use it. I understand its purpose and importance but I'm worried that I'll fail to notice that recursion is a solution to a situation when I come across it. Up until this point, I've used recursion after the problem mentioned recursion or trees. For example, we had one tutorial that's purely dedicated to recursion. Because of that, I know that I'm supposed to use it for this lab. But if a situation arises that could be solved with the use of recursion, my problem here is recognizing that. Otherwise I'd probably be using a bunch of loops.

Perhaps I should practice solving problems twice by using recursion and then loops. I can note its difference between my solutions.

Week 6 - Assignment 1

Unfortunately I did not finish the assignment on time. I thought the due time was 10:15 but I got an email saying it was at 12. Well its too late now but that extra two hours would of helped me a lo. I basically finished all the step except step 5. Last week, I said that I didn't know what the point of tracing is but now I know. It helped me a lot about what's going on with the recursion method M(n). It helped me come up with a strategy to finish the problem. Unfortunately, that strategy is flawed and I didn't have enough time to sit down and come up with another strategy with the help of tracing. So instead, I decided to use all of my short remaining time to make my method much more complicated which still doesn't work for n > 8.

So I guess I feel pretty down and ashamed for not finishing the assignment on time. I guess that means I'll need to start on my next assignment earlier.


That is all.

Week 5

Welcome back :)

I did some recursion in tutorial this week. I'm glad I've got to practice with it but I feel as if I still lack experience. Recursion is still mind bending to me. So I feel like I need to practice with recursion more.
Not only that, I feel like I still don't know when to use it. If I come in a situation where I'll need to use recursion, I'll probably think of a different solution like loops without realizing that recursion would be a better option.

I guess I just need more practice with recursion.

Another thing that I didn't understand in tutorial was "Trace". I can see that there is a relationship between Trace and recursion but I still don't know what it is. To me, it just seems to be a waste of time.

Anyways, I'll be practicing trace and recursion over reading week. It also seems that the assignment will require me to use recursion. I have started on it but haven't done enough to speak about it this week. So expect me to talk about it next week!

Recursion and Inheritance

Welcome back!

I've know about recursion and what it does for a long time now. But I never found an opportunity to use it, nor do I ever think about it while programing. However, it appears that there are a  lot of emphasis on the importance of recursion. I hope that I'll come across many examples and situations where I'm forced to use this. It looks like we'll be working on recursion next tutorial, so I'll be looking forward to that!

Speaking of tutorials, this week tutorial was once again, useful. The biggest highlight for me that occurred in that tutorial is working with inheritance.
I've never really understood the importance of inheritance. I felt as though there is no point in inheriting a class if you can just make a new instance of the class instead. However, I was taught that there was an important reason of why you would use inheritance. In an inheriting class, you can have methods that belong only to this class, rather than the class it's inheriting from.

Unfortunately, this tutorial did not really instruct us to make methods within the inheriting class. I think It would help be much more benefiting for me if we were to do so. Hopefully I will come across a situation in the near future where inheritance will be used.

But for now, I'm more interested in using recursion. I'll be looking forward to next week's tutorial!

Object-Orientated Programing

Object-Orientated Programing
I have been programing for years on my spare time. I have developed small games, servers and other programs which requires object-orientated programming. Most of my programming skills come from experience and looking at small tutorials/docs for minor things such as how to use a certain type of variables and its methods. I usually put effort into learning new things about a certain programming language rather than enhancing the skills I have right now. This results in knowing a lot about a certain language(i.e. knowing variables and what I can do with them) but having poor style and doing things the long, complicating way. This is my main reason of selecting this course, to improve my programming style and to learn new useful techniques and when to use them(i.e recursion).

Before taking this course, I barley understood what object orientated programing means. I just wrote codes, and did many OOP while not fully understanding whats happening. This would sometimes cause problem. For example, I used to be really confused and lost when I'm trying to use a particular instance of a class in a particular way but ended up creating a new class (the problem was much more complicated).

After taking this course, I have a deeper understand of OOP.
There are three main vocabularies to know when thinking about OOP.
Object: Similar to real life objects; They contain data (i.e. name, age) and functionality (i.e. walking, reading)
Class: A template or blueprint of objects which contains variables and methods
Instances: A unique copy of a class which refers to an object.

So for example:
Lets say you have 5 different phones. Each of these phones is an Object of type Phone.
When programming, you create a class called Phone, which has variables such as size, service provider and colour. It also has some methods to describe the behavior such as turn on, calling, sending. This class is a blueprint of the object Phone.
Since we have five phones, each of these phones is an instance of the Phone class, which represents the object.

Each of the instances will have different variables set (i.e. one phone is blue while the other is red). These instances can also call methods to perform a behavior (i.e. one phone can be sending a text, the other can be turning off, and the rest can be doing nothing).

Now that I have a deeper understanding of Object Orientated Programing, I want to talk about something new I learned from a tutorial. If I want to compare two instances, I'd normally have a function that takes in both instance and compare them. But apparently, this isn't a proper way of doing things. What I was told is that it's better to create a method inside the class and do the comparing there.

I personally still am confused on why this is more appropriate. When creating this method inside a class, we can call the method by the first instance or the second instance. For example:
a.compare(b) or b.compare(a)
I feel like I'd rather have: compare(a,b)
But this way also works and since it seems conventional, I gotta put my personal taste aside.

As mentioned earlier, I had very limited knowledge of what OOP is even though I have been using it for years. Fortunately,  I feel as if I have achieved great understanding on OOP and I've gotten really confident with this topic. I'm looking forward to my next lecture and tutorial in this course.

Thanks, see you next week :)