Week 10 Sorting Efficiency

The idea of efficiency is not new, especially when it comes to coding. Minimizing the run time of certain code and functions allows for the overall program to be made faster. Even though some solutions may seem to work very well for small sets of data, they may have terrible run times for large data sets. The efficiency of the algorithm depends on the input parameters and the actual algorithm itself. It can be most simply explained by sorting algorithm using Big O notation - essentially its efficiency in the worst scenario.

Bubblesort is an example of a very inefficient algorithm. Its best scenario is O(n) while its worst and average scenario are both O(n^2). Its poor efficiency can be explained by its algorithm implementation: it compares swaps two indexes, i and j, for every index in the whole list. Therefore it can been seen as one for loop with another for loop as both indexes are constantly changing. Therefore we can see it as the efficiency of this algorithm would be n x n = n^2

Other efficient sorting algorithms usually have sorting time of O(nlogn) for worst and average case scenarios. For instance, merge sort has a best, average, worst scenario of O(nlogn). Therefore it can been that although the best case scenario case can be seen to be less efficient than that of bubblesort, the scenario that really matters is the average and worst scenarios. It is okay if the algorithm is not the best, but it is very important that it will never be the worst. 

For algorithms such as sorting, the structure of the input data also affects the efficiency. For instance, when searching for an element in a list, a linear search will search every element in the list, giving it a O(n) efficiency. However if the list is sorted, we can apply a binary search instead: start in the middle of the list, if the element > middle, then search to the right, if element < middle, search to the left. This will naturally increase the search efficiency. 

Algorithm efficiency has very real applications and there are many natural ways in which humans apply these algorithms, even unconsciously. For instance, we tend to use insertion sort. When we search for a word in a dictionary, we would search by looking where we think the letter is first - similar to binary search.

Efficiency of an algorithm is very important and it essential that we ensure the code that we right are efficient for their purposes. If an algorithm takes way too long, even if it works, it may not be the best choice and it would be a better idea to make the algorithm more efficient or simply to look for another solution.

My Problem with Recursion and How I May Have Found the Solution

Week 7 - Recursion

Learning the concept of recursion was quite new for me.

Python is really the first programming language that I was introduced with. It has very simple syntax and the learning curve was quite fast until I reached recursion. It stopped me right in my path. Usually I learn well alone, and I have learned most of Python and applying it through the book "How to Think Like a Computer Scientist". The idea of recursion is not new. It's structure makes sense intuitively but it does seem to lack something that makes is flow in my mind.
From CSC108, we have simply learned to do things step by step. Make a function that performs this, then make another function that do that. If needed, we can make helper functions that makes us accomplish what we need by calling it in another function. However, recursion seems to by pass the step by step format by simply encompassing all the steps into one step, by recursively calling the function itself with simply one line of code. As written in the book, you will need to perform mental abstraction, or take a leap of faith in believing that the base case will work. However, I found taking the leap of faith to be quite difficult. I often find myself tracing the whole code line by line, as I usually do with code in CSC108. However, this step by step method can be very exhausting. Nonetheless, I did manage to find a solution this week to finally mange to learn the idea of recursion - at least I hope so.
After lab 7 and 8 - linkedlist, I found a basic technique of using recursion and coding recursion when needed. That is, to follow the basic format of recursion. I use my own sort of algorithm for recursion.
1. Identification
- Recursive structures are fairly easy to identify, sub-problems have the same structure as the overall great problem. So this was quite simple (Examples are fractals or Trees)
2. Coding recursion using the basic idea of:
a) Base case - this line will do something for the base case (summing the lowest leaves of a Tree)
b) Recursive call - This line will make the recursive call if the current arguments are not the base case
3. Believe - I find that the leap of faith is very important. There is no need to trace every recursive call - it is simply annoying and can lead to mistakes. Just take in mind that your base case code will handle the smallest problem, and your identification in step 1 + recursive call in 2b) will handle the rest because if you correctly performed step 1 then your recursive call will work. Every recursive call is the same even if the arguments change because that is what recursion is all about. Using the solution of the smallest problem to solve the biggest problem because they are essentially the same problem.

Recursion is a brilliant idea and it makes coding incredibly efficient. I have often wondered what makes computers incredibly efficient at performing tasks that humans find incredibly difficult. Now I believe I have found one piece that explains the differences between humans and computers. Computers are exceptional at performing the same task over and over again with no mistakes, while humans are not. However, humans are able to adapt different strategies for different problems. In real life, no situation is the same, and thus we will rarely find recursive structures in nature. However, when we categorize the world and store its information into data that have the same structure, computers can use recursion to complete these repetitive, long tasks.

Week 3: Objective Oriented Programming

Week 3 has been quite fun.
Objective oriented programming makes me feel as if programming became a lot more realistic tool for me.
Compared to 108, I just realized that object oriented programming is what really allow us to code complicated programs and tools. Understanding it is quite difficult at first. In my first lab, my partner and I both had trouble understanding how objects really work, but once we got through the first barrier, the rest of object programming, methods, attributes and etc, all came really easy. Essentially once the concept was grasped, the rest was really simple.

Overall I am quite confident thus far. I am hoping to really apply what I am learning to code something that I can possibly use in real life. Compared to other classes, this is probably the most fun class. I am not only learning concepts, I am applying them in ways I like to solve problems. This course really takes the load of other courses where it is essentially memorization.

Hopefully the next few weeks are equally exciting!