Sorting and Efficiency

Sorting is the process of reorganizing a collection of items according to the desired criteria. This desired criteria is usually among ascending, or descending order. In computer science, there exist many types of sorting algorithms that get this job done. From my time in CSC108, the sorting algorithms that I have knowledge about are the bubble sort, insertion sort, and selection sort. However, recently I have learned about quick sort, merge sort, count sort, and python's default built-in sorting algorithm known as tim sort. One might think "why use one type of sorting over the other?" when all types of sorting algorithms can get the job done. Some notable reasons are that depending on the input to be sorted, some algorithms are more efficient than others. What do I mean by more efficient? If the sorting algorithm is given an input that is large in size, either ordered or non-ordered, performance will be quite different. For example, if a sorted list is given to both a program that utilises insertion sort and selection sort, insertion sort would perform better. This is because if the list is ordered, insertion sort just adds each element of the list to the sorted side without having to shift, or insert it into the right position. As a result, this takes at most n iterations. On the other hand, selection sort would still have to go through the whole unsorted side of the list each time to find either the biggest number or smaller number in the group. As a result, at least n^2 iterations are required for selection sort. Now imagine if the size of the input was 10,000. Insertion sort would go through 10,000 iterations while selection sort would go through 100,000, 000 iterations at the least. That would be a big difference in the amount of work the computer has to do. Thus, in this scenario selection sort is less efficient than insertion sort.

Computer scientists like to be able to analyze the run time complexity of algorithms. The notion that is used to represent the upper bound of the run time is known as the Big O. On a side note, the lower bound is known as the big omega and the tight bound (upper and lower bound) is known as big theta. I will be focusing on the Big O notion, but similar arguments can be made to the other two. As an example, the selection sort algorithm is based on a nested loop that depends on the size of n. Thus, selection sort will take at least n^2 iterations. The Big O notation in this case is O(n^2) which means that c*n^2 where c is a constant number is an upper bound for n^2 iterations. This means that the amount of iterations that selection sort takes is either equal to, or less than c*n^2 after a certain size of input. When talking about complexities of algorithms, only the effect at a large size of input is important to us because at a small size input the difference in efficiency is usually ignorable. So, how do we know what is an upper bound for each case? The following hierarchy sets the rules in place: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(n!) < O(n^n). The farther the Big O expression is in this inequality, the worst the performance is. Thus, computer scientists would prefer O(1), O(log n), O(n) over the other ones because at large size of input the difference is immense. 

I will now try to use this notion to describe the new sorting algorithms that I learned known as quick sort, merge sort, count sort, and tim sort. Quick sort is a sorting algorithm that depends on finding a pivot point and separating the elements that are larger than the pivot point to the right side and the elements that are smaller to the left side. This process is repeated n times and if the list is divided equally it will be defined by O(n log n). However, if the list is not divided equally each time, it will be defined by O(n^2) in the worst case. Thus, in the best case n log n is the upper bound for quick sort, but in the worst case c*n^2 is the upper bound for quick sort.

Merge sort is similar to quick sort in the aspect that it also divides the list into two sections and repeatedly does this until each list is a single element. Then, each list is compared with another and merged together into the right order. This process is repeated over and over again until the list is in the correct order. The number of times that merge sort divides the list is described by log n and because there are n elements, the process is repeated n times. Therefore, the Big O for merge sort is defined by

O(n log n). For example, if given the list [5,3,4,2,1], the list is divided into the lists [5,3] à [5] and [3] and [4,2,1]à[4] and [2,1]à[2] and [1]. [3] , [5] merges into [3,5], and [2] , [1] merges into [1,2] , and  [1,2] ,[4] merges into [1,2,4] , and [3,5] , [1,2,4] merges into [1,2,3,4,5].

Tim sort(known as the built-in sort function that python uses) is a sorting algorithm that uses a combination of insertion sort and merge sort to achieve its goal. Thus, the best case scenario is achieved when the list is ordered and insertion sort will only have to insert the items n times. The Big O notation would be defined as O(n) for the best case. However, in the worst case merge sort would be called n times and tim sort would take on the complexity for merge sort instead.  Therefore, tim sort has an order of n log n in the worst case.

In general, computer scientists only care about the efficiency of an algorithm when the size of the input is very large because the difference between small sized input results is usually dismissible. Imagine given a database with millions of entries and it is required to find one element in that database. Of course with our knowledge of the Big O, a searching and sorting algorithm for this problem is preferred to be on the left side of the hierarchy. By comparing the amount of resources used for a log n algorithm versus a n^3 algorithm, one can see the amount of time, resources, and money saved by efficiency. Therefore, sorting and efficiency is a very important topic for future years of computer science.

Binary Search Trees

