Sorting data is probably one of the most basic functions that you might have a computer do, its one or two steps above asking the computer to store data or perform arithmetic. The problem seems very simple and intuitive to all of us and so you might imagine that this problem is equally as simple in computer science. Well, yes and no; it really depends on what you're looking for. Yes, writing an algorithm to sort an array is very simple, you can brute force it if you like (please don't!). But sorting efficiently? Now thats a non-trivial problem and one that I want to address here.
Asymptotic Run Time
To begin, we first need to develop some tools in describing the efficiency of an algorithm. Now, the number of steps/the time it takes for a sorting algorithm to run depends heavily on the machine it's being run on and the details of the implementation of algorithm being used. However, when we talk about an algorithm's efficiency, we want to detach our analysis from these specifics and a good way to do this is by looking at its asymptotic running time, i.e. big O. Now, say that the number of steps it takes for an algorithm to sort a list of n elements is T(n). Informally, we can say that T(n) is in O(g(n)) if, as n becomes really large, T(n) can be bounded from above by the function c*g(n), where c is a constant. So in other words, g(n) provides an upper limit for the asymptotic growth of the function T(n). If T(n) is in O(n) (linear time) then it cannot grow faster than a linear function, for example it cannot grow like a quadratic or exponential function.
Sorting Algorithms
Now that we're able to describe the efficiency of a sorting algorithm, let's look at a few and see what each has to offer. Note: this is in no way meant to be comprehensive.
Selection Sort
This algorithm is quite simple, you simply find the smallest element of the original list, delete it and then append it to a second list. You keep doing this until the original list is empty and then you return the second list. Over a single pass the algorithm makes n-1 comparisons where n is the current size of the original list. This leads a total of n-1 + n -2 + ... + 1 comparisons which means T(n) is in O(n2). One characteristic of this algorithm is that all lists of size n take the same amount of time to sort.
Insertion Sort
This is another very similar algorithm which involves building a sorted list one element at a time by swapping elements in a sublist until that sublist is sorted. The worst case scenario for this algorithm is the same as selection sort, i.e. O(n2) however it is very fast for nearly-sorted lists i.e. O(n) and is one of the most efficient sorting algorithms for small lists.
Merge Sort
This algorithm splits the list in half and then calls itself recursively on those halves. It then combines the sorted halves using a linear time merge operation. In total, the algorithm performs log2n merges making it a O(nlogn) sorting algorithm and therefore much better with large lists than both selection and insertion sort. Merge sort also shares with selection sort the characteristic that the order of the elements in the presorted list do not affect its runtime.
Quick Sort
Quick sort works by choosing a pivot point in the list and then moving all values in the list smaller than that pivot point to the left and all values larger to the right. It then recursively sorts the two sublists. The efficiency of quick sort is highly dependent on the choice of the pivot point. At its worst, its a O(n2) algorithm like insertion sort and selection sort (this is extremely unlikely if the pivot point is chosen) but on average it's a O(nlogn) algorithm like merge sort. In fact, its performance is actually better than merge sort given a wise choice of pivot point.
Counting Sort
This reads the value of each integer in an list and adds a counter to an bookkeeping array for each copy of a specific integer found. The sorted list is made by reading off counters from the bookkeeping array. You might have already realized that because you only go over the list once, this is always a O(n) algorithm! Every sorting algorithm which has been mentioned so far is an example of a comparison based sorting algorithm. Theoretically, the average runtime of these algorithms cannot be faster than O(nlogn) however counting sort is not comparison based and is therefore not subject to this lower bound. The problem with bin sort is that it can only be implemented of arrays of integers and it cannot be efficiently implemented when the difference between the max and min values of the list (the algorithm is also in linear time with respect to this difference) grow to much larger than the size of the array itself.
The Ideal Solution
As you can see from above, no algorithm has it all; each algorithm has its own strength and weaknesses. Insertion sort is by far the best sorting algorithm for small arrays but, as a O(n2) sorting algorithm it is quickly out-scaled by both merge sort and quick sort. Quick sort and merge sort may be both O(nlogn) on average but Quick sort has a worst case of O(n2) whereas merge sort is always O(nlogn). Counting sort's average case of O(n) is superior to all the other sorting algorithm but it is much more limited in breadth compared to the others. In the end, there probably won't be an ideal solution which works for every case but there is certainly not a short supply of algorithms which are well-suited for whatever specification you desire.
Wednesday 2 April 2014
Monday 3 March 2014
Recursion
When I first saw recursion, I thought it was a pretty cool. It was a neat little trick that can solve certain problems while being very succinct when written. However, this interpretation is purely superficial and completely masks the true power of the technique and how central it is to computer science. Recursion is used in many powerful algorithms and there are man problems that exist which are most efficiently solved through recursion.
At its core, recursion is about breaking a problem into smaller versions of the same problem and then recursively breaking those smaller problems into even smaller problems until you reach a base case which can be solved directly. Using the solution of the base case, you then move up the chain solving each problem until the original problem is solved. An example of this would be a function which calculates the factorial of an integer n. The factorial of n or n! is equal to n(n-1)...1. One can immediately see that n! = n(n-1)!, this serves as the so-called recursive case and by definition we'll take 0! = 1, which will be the base case. So to solve n!, you would to solve (n-1)! and to solve (n-1)! you would solve (n-2)! and so on. If you keep applying the same procedure you eventually reach the base case 0! and then you can evaluate the entire chain of factorials before it. An implementation of this algorithm in python would be the following:
def factorial(n: int) -> int:
# recursively calculates n! for int n >= 0
if n == 0:
return 1 # base case
else:
return n*factorial(n-1) # recursive case
We can examine how this function works by tracing the code when it calculates something simple, like for example 3!.
factorial(3) -> [3*factorial(2)] ->
3*[2*factorial(1)] -> 3*2*[1*factorial(0)] -> 3*2*1 -> 6
So it essentially multiplies n by a recursive call on n-1 and it keeps doing this recursively, generating the familiar n(n-1)...1 expression as expected.
Now this is not a particularly interesting example of recursion, in fact recursion is not necessary to solve this problem and iteration would work just fine so let's move on to a slightly more interesting example. Take a function which sums a list of nested lists, i.e. a list within a list within a list, etc. Summing a list of nested lists is the same as summing each nested list and then summing the result of those sums. If an element within a nested list is another nested list, then you apply the same procedure until you reach the base case which is just a list of integers. An example of a function using this algorithm in python would be the following.
def sum_list(L: list) -> int:
# recursively sums a list of nested listed lists L
return sum([sum_list(element) if isinstance(element, list) else element for element in L])
So this function iteratively goes through the elements of the list L and checks if each element is a list or not. If it is, the function then calls itself on the element and then replaces the element with the result of that function call and if not, the function leaves it alone. Once the list is exhausted, it then returns the sum of the list. It will keep evaluating recursive calls until the list L is entirely filled with integers at which point it just sums everything.
One of the wonderful things about this function is that it can handle lists of any arbitrarily large depth and it will sum any arbitrarily large number of lists. This ability to scale is one of the most powerful aspects of recursion.
Now notice that in both of these algorithms, each recursive call brings the function closer to the base case. This is extremely important because if either a) the base case doesn't exist or b) the base case is never reached, then the function leads to an infinite recursion which will not return anything.
Now the above talks about recursive functions/algorithms, there is another very important area of computer science in which recursion is of utmost importance, that being recursive data types. In a recursive data type, the definition of the data type links to itself. An example of which is a linked list, which is defined to have a head, which contains some data, and a tail, which is (a reference to) another linked list. The main advantage of recursive data types is that they can grow dynamically to arbitrarily large sizes if need be, in contrast to statically-defined data types which are fixed after creation. For example, a list created using linked lists need not have all its elements stored together in memory like a static array implementation would require, elements can be freely added or removed by simply creating another linked list and then changing the appropriate memory references. One should not be surprised to hear that recursive functions and algorithms lend themselves surprisingly well to working with these data types.
So in conclusion, recursion is very useful whenever a problem can be broken up into smaller instances of the same problem. Recursive solutions should be admired for being very succinct answers to complicated problems and for their ability to handle an arbitrarily amount of scaling. One should look for recursive solutions whenever possible but one must also recognize that they are not always possible to find in many cases.
At its core, recursion is about breaking a problem into smaller versions of the same problem and then recursively breaking those smaller problems into even smaller problems until you reach a base case which can be solved directly. Using the solution of the base case, you then move up the chain solving each problem until the original problem is solved. An example of this would be a function which calculates the factorial of an integer n. The factorial of n or n! is equal to n(n-1)...1. One can immediately see that n! = n(n-1)!, this serves as the so-called recursive case and by definition we'll take 0! = 1, which will be the base case. So to solve n!, you would to solve (n-1)! and to solve (n-1)! you would solve (n-2)! and so on. If you keep applying the same procedure you eventually reach the base case 0! and then you can evaluate the entire chain of factorials before it. An implementation of this algorithm in python would be the following:
def factorial(n: int) -> int:
# recursively calculates n! for int n >= 0
if n == 0:
return 1 # base case
else:
return n*factorial(n-1) # recursive case
We can examine how this function works by tracing the code when it calculates something simple, like for example 3!.
factorial(3) -> [3*factorial(2)] ->
3*[2*factorial(1)] -> 3*2*[1*factorial(0)] -> 3*2*1 -> 6
So it essentially multiplies n by a recursive call on n-1 and it keeps doing this recursively, generating the familiar n(n-1)...1 expression as expected.
Now this is not a particularly interesting example of recursion, in fact recursion is not necessary to solve this problem and iteration would work just fine so let's move on to a slightly more interesting example. Take a function which sums a list of nested lists, i.e. a list within a list within a list, etc. Summing a list of nested lists is the same as summing each nested list and then summing the result of those sums. If an element within a nested list is another nested list, then you apply the same procedure until you reach the base case which is just a list of integers. An example of a function using this algorithm in python would be the following.
def sum_list(L: list) -> int:
# recursively sums a list of nested listed lists L
return sum([sum_list(element) if isinstance(element, list) else element for element in L])
So this function iteratively goes through the elements of the list L and checks if each element is a list or not. If it is, the function then calls itself on the element and then replaces the element with the result of that function call and if not, the function leaves it alone. Once the list is exhausted, it then returns the sum of the list. It will keep evaluating recursive calls until the list L is entirely filled with integers at which point it just sums everything.
One of the wonderful things about this function is that it can handle lists of any arbitrarily large depth and it will sum any arbitrarily large number of lists. This ability to scale is one of the most powerful aspects of recursion.
Now notice that in both of these algorithms, each recursive call brings the function closer to the base case. This is extremely important because if either a) the base case doesn't exist or b) the base case is never reached, then the function leads to an infinite recursion which will not return anything.
Now the above talks about recursive functions/algorithms, there is another very important area of computer science in which recursion is of utmost importance, that being recursive data types. In a recursive data type, the definition of the data type links to itself. An example of which is a linked list, which is defined to have a head, which contains some data, and a tail, which is (a reference to) another linked list. The main advantage of recursive data types is that they can grow dynamically to arbitrarily large sizes if need be, in contrast to statically-defined data types which are fixed after creation. For example, a list created using linked lists need not have all its elements stored together in memory like a static array implementation would require, elements can be freely added or removed by simply creating another linked list and then changing the appropriate memory references. One should not be surprised to hear that recursive functions and algorithms lend themselves surprisingly well to working with these data types.
So in conclusion, recursion is very useful whenever a problem can be broken up into smaller instances of the same problem. Recursive solutions should be admired for being very succinct answers to complicated problems and for their ability to handle an arbitrarily amount of scaling. One should look for recursive solutions whenever possible but one must also recognize that they are not always possible to find in many cases.
Sunday 26 January 2014
Introduction and Object-Oriented Programming
Greetings, traveler of the inter-webs. You have arrived at a student blog for CSC148 at the University of Toronto. For this visit, I will guide you through my experiences over the course of the semester. The topics encountered below will be primarily related to computer science and will often be about the python, the most venomous snake found in these here lands. Wait. I mean programming language - the python programming language. Right. Anyways, I will stop making stupid jokes for fear of further embarrassment.
Now, onto the main topic: object-orientated programming. I had heard the term object-orientated programming (OOP) before taking CSC148, though I had never really understood it. Most of my experience programming was conducted in a physics-orientated setting and we did use python but we did so without reference to objects and such.
Object-orientated programming is a so-called programming paradigm, basically a sort of mindset when it comes to designing code, and is often contrasted with procedural programming. In OOP, things like lists, numbers and arrays are treated as objects. Each object is an instance of a class, basically a template for objects, and each class has associated properties and functions, these are termed attributes and methods.
Taken as a whole, OOP does not add any additional functionality to the code - you can make code which performs the same function with any procedural language. What it provides however, is a coherent and logical scaffolding around which code can be built and organized around. This division of objects into various classes reflects a natural human tendency to organize and group things, with more closely related objects sharing both properties and functionality. It's certainly an interesting way of designing code but the merits are not obvious at first glance. For smaller programs, the added complexity can seem superfluous but for larger programs one could imagine the extra organization helping in tying the program together. But who knows, I may be completely wrong. There's much for me to learn and perhaps only after I've gotten more experience working with objects will I have a firmer grasp of both its importance and relevance. There'll be more on that later though.
Now, onto the main topic: object-orientated programming. I had heard the term object-orientated programming (OOP) before taking CSC148, though I had never really understood it. Most of my experience programming was conducted in a physics-orientated setting and we did use python but we did so without reference to objects and such.
Object-orientated programming is a so-called programming paradigm, basically a sort of mindset when it comes to designing code, and is often contrasted with procedural programming. In OOP, things like lists, numbers and arrays are treated as objects. Each object is an instance of a class, basically a template for objects, and each class has associated properties and functions, these are termed attributes and methods.
Taken as a whole, OOP does not add any additional functionality to the code - you can make code which performs the same function with any procedural language. What it provides however, is a coherent and logical scaffolding around which code can be built and organized around. This division of objects into various classes reflects a natural human tendency to organize and group things, with more closely related objects sharing both properties and functionality. It's certainly an interesting way of designing code but the merits are not obvious at first glance. For smaller programs, the added complexity can seem superfluous but for larger programs one could imagine the extra organization helping in tying the program together. But who knows, I may be completely wrong. There's much for me to learn and perhaps only after I've gotten more experience working with objects will I have a firmer grasp of both its importance and relevance. There'll be more on that later though.
Subscribe to:
Posts (Atom)