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.