You write a function that operates on an arbitrarily large volume of input.
Assuming that there is no bug - that it returns the right values every time (especially no infinite loops) - the only question now remains: how long does it take for the thing to finish?
Time is not an adequate means of measuring that because i could be running it on a better computer than you.
There are 3 ways of expressing time complexity, best case, worst case, and average case, and its performance depends on how "pre-sorted" the input already is and on the property of the algorithm itself.
Let us illustrate that with some sorting algorithms.
selection sort:
The selection sort iterates through every single element starting from the first index of the unsorted section, selecting the minimum, and places it to the front of the queue. Whatever input n is given, it takes n^2 steps to solve it. Therefore, the selection sort, worst case = best case = average case, running time can be expressed as: O(n^2)
quick sort:
the quick sort picks a pivot point and arranges two values at a time into the right order. The time complexity depends largely on how sorted the input already is. Therefore, worst case is O(n^2) if the input is a mess and it operates much like the selection sort. The best case is O(n log n) if the input is already sorted. The average case of the two is simply O(n) by simple algebra.
merge sort:
The merge sort takes a list of values and divide them into single elements, then compared each element with the adjacent list to merge into lists. The same process is repeated regardless of input, therefore, worst case = best case = average case, O(nlogn).
count sort
the count sort algorithm is usually used when the number of elements approximately equals to the number of possible key values.
There is only one case or runtime for count sort, and that is dependent on the size of input n and the number of key elements N
O(N + n)
Thursday 27 March 2014
Monday 24 March 2014
week of march 19, 2014 csc148h1 winter 2014
topic: Runtime analysis:
The binary search algorithm leads to the next question, how do you calculate the runtime of an algorithm?
We use O(n) as a mathematical function to represent the runtime.
The following are example models (which can be used in combination) the time a program could take to complete. Of course, time here is not measured in seconds (what if i have a better computer than you?) but in steps for n inputs.
The bellow mathematical models (stolen from the lecture slides) are very similar to the functions learned in high school math.
All these models (graphically) share the same "break even point" where a given n input produces the same runtime, but each function behaves arbitrarily different as the input becomes larger and larger.
To conclude, given lots and lots of input, with many many different methods of writing the code, the efficiency of the code should be kept in mind with the O(n) models.
The binary search algorithm leads to the next question, how do you calculate the runtime of an algorithm?
We use O(n) as a mathematical function to represent the runtime.
The following are example models (which can be used in combination) the time a program could take to complete. Of course, time here is not measured in seconds (what if i have a better computer than you?) but in steps for n inputs.
The bellow mathematical models (stolen from the lecture slides) are very similar to the functions learned in high school math.
All these models (graphically) share the same "break even point" where a given n input produces the same runtime, but each function behaves arbitrarily different as the input becomes larger and larger.
To conclude, given lots and lots of input, with many many different methods of writing the code, the efficiency of the code should be kept in mind with the O(n) models.
constant:
c
2
R
+
(some p ositive numb er)
logarithmic:
c
log
n
linear:
cn
(probably not the same
c
)
quadratic:
cn
2
cubic:
cn
3
exp onential:
c
2
n
horrible:
cn
n
or
cn
!
Where n is the input, and O(n) represent the "Worst case running time" of the code.
week of march 12, 2014 csc148h1 winter 2014
Topic(s): binary search
Assume a list in already-sorted order.
If you were asked to find a value within the list, how would you do it?
The simplest way would be to iterate through every single value in the list and check each value and return iff there is a value that match.
The question now becomes: how efficient is that?
If you were given a ridiculously long list and the target value is near the end of that ridiculously long list, that would take forever to such a point that you would doubt if your code will ever terminate.
There does exist a faster way of retrieving that value (providing that the list is sorted in order) - binary search.
The though process of it is that: assume the list in sorted order, you find the middle most value of the list, if the middle value is not the target value, you check whether it is bigger or smaller than the target value and ignore the other half of the list. The same process is recursed with the now half-sized list - find middle most value, if it != the target value, begin again on the half that contains the target value.
The complexity of this search sequence pays off in terms of time efficiency since the computer is only working with (1/2)^n of the content at all times.
Assume a list in already-sorted order.
If you were asked to find a value within the list, how would you do it?
The simplest way would be to iterate through every single value in the list and check each value and return iff there is a value that match.
The question now becomes: how efficient is that?
If you were given a ridiculously long list and the target value is near the end of that ridiculously long list, that would take forever to such a point that you would doubt if your code will ever terminate.
There does exist a faster way of retrieving that value (providing that the list is sorted in order) - binary search.
The though process of it is that: assume the list in sorted order, you find the middle most value of the list, if the middle value is not the target value, you check whether it is bigger or smaller than the target value and ignore the other half of the list. The same process is recursed with the now half-sized list - find middle most value, if it != the target value, begin again on the half that contains the target value.
The complexity of this search sequence pays off in terms of time efficiency since the computer is only working with (1/2)^n of the content at all times.
week of march 5, 2014 csc148h1 winter 2014
Topic: Linked Lists.
In this week, linked lists are introduced as a new ADT.
According to wikipedia:
a linked list is a data structure consisting of a group of nodes which together represent a sequence.
a linked list is created as a form of a class similar to other forms of Object Oriented Programming.
In the initializer, what is created is a variable, a variable with list as a beginning item and it has a reference to the next list, and that has a reference to the next list, and so on... The linked list shares a strong similarity with the already-learned queue ADT, in a sense that inserting values into the linked list is done in chronological order, one value after the other. The first noticeable distinction is that, while a queue will only remember the top most value in its chain, the linked list can be worked on in various ways: insert, delete, reverse order.
The structure of the linked list is also unique in a sense that each item is represented by a list. The following is the skeletal structure of a linked list: [list a] -> [list b] -> [list c]....
each item contains items, and has a reference to the next item.
Compared to other ADT's, the linked list shares the property of one item referencing to the next item like a tree, except there can only be one child, and it is also like a tuple, where it can only be operated one item at a time.
In this week, linked lists are introduced as a new ADT.
According to wikipedia:
a linked list is a data structure consisting of a group of nodes which together represent a sequence.
a linked list is created as a form of a class similar to other forms of Object Oriented Programming.
In the initializer, what is created is a variable, a variable with list as a beginning item and it has a reference to the next list, and that has a reference to the next list, and so on... The linked list shares a strong similarity with the already-learned queue ADT, in a sense that inserting values into the linked list is done in chronological order, one value after the other. The first noticeable distinction is that, while a queue will only remember the top most value in its chain, the linked list can be worked on in various ways: insert, delete, reverse order.
The structure of the linked list is also unique in a sense that each item is represented by a list. The following is the skeletal structure of a linked list: [list a] -> [list b] -> [list c]....
each item contains items, and has a reference to the next item.
Compared to other ADT's, the linked list shares the property of one item referencing to the next item like a tree, except there can only be one child, and it is also like a tuple, where it can only be operated one item at a time.
Friday 28 February 2014
week of feburary 26, 2014 csc148h1 winter 2014 Assigned topic: Recursion.
Assigned topic: Recursion.
At this point, i have had my first exposure to recursion, a powerful technique in computer programming.
According to wikipedia,
"Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration)."
Simply put, recursion technique is seen when the function being run calls itself within its own code (because the function calls itself to start its work again on the given input).
The following code illustrates an example of recursion (stolen from week 4 lecture slides):
def rec_max(L):
return max([rec_max(x) if isinstance(x, list) else x for x in L])
This function sorts through a given list input and returns the greatest value within the list.
The most important component of any recursive call is its "base case." This is the condition in which the function has to reach so that it terminates and stops running. Otherwise, python will return a "recursion exceeds maximum depth" error.
The closest analogy that comes to my mind is the concept of a "while loop," because it is also an iteration technique that keeps running and running until it reaches a condition in which it stops. Likewise, the while loop faces the same problem of an "infinite loop" if its exit condition is not well defined.
So, it begs the question, what is the point of recursion when there already exists a similar technique that does the same job?
Refer to the rec_max(L) function above.
If the given input is a list of [1, 2, 3, 4, 5], the function would return 5. A very simple test case which either the for loop or while loop can easily accomplish.
However, what if the given input is something like: [1, [2, 3, 4], 5]?
A for loop, for example, would iterate through: 1, the inner list, then 5, and return 5, with no regard for the content of the inner list - for its assigned objective does not directly deal with such a disposition.
Even if you were to install a command to the effect of "if you encounter another list, start the iteration again," it is still not going to account for an input which has 99 layers (an exaggerated point) of nested lists.
This is where recursion comes in.
the 1 line code above in english means "if you encounter another list, start the iteration again." The code re-executes itself given the condition is met. In the example of the nested list, the only (known) way to dealing with an ADT that contains layers and layers of variables is to start the count again, as if you were to do it manually.
This is where recursion becomes indispensable: when the input ADT consists of entries that are not of the same format.
Recursion, at its base definition, is a form of loop. A loop is a command to the computer to execute code over and over again until the condition is met. However, recursion allows itself to start the iteration again if it becomes necessary. But, in general, a recursion should always be used when a big problem needs to be broken down into small problems and solved step by step. ex. decomposing a big list into smaller lists and iterating through each item to return the desired entry.
In brief, recursion is a powerful tool in computer science that allows the computer to solve complicated problems by breaking it down into smaller ones via. starting the iteration again - very useful when the given input ADT is not of a consistent format.
At this point, i have had my first exposure to recursion, a powerful technique in computer programming.
According to wikipedia,
"Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration)."
Simply put, recursion technique is seen when the function being run calls itself within its own code (because the function calls itself to start its work again on the given input).
The following code illustrates an example of recursion (stolen from week 4 lecture slides):
def rec_max(L):
return max([rec_max(x) if isinstance(x, list) else x for x in L])
This function sorts through a given list input and returns the greatest value within the list.
The most important component of any recursive call is its "base case." This is the condition in which the function has to reach so that it terminates and stops running. Otherwise, python will return a "recursion exceeds maximum depth" error.
The closest analogy that comes to my mind is the concept of a "while loop," because it is also an iteration technique that keeps running and running until it reaches a condition in which it stops. Likewise, the while loop faces the same problem of an "infinite loop" if its exit condition is not well defined.
So, it begs the question, what is the point of recursion when there already exists a similar technique that does the same job?
Refer to the rec_max(L) function above.
If the given input is a list of [1, 2, 3, 4, 5], the function would return 5. A very simple test case which either the for loop or while loop can easily accomplish.
However, what if the given input is something like: [1, [2, 3, 4], 5]?
A for loop, for example, would iterate through: 1, the inner list, then 5, and return 5, with no regard for the content of the inner list - for its assigned objective does not directly deal with such a disposition.
Even if you were to install a command to the effect of "if you encounter another list, start the iteration again," it is still not going to account for an input which has 99 layers (an exaggerated point) of nested lists.
This is where recursion comes in.
the 1 line code above in english means "if you encounter another list, start the iteration again." The code re-executes itself given the condition is met. In the example of the nested list, the only (known) way to dealing with an ADT that contains layers and layers of variables is to start the count again, as if you were to do it manually.
This is where recursion becomes indispensable: when the input ADT consists of entries that are not of the same format.
Recursion, at its base definition, is a form of loop. A loop is a command to the computer to execute code over and over again until the condition is met. However, recursion allows itself to start the iteration again if it becomes necessary. But, in general, a recursion should always be used when a big problem needs to be broken down into small problems and solved step by step. ex. decomposing a big list into smaller lists and iterating through each item to return the desired entry.
In brief, recursion is a powerful tool in computer science that allows the computer to solve complicated problems by breaking it down into smaller ones via. starting the iteration again - very useful when the given input ADT is not of a consistent format.
Thursday 13 February 2014
week of february 12, 2014 csc148h1 winter 2014
This week was tough, >10 hour spent finishing up a1.
This is the first time in this course i have been implementing recursion, and i have implement it in two ways:
1) using recursion to calculate i, the integer constant 1<=i<n in the M(n) function. M(n) is function that generates the number of moves needed to finish a stool of n cheeses. There is always an i that minimizes the number of moves you need to make. What i did was that i used a for loop to iterate i 1<i<n and plugged into the M(n) equation. The M(n) values are then appended into an empty list. Then the appendix of the list is returned to produce i. I feel almost a little proud because they say that this is the hardest part of the assignment and i finished this function in <20 minutes.Most people tried to return --- in 1 line, but that was simply too complicated for python to operate. Instead, i created a helper function to be called within my main function, and that worked without bugs.
2) the second implementation of recursion was a bit unlike to what i understand recursion to be. if number of cheeses > 1, the order of the stools of the parameters in the move function are shuffled in different orders. again, like M(n), i called a 3-stool move function within my 4-stool move function, this is because when there are cheeses on the intermediate stool, there are only 3 stools you can use to work with (the origin stool is being occupied by the longer cheeses). The greatest challenge of this part is working with parameters i have not defined, tracing through where the recursion is working on, and coming up with a complete algorithm that moves the cheeses when moved over and over again.
All in all, i feel very accomplished that i have learned how to adequately implement recursion, however i do hope that the test will not be as difficult. =(
This is the first time in this course i have been implementing recursion, and i have implement it in two ways:
1) using recursion to calculate i, the integer constant 1<=i<n in the M(n) function. M(n) is function that generates the number of moves needed to finish a stool of n cheeses. There is always an i that minimizes the number of moves you need to make. What i did was that i used a for loop to iterate i 1<i<n and plugged into the M(n) equation. The M(n) values are then appended into an empty list. Then the appendix of the list is returned to produce i. I feel almost a little proud because they say that this is the hardest part of the assignment and i finished this function in <20 minutes.Most people tried to return --- in 1 line, but that was simply too complicated for python to operate. Instead, i created a helper function to be called within my main function, and that worked without bugs.
2) the second implementation of recursion was a bit unlike to what i understand recursion to be. if number of cheeses > 1, the order of the stools of the parameters in the move function are shuffled in different orders. again, like M(n), i called a 3-stool move function within my 4-stool move function, this is because when there are cheeses on the intermediate stool, there are only 3 stools you can use to work with (the origin stool is being occupied by the longer cheeses). The greatest challenge of this part is working with parameters i have not defined, tracing through where the recursion is working on, and coming up with a complete algorithm that moves the cheeses when moved over and over again.
All in all, i feel very accomplished that i have learned how to adequately implement recursion, however i do hope that the test will not be as difficult. =(
Sunday 9 February 2014
week of February 5, 2014 csc148h1 winter 2014
This week, we were introduced to some applications of recursion and unit test.
By comparing lecture slides to our assignment 1, towers of anne hoy, it seems like our objective is to create an automated application that solves a problem by implementing recursion.
If all the instructions can be defined as a general formula instead of lines and lines of code on how to move cheeses around, the following can be an example of how such an application can be implemented:
1. move all but the bottom cheese to the source to intermediate stool.
2. move the bottom cheese from source to intermediate stool.
3. move all but the bottom cheese from the intermediate stool to the destination stool.
If all these commands are implemented into code as a base case, then calling the function again and again until it is done will create an automated "problem solver" to tower of anne hoy.
Unittest, on the other hand, is another form of automation. It provides a series of test cases to run to test the specific functions built within the test file, and executes them one by one and reports back the errors found. I tend of think of unittest as a general solution that can be used to test many different instances of the same code - input case, return result.
In brief, recursion and unittest are both powerful tools of automation that breaks down a long and complex task down to easy steps and implement until the job is done.
By comparing lecture slides to our assignment 1, towers of anne hoy, it seems like our objective is to create an automated application that solves a problem by implementing recursion.
If all the instructions can be defined as a general formula instead of lines and lines of code on how to move cheeses around, the following can be an example of how such an application can be implemented:
1. move all but the bottom cheese to the source to intermediate stool.
2. move the bottom cheese from source to intermediate stool.
3. move all but the bottom cheese from the intermediate stool to the destination stool.
If all these commands are implemented into code as a base case, then calling the function again and again until it is done will create an automated "problem solver" to tower of anne hoy.
Unittest, on the other hand, is another form of automation. It provides a series of test cases to run to test the specific functions built within the test file, and executes them one by one and reports back the errors found. I tend of think of unittest as a general solution that can be used to test many different instances of the same code - input case, return result.
In brief, recursion and unittest are both powerful tools of automation that breaks down a long and complex task down to easy steps and implement until the job is done.
Subscribe to:
Posts (Atom)