Sorting and Efficiency are two topics in Computer Science that is essential in being a good Computer Scientist. Sorting is simply organizing objects in a particular order, this order is generally done ascending or descending. Efficiency is the measure of performance over time of a program and maximizing efficiency is the key to writing good program as low run times is what computer scientists strive for in their code. These two concepts together sees the subject of comparison between sorting efficiency of algorithms. Different sorting algorithms will accomplish the same task with different methods that vary in efficiency.
Many different types of sorting algorithms exist and is nearly impossible to talk about them all in this Blog. A few popular ones that everyone knows include Bubble sort, insertion sort, selection sort, quick, merge, and tim sort. As it turns out, the examples provided are also listed in order of efficiency with bubble sort being most inefficient while tim sort having best efficiency. To be efficient, the sorting algorithm must be able to able to perform the program with relative short time. This efficiency can be measured in terms of constant time and and the number of iterations we use within our algorithm. This "time complexity" lives within a notation denoted by "Big-O" and can represent an algorithms worst, average, and best expected run time with respect to constant time. The most common run times we use to analyze the run times of programs are denoted by the following; O(n), O(lg n), O(n lg n), O(n^2), O(2^n), O(n!), and O(1). It should be mentioned that the lower number within the brackets represent the most efficient run time.
Lets analyze selection sort, the algorithm can be found below:
def select(L):
"""Produce copy of L in sorted order
>>> select([3, 1, 2])
[1, 2, 3]
"""
L1 = L[:]
for i in range(len(L1)):
m = min(L1[i:])
j = L1.index(m,i)
L1[i], L1[j] = L1[j], L1[i]
return L1
We have a list <L1> which is being iterated through by the for loop, assuming our list length is n, iterating through n items will take O(n) time. Everything else within the loop is O(1) time approximately because we generalize variable assignments and such to this order, rendering the program O(n). This makes sense, but the line where we copy <L> to <L1> could also take O(n) steps if we were to imagine it with a for loop. This is to say the program has O(n) + O(n) time, but this is would simply be 2*O(n) which is a constant multiplied by our scaling time complexity. The key to time complexity is that we only care about scaling variables, therefore we drop the 2 and end up with O(n) time.
Sorting is a very interesting in computer science as unlimited opportunities exist for the algorithm to be even more efficient. Some algorithms are more efficient in certain cases while perform worse in others. Efficiency is key in writing code as runtime really starts to matter when the program is executing on objects that are very large.
Wednesday 2 April 2014
Wednesday 26 March 2014
Week 9 - Working on A2
This week was mainly focused on A2 and the working of regexs. This week was mainly focused on A2b as A2a was done immediately upon return from reading week. A2b focused more on the actual running of code whereas A2a served as a template for the rules of the various trees such as bartree and startree.
My group and I encountered problems straight away when starting the assignment. We wondered just how exactly we were going to go about writing these functions. The first one was is_regex that determined whether we were working with a regex or an invalid one. We initially hard-coded the entire function which took around 200 lines. This was very inefficient and had some problems while running. We later discovered that this can we written recursively and can be done in less than 50 lines of code without errors occurring. We then began thinking and approaching the problems in a more recursive manner and tried to incorporate recursion in all of the functions. Permutations of the regex was quite hard to do but we were eventually able to do it with recursion.
My group and I encountered problems straight away when starting the assignment. We wondered just how exactly we were going to go about writing these functions. The first one was is_regex that determined whether we were working with a regex or an invalid one. We initially hard-coded the entire function which took around 200 lines. This was very inefficient and had some problems while running. We later discovered that this can we written recursively and can be done in less than 50 lines of code without errors occurring. We then began thinking and approaching the problems in a more recursive manner and tried to incorporate recursion in all of the functions. Permutations of the regex was quite hard to do but we were eventually able to do it with recursion.
Week 8 - Linked lists
This week we were introduced to the concept of linked lists. Linked lists are kind of similar to trees as they have a value while referencing another list. Trees hold a value and reference its "children" thus making these two things similar. Linked lists are important data structures that can be very important in many fields of computer science.
What we have explored in linked lists is the fact that each linked list holds a node called a cargo. This cargo is a value that is stored. The other part of the linked list is the reference to another linked list node. This other node will also hold a cargo as well as another reference until eventually the linked list references None which marks the end of the linked list. As one might predict, this type of referencing and cargo holding can be done recursively. Since the linked list can reference upon itself, recursion makes the traversal of this linked list very simple to do. Another thing to note about linked lists is that they cannot be indexed and must be iterated over in order to go through the list. This is another reason why recursion is such a good method to go about handling linked lists since recursion will iterate until you set a condition that the function must meet. Linked lists is thus interesting and very fun to learn about.
What we have explored in linked lists is the fact that each linked list holds a node called a cargo. This cargo is a value that is stored. The other part of the linked list is the reference to another linked list node. This other node will also hold a cargo as well as another reference until eventually the linked list references None which marks the end of the linked list. As one might predict, this type of referencing and cargo holding can be done recursively. Since the linked list can reference upon itself, recursion makes the traversal of this linked list very simple to do. Another thing to note about linked lists is that they cannot be indexed and must be iterated over in order to go through the list. This is another reason why recursion is such a good method to go about handling linked lists since recursion will iterate until you set a condition that the function must meet. Linked lists is thus interesting and very fun to learn about.
Week 7 - More Recursion!
Week 7 began with more recursion and more function writing in recursion. This time, recursion was done alongside trees. Traversing a tree can be very tiresome if the tree is very big especially when we do not know the exact size of it. This is when recursion comes in and allows us to traverse the tree without having to know how big or small it is.
We applied this idea to trees in this week's CSC148 course. An example of this is comparing the root of a tree to its children. We recursively call the function with every recursive call checking to see whether the root is greater or less than the left or right subtree. With a given condition, the recursive call will stop once we have reached a subtree that is less than that of the root. This is very easy to do with recursion as the function will keep going until the condition is met to stop recursing. When doing recursion like mentioned before, we must keep in mind of a condition to stop the recursion or else the computer will run out of memory and the maximum recursive depth is reached. This condition is usually one that is not met immediately and only reached after going through the tree (answer found in one of the children of the root). This method allows us to not care about the size of the tree as the recursion will do that for us. If we didn't do recursion, it might become extremely difficult to program as the tree is not defined as a finite number.
Recursion is extremely helpful in many situations not just in trees. We however explored trees this week and the traverse of it became much much easier with recursion. Without recursion, tree traversal will be very annoying and hard to do!
We applied this idea to trees in this week's CSC148 course. An example of this is comparing the root of a tree to its children. We recursively call the function with every recursive call checking to see whether the root is greater or less than the left or right subtree. With a given condition, the recursive call will stop once we have reached a subtree that is less than that of the root. This is very easy to do with recursion as the function will keep going until the condition is met to stop recursing. When doing recursion like mentioned before, we must keep in mind of a condition to stop the recursion or else the computer will run out of memory and the maximum recursive depth is reached. This condition is usually one that is not met immediately and only reached after going through the tree (answer found in one of the children of the root). This method allows us to not care about the size of the tree as the recursion will do that for us. If we didn't do recursion, it might become extremely difficult to program as the tree is not defined as a finite number.
Recursion is extremely helpful in many situations not just in trees. We however explored trees this week and the traverse of it became much much easier with recursion. Without recursion, tree traversal will be very annoying and hard to do!
Sunday 2 March 2014
Week 6 - Trees
Week 6 began with the talk about the concept of Trees in computer science. Essentially, Trees are a type of data structure that is used in computer science that is a way to store information. The trees that we did were binary trees starting out with the root with each root having children or leaves called nodes. Each node can have a value and the tree can be traversed recursively. Trees are a very convenient way to store information since the leaves of a binary tree can be treated as two different keys with values. The keys can be ordered so that the side of a tree can be keys with values that are smaller than another side. Thus, traversing a tree becomes very efficient since you can code it recursively to always go towards the smaller side of a tree in order to find the smallest or largest value. Due to the way a binary tree is implemented, you can search for values in the nodes recursively since you know which of the two leaves of a node has a certain property and recursing for long enough will get you the value that you are looking for. Trees can be thought of as a more complex list to store information in.
Like most things in python, trees can be written in a object oriented way. The first step is to initialize your tree by setting up the different nodes and seeing whether you want a binary tree or another type of tree. The rest of the functions can be anything that you want such as the length of your tree. In most cases, the traversing of your tree is done recursively. In the binary tree, each node contains 2 possible keys and you recursively decide which key to take depending on what you want. Eventually the recursion will take you to the value you need within the tree data structure.
Like most things in python, trees can be written in a object oriented way. The first step is to initialize your tree by setting up the different nodes and seeing whether you want a binary tree or another type of tree. The rest of the functions can be anything that you want such as the length of your tree. In most cases, the traversing of your tree is done recursively. In the binary tree, each node contains 2 possible keys and you recursively decide which key to take depending on what you want. Eventually the recursion will take you to the value you need within the tree data structure.
Tuesday 11 February 2014
Week 5 - Assignment 1 and more recursion
The week started off with my group mates and I beginning to work on our TOAH assignment. Upon first seeing the assignment, the instructions were confusing and the overall coding was vague to us. We did research and began to understand more of what the concept of stacking cheese was. It turns out it is a very popular problem and the best proposed solution is an algorithm called the Frame Stewart algorithm. This however did not help us in the coding aspects of the first 2 steps in the assignment. We added methods such as add and remove in order to move the cheese around the stools. We also defined global variables in order to be able to work with our lists globally which was taught to us in class this week as well. We used a dictionary to store our stools as keys and a list of integers for our cheeses that is stacked upon the stools as the value. Our various methods such as add and remove will help in moving cheese from one stool to another while altering the global dictionary that we made which is our actual TOAH. We are still working on our assignment and struggling but progress is being made.
What we did in tutorials this week was tracing and writing recursive functions. Even though recursion was talked about in class for a while, the actual application of it was different from simply listening. Initially, my partner and I were running a recursive function with a for loop. However, we failed to return a value in our second else statement which caused the function to continue without stopping. We expected that the recursive function would only work given that we used a for loop. We were told that we could do it without a loop and with simple if and else statements. We then changed our loop into if statements and got the function to run as it should. Our understanding of recursive has increased after the tutorial.
What we did in tutorials this week was tracing and writing recursive functions. Even though recursion was talked about in class for a while, the actual application of it was different from simply listening. Initially, my partner and I were running a recursive function with a for loop. However, we failed to return a value in our second else statement which caused the function to continue without stopping. We expected that the recursive function would only work given that we used a for loop. We were told that we could do it without a loop and with simple if and else statements. We then changed our loop into if statements and got the function to run as it should. Our understanding of recursive has increased after the tutorial.
Sunday 2 February 2014
Week 4 - Recursion in programming
Week 4 in the course introduced to us the concept of recursions in programming. Recursion was mentioned numerous times throughout csc148 and was shown for the first time this week. Since this year was my first time doing computer science, it is my first time seeing recursive functions. Some people had already seen this type of programming in other languages and programming courses they may have taken. After learning about the concepts behind recursion, i can see how this style of coding can be beneficial to many problems. This style of programming allows for the user to get his answer by running the code until the value that it needs is met. The code will continue to run by itself through the recursive function calling itself. Special precautions must be taken however since in some cases, the code may run infinitely long and thus result in an error. Users using recursion must have statements in their code that tells the recursion to stop running when a certain case is met in order to avoid this error.
Other concepts in computer that was learned this week is creating test cases for our own code. This was done in our tutorial time as we had to write objected oriented programs and then write auto-tests to test our code. This may seem like a waste of time at the moment because our code is short but when our code becomes complex, it will become extremely useful to test it automatically rather than manually. The exercise this week had us explore the exception class and write our own functions that calls upon these functions. This week had been great in learning about recursive functions as well as testing and the exception class.
Other concepts in computer that was learned this week is creating test cases for our own code. This was done in our tutorial time as we had to write objected oriented programs and then write auto-tests to test our code. This may seem like a waste of time at the moment because our code is short but when our code becomes complex, it will become extremely useful to test it automatically rather than manually. The exercise this week had us explore the exception class and write our own functions that calls upon these functions. This week had been great in learning about recursive functions as well as testing and the exception class.
Subscribe to:
Posts (Atom)