Sorting and Efficiency

To sort a list of data means to rearrange it to be in order. There are applications of sorting algorithms everywhere we look, from organizing a library in alphabetical order to arranging scores in athletic competitions. We have learnt that in computer science, it is often very useful to have the data sorted, as it enables more efficient search algorithms (eg Binary Search).

http://www.question-defense.com/wp-content/uploads/2010/03/itunes-music-library.gif

We have learnt that there are many ways to approach the problem of sorting, and some are more efficient than others. The main algorithms that we talked about in class are listed below from the most inefficient to the most efficient:

• bubble sort
• selection sort
• insertion sort
• merge sort
• quick sort

The first three are less efficient ( O(n^2) ).

Bubble sort works by going through the list comparing each item to the next one, exchanging them if list[i+1] is greater than list[i], "bubbling" an item until a greater one is found or the end of the list is reached placing the largest item at the end. The process is repeated n-1 times, bubbling through a smaller list every time. This algorithm is considered to be the most inefficient as it can often exchange the same variable several times before it is at is final location.

Selection sort similarly requires n-1 passes, however this time each pass requires only one exchange. First t the whole list is considered, the min of the list is found, and replaced with the first item of the list, then the algorithm repeats the remaining n-2 times until the end is reached.

Insertion sort also requires n-1 passes, creating a sorted a sublist from the first item of the list and inserting each new value into the sorted sublist at it's correct position.

Merge sort is different from the previous three algorithms. It is a recursive algorithm that works by continuously splitting the list in half until each item is a single element list, then going backwards by merging the original lists in correct order. Merge sort (unlike quick sort) has a consistent efficiency of O(n log n) however it also requires more memory to be storing one half of the list while performing operations on the other.

Quick sort is similar to merge sort in that it is a divide and conquer (recursive) algorithm. It works by picking a pivot value and going through the rest of the list from both sides. Swapping values that are in the wrong place (>pivot value going from left, <pivot value going from right), until the search crosses and the location for pivot value is found (all items less than pivot value on one side, greater on the other). At this point we swap pivot value with the item at pivot value location, and recursively call quicksort on list[:pivot_value_location] and list[pivot_value_location]. Quick sort doesn't require as much memory as merge sort, however it's efficiency can be compromised by choosing pivot value that is too big or too small (optimized when the pivot value is close to the median)

http://sortvis.org/images/dense-quicksort.png

PS :

I found some really cool visualizations of different sorting algorithms like the one above that you can check out here:

http://sortvis.org/index.html

also this video is pretty neat:

https://www.youtube.com/watch?v=kPRA0W1kECg

Recursion

Recursion occurs in computer science when a function calls itself in its definition. It is a concept that is hard to grasp but once you do, it becomes a very useful tool. Recursion is used when to evaluate the task the same algorithm is performed again and again converging towards the base case until the solution is evaluated. One might think that sounds a lot like iteration, and that's because the uses of recursion and iteration are similar, one being more or less appropriate depending on the task at hand. 

One of the simplest applications of recursion is finding the n-th term of a sequence that is defined by recurrence relation, meaning each term is implicitly defined by the previous term. One of such sequences is the fibonacci sequence. Using recursion requires to user to define the base case, the outcome that results when the recursive function is able to return a value before calling itself once. The more times the function has to call itself, the further away the initial value is from the base case.

In the case of the function nested_depth the base case is defined for L that is a non list, it returns 0. That means that throughout the calculations, the base case is used whenever the function encounters a non-list, which otherwise allows to cumulate the amount of nesting in a given list.

Some say intelligence as we know it, is the evolutionary result of an ability unique to humans (as far as we are concerned) called metacognition, which basically means "thinking about thinking".  Great philosophers have pondered on this for centuries. 

Today, most have probably heard of the statement: "I think, therefore I am" coined by Rene Descartes, a 17th century philosopher. This statement implies that the whole nature of existence is recursive based on the condition of self awareness.  Fractal patterns produced by recursion are seen all over in nature. Perhaps recursion can be used to approach some of the most fundamental questions about the universe, macro and micro.

pictures: 

https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiEKSRkftRym5w4PiZ8RM0aXB5eVyoZDFfK5E_kT3ELFpu4_ZP2hIidruUEKOkJYaI82USY5jzc9vY6QisVIDuB3xaHuB8p-3Puzx5gSZIGxF2gzgzCXv4Pfgp_ssBfmqRNOUosE7R3UQ/s1600/recursion.jpg

https://lh5.googleusercontent.com/-huTWn4MTkKw/UYuLcVBsA2I/AAAAAAAAtJE/mR8otMVN0OA/w800-h800/recursion.png

            

Object-Oriented Programming

Object-Oriented Programming is the defining feature of Python as a programming language. Objects are used to create variables which can then be used for basic operations or something more complex like writing functions to perform specific tasks. Python offers the user some basic built-in data types (int, bool, str.. etc.) which are all considered objects. These objects have their own defining features. Different objects are used to store different types of data allowing the user to perform certain operations on them. The types of operations that can be used with an object are defined by the methods associated with that type of object. A class is a special type of object that allows the user to define the features of that type of object. It can be conceptualized as a blueprint for a user defined object. When creating a new class, the user will generally have to write the "initializer" method (__init__) that will be called when a variable of the object type defined by the class is created. There are some generally useful methods to write in any class (__str__, __eq__, __repr__). However, the ability to design a class gives the user the freedom to write their methods that can then be called on variables of that class to perform certain functions. With this freedom, Python becomes a language that can be designed by the user depending on the task at hand.

first entry (Welcome!)

Hello and welcome to my SLOG. From now on I will be posting reflections on the progress I make in CSC148. I hope you enjoy your stay and feel free to comment on any entries I make.