Firstly, let us make the distinction between binary trees and binary search trees. Both tree structures branch off from a root with maximum 2 children per root, but the difference is that binary search trees sort the data with a condition asserted. This is the condition that all values less than root must go on the left sub-tree of the root while all values greater than the root belongs in the right sub-tree of the root. In the basic sense, binary search trees are the sorted version of binary trees. Due to the structure of binary search trees, searching for a value in them for many of the operations such as inserting, deleting, and returning are effectively more efficient than in a simple binary tree. Because of the condition of the binary search tree, each time we look for a value in the tree, one half of the values can be ignored. For example, if we had 1,000,000 elements in the tree to search from, 500,000 would remain after the first step. This is because if the value we're looking for is larger than the one at the root, the left side is ignored because all of them is smaller than the root which means they are also smaller than the value desired. A similar argument can be said for the other case where the value is smaller than the value at the root.

Binary search trees have similar operations to binary trees, but the way they are implemented is slightly different due to the condition. When implementing methods such as adding, deleting, inserting, or returning, the first condition to check is if it is smaller, equal, or larger than the root value. Then, afterwards depending on what the method is the children are checked for the same cases recursively until the base case for the method is reached. For example, the deleting method for binary search trees have a couple of cases. They are deleting from an empty tree, deleting from a tree with either only the left child, or only the right child, and lastly deleting from the tree with both the left and right child existing. Each case effectively ignores half of tree each time recursively until the base case is reached and the objective of method is reached. The way I see it is that binary search trees are more efficient than binary trees like how binary search is more effective than linear search for large number of searches.

LinkedLists

A linked list is a recursive data structure that is a collection of nodes. A linked list has the option of either being an empty list, or a node that stores data and refers to another linked list. The empty list case is represented with None while the other case splits the node into two parts: the head and the tail. The head is where the value of the node is stored while the tail is where the node references to another linked list. This means that the node may refer to an empty list, or another node like itself. As one can see, recursion plays a big part in linked list structures due to multiple referencing to other linked lists.

Linked lists are similar to lists in the aspect that information can be stored and modified. Some of the operations that they share are adding an element, deleting an element, reversing the list, and finding the element according to the index of the element. However, there is a slight difference because linked lists depend on referencing to another object instead of being one whole object like lists. In linked lists, the operations require the changing of the head's value and the tail's reference. For example, to prepend a value to the front of the linked list, the head of the list must be equal to the new value, but the tail must refer to the previous head of the linked list. Because linked lists use this referencing, infinite loops can cause issues for most of these methods and operations, which end up crashing the program.

As with many computer science structures, there is more than one way to implement linked lists. The first one is the one I've been talking about so far with the use of a head and a tail. The other way to implement linked list is to use linked list as a wrapper class for a class that defines a single node. The node class saves the value and the referenced node while the linked list wrapper class manipulates the nodes with operations. Both implementations essentially do the same thing, but in some cases the other one is more preferable due to the conditions of the problem. Linked list is another way for computer scientists to store and manipulate information, but in a slightly different approach than storing in one object such as list.

Recursion: When and Why?

Recursion is a strong technique of programming where a function calls itself to finish a task. Recursion requires two important parts: the base case and the recursive case. The base case is the one that prevents recursion from going on infinitely. On the other hand, the recursive case is the recursive technique where the function calls itself to solve a problem multiple times until the base case is reached. 

When should recursion be used and when should it not be used? In programming, sometimes there are problems where the large problem at hand can be broken down into a collection of the same problem, but at a smaller scale. For example, the Towers of Hanoi for 3 pegs is a problem where a stack of items must be moved from the source to the destination. This must all be done while following the rule that no bigger piece can ever go on top of a smaller piece. As a result, there exists a sequence of moves that move each item to an intermediate location and then later moving it to the destination. These same moves are repeatedly done over and over again for each item of the stack of items. Hence, in the big picture, the task of moving the large stack of items is just the processing of moving each item piece by piece. This is the recursive technique used in the towers of Hanoi. For problems similar to the towers of Hanoi, the number of times the main recursive technique is used is usually unknown to the coder. Thus, by using recursion the coder can make the program apply this recursive technique as much times as required until the base case is met, which stops the program from executing further. Thus, recursion should be used when the number of iterations required is unknown to the coder.

Another reason why a coder would use recursion is for more elegant code, which makes it easier to read for the coder and the user. This is because the alternative to using recursion is using loops to iterate, which requires more code to achieve the same process as recursion in some complicated scenarios. Also, another thing to take note is that sometimes this results in much messier code. From my understanding of recursion, I believe that recursion makes problems easier for cases such as nested lists, trees, linked lists and any format that has a smaller version of itself within itself. I can conclude that mastering this strong technique will simplify future code and make recursive problems easier to understand in the future.

