Sorting and Efficiency

For the past two weeks, the course has taken a look at different sorting methods in python, and how they can compare to each other in efficiency. Sorting means to place elements of a list in a certain order.
For an explanation of how sorting efficiency is determined,
feel free to check out this blog  --  http://jason-csc148.blogspot.ca/  --  under "Sorting and Efficiency".
Some examples of sorting algorithms are bubble sort, insertion sort and merge sort.

Bubble sort in python is a very simple algorithm that compares adjacent elements in a list, swapping them if they are in incorrect order. Bubble sort is one of the slowest sorting algorithms, and in worst cases has a time performance of O(n^2).

Insertion sort is similar to bubble sort, in that it compares adjacent elements in the list. However, once it finds a pair of unsorted elements, it takes the correct element from the two, and inserts it into the correct position of the sorted part in the list. When comparing the efficiency of bubble and insertion sort for an unsorted list, insertion sort requires fewer comparisons and is therefore more efficient. It, too, has a time performance of  O(n^2) in a worst case scenario.

Merge sort, however, is on a completely different level than insertion and bubble sort. It maintains a time performance of O(nlogn) for both its best and worst case scenarios. Merging sort works through a merging step, which takes two sorted lists and merges them into one sorted list. This happens by comparing the smallest elements of each list, and placing them into the merged list accordingly. This step is used in merge sort by firstly splitting up the list into single element lists. Then, we merge each pair of lists into a larger list using the merging step. Next, we take the sorted two-element lists and repeat the process by pairing themselves up with of other two-element lists and merging the two lists together. We complete this process until we unify all of the smaller lists into one finalized sorted list. Merge sort is a lot better than insertion and bubble sort because it takes almost constant time to sort any list of the same length, and the run time in general is a low faster.

Recursion

Recursion is a method of problem solving that is based around the idea of taking a complex problem, breaking it down into more easily solves instances of itself, and then finalizing it into a complete solution. Simply put, recursion is a function that calls itself. For example, here is a piece of code that can be used to calculate the factorial of any given number:

def factorial(n):

    fact = 1

    for i in range(1, n + 1):

        fact = fact * i

    return fact

The Factorial of n is calculated by multiplying all the numbers between 1 and n. The above code gives an iterative solution. In order to come up with the recursive solution for the problem, we must first understand that the nth Factorial number is n * Fact(n - 1). Alternatively said, if you know the Factorial for one number, you can calculate the Factorial for the next number. This would be the recursive solution for the factorial number of n:

def recursive_factorial(n):
    if n < 2:
        return 1
    return n * recursive_factorial(n - 1)

In this solution, I placed a threshold to stop the code from iterating through itself forever. This is what is known as the Base Case. In this case, the program returns the number 1 whenever the function is called with an argument value of 1 or less. The program also has something called the Recursive Step, where we call the same method with a slightly modified parameter.

During the first assignment, there were many problems that took me longer than expected to deal with. However, by using the my computer science's "Piazza" website, I was able to conquer many of the problems I came face to face with. The problems I could not solve using this website, I simply went onto Stack Overflow which gave me a greater insight onto how similar problems to the problem I was currently working on were solved. It was also very beneficial asking my friends in the class, as well as my lab partner to give me help on specific parts of the assignment. In all, without communication with my classmates through the Piazza website, and during class hours, I would have had a much more difficult with the assignment. I am very grateful for this, and hope that I can repay their efforts by continuing to be actively social with others taking the CSC148 course.

Coming To Understand How I Program

Lately, I have come to a more psychological answer to difficulties I am having in programming. This realization is as follows: although it may be true that I can understand a problem I am working on by working alone, but I find it a lot easier to work with someone of my own skill level. By easier I mean less time consuming, less stressful, and very helpful when it comes to debugging and getting the program to work properly. Whenever I find myself staring at a complex or difficult program, I tend to stare at it for minutes on edge just trying to understand the very basic concept of what I am seeing. If I don't do this, I would never be able to understand what I am supposed to do in the program, and it would just take longer for me to get past any confusion. However, working with a partner makes this process faster. We would both give each other ideas on how we can work through bits and pieces of the program, ultimately putting my brain at ease, and helping me become more focussed at the task at hand. If any of us gets confused, we would solve the problem a lot faster than if I were just by myself. Many times during the lab, or even during Assignment 1, I would find myself thinking, "What would have happened if I were to do this problem alone?" The answer would probably be me taking more time on something which is, in reality, a very simple problem.

Generally speaking, I feel a lot more comfortable working on more basic problems with myself than anyone else. I am a quick learner when it comes to basic programming, so I feel that if I were to be paired with anyone else to work on something simple, they would only slow me down. I can be quick to program anything that I have already done before, but when it comes to new ideas, or new concepts on how to apply my knowledge, this is when my programming becomes a lot slower. Therefore for problems that involve applying my knowledge or approaching programming in a different way that  I was taught before, are better done with a partner to help me along the way.

Object-Oriented Programming

In the past couple of weeks of the CSC148 course, I have come to a conclusion in python that helped me better understand the concept of object-orientation. Whenever I am asked to create a function that involves the iterations of some random variable, the whole program itself is centred strictly on using an object (an integer for example) which carries out a set of various tasks to achieve a certain outcome. However, some more complex programs, ones in which we have been working on with the introduction to Classes in python, involve a broader use of objects. For example, we would have multiple variables that would be created by the user, and then manipulated to perform whatever action it is that we want it to do. Just about everything we do in object-oriented programming uses objects as place holders for information that we can change, recreate, or delete altogether. This is what makes this kind of programming so interesting to me. Generally speaking, I can make a program to do just about anything that I want it to do, in a way that I can always come back and change specific information in the program at any time I want. We can choose if our objects are to be static or dynamic. This is the kind of flexibility that I love in programming.

So far, we learned how to create a superclass and a subclass, and how these two interact with each other. I enjoyed learning about how I can add on to my current class without altering the original class in any way. Although the first tutorial this semester was very hard in relation to the past tutorials in my CSC108 course last semester, it seems to have prepared myself for the second tutorial, which I found to be much easier.  The first exercise proved to be not all that challenging in my opinion, which brought up my confidence in this course so far. If there is anything that I am currently not so sure about it would be recursion, which may be something that I would have to spend time on to get used to it. In general, I am beginning to get the hang of classes in python, and the depth to which I can create a program to do whatever it is that I want it to do.