Binary Trees, Pre-order, In-order, and Post-order Traversals

Pre-order, in-order, and post-order traversal is three ways that computer scientists travel through binary trees that hold different data structures. Depending on the order chosen, the final output may be different. Firstly, binary trees can be thought of as trees where each node is either a root, or a leaf. Roots are the nodes that have children and leafs are the nodes that do not have children. These roots may lead to another tree, or simply a leaf. From a computer science perspective, this can be modeled by recursion by breaking a big tree into a collection of smaller tree and leaves. The question that is left to be answered is "which order do we follow in the tree?"

Pre-order traversal is the method where we start from the root of the tree, then move on to the left sub-tree if available and finally move on to the right sub-tree if available. Note if the sub-trees have other sub-trees within the tree, this method is applied again.

In-order traversal is another method of traveling through a binary tree, but is slightly different from pre-order traversal. Instead of going from root to left sub-tree to right sub-tree, in-order traversal starts from left sub-tree, then move to the root, and finally move to the right sub-tree if available. Note the method is applied recursively if more sub-trees exist within other subtrees.

Post-order traversal is the last way to travel through a binary tree and the method goes as follows: starts from left sub-tree, then move on the root of the tree, and lastly move on to the right sub-tree. Note the recursive techniques applies to this method as well.

These three traversal methods can be coded through recursion and understanding these methods is key before any coding can be done. I myself looked through the tree diagrams and traced each method on paper a couple of times before I could say i was okay with the recursive techniques.When I first stumbled into these three methods in class, I was startled because traversals was completely new to me and I was still quite new to recursion. However, I believe the problem lies in me not being prepared for the lectures due to not reading the lecture notes ahead of time. Thus, that is the main problem at hand that I must fix. Concentration is key and slacking off only leads to falling behind and is a path I would not like to walk in.

Scope of Names and Variables

This week introduced a familiar topic to me known as the scope of names and variables. The immediate difference that I found between the scope in python and java was that scope in python is separated by indentation and white space. While in java the scope of the variables can be understood through what brackets the variables are within. In my understanding of scope, scope is the boundaries of where the variable and names can be accessed. This is a very important concept to understand because in a large program where multiple variables have the same name due to a limited number of ways to describe the same object, the coder will want to specify where each variable should and can be accessed by the program. As explained in the lectures, scope has multiple levels going from local to non-local and to global. In python, I learned that scope is determined by searching from the most inner scope and working outwards toward the global scope. For example, let us say there is the following program.
x = 5
def num_squared(x):
    x = 4
    return x**2

>>> num_squared(5)
16

As the output shows, the x that is considered first is the one inside the function definition and not the x that is equal to 5 which is in the global scope in this case. If the x that we wanted was not the x in the function header, or the x in the body of the function, another approach would have to be used to force x to refer to the x in the global scope. This is the part where the lecture created some confusion for me because we were analyzing scope where a program forced certain names and variables to be visible at different scopes. I wasn't able to keep track of what was happening all at once, but after listening to some discussion from other students in the class, some of this confusion was reduced. I believe the main reason why the concept was confusing to me was because I didn't jot down my thoughts to keep track of what each part of the scope program was doing. As a result, I missed many important things that was happening and led to my wrong conclusion and false understanding.

For class inheritance, my understanding of the concept was pretty much on the spot. The exercise in the lecture where we predicted which functions was used by class B helped practice my understanding of how inheritance worked and as well in a way helped improve my understanding of scope. This is because both concepts start from the inner and then work towards the outer. In the case of inheritance, a method is first searched for in the child class and then the parent class if and only if the method does not exist in the child class. Overall, I believe this week was a very successful one.
 

Reflection of the Week

This week's lectures focused mainly on recursion which is an important concept to understand in order to be able to simplify difficult problems into smaller easier ones. At first glance at recursion, I had some difficulty in understanding the process because of a few minor reasons: not enough time to trace out the code completely, and not enough practice of the concept. For example, in the turtle problem I traced the first and second level of recursion incorrectly due to not understanding how the loops worked with recursion. In order to understand the process a bit more, I have chosen to go back to the first level of recursion and retracing it with pencil again. However, this time I will be tracing the turtle problem and other recursion problems at my own pace of learning and giving myself a longer time period to absorb the concept between each step. I believe this practice will help better my understanding of recursion if even slightly. I truly want to understand recursion because I value the virtue of being lazy in the first year of computer science. Recursion leads to this laziness by simplifying a program that may need 100 lines into a shorter one that only needs 20 through recursive calls. This saves time, effort, and code for the coder. My dream of designing games may cut down from an impossible goal to a reachable goal through recursion.  Mastering recursion will be my goal for week 4 and beyond for CSC148.