This is the last entry in this wonderful slog.Well, graded entry. I might continue this over the holidays if I am permitted.
This has been a useful tool to increase my understanding of concepts in class. It is said that nothing gives you more understanding than explain a concept and this is what this slog forces you to do. I had to do some research to make sure I understood the concepts so I wouldn't write rubbish(hopefully I accomplished this!)
I enjoyed the course, put in a lot of hours understanding concepts and practising coding and feel I am prepared(almost) for the finals!
Wish me luck everyone!
P.Jiggly
Friday 6 December 2013
I've got this sorted! Sort of...
In this post, I am going to talk about different sorting algorithms and compare their effiencency using Big-O notation. Big-O classifies algorithms according to how their processing time changes (or use of space)to changes in input size.
We learned about three different sorting algorithms, selections sort, quick
sort, and merge sort.
In selection sort you iterate through a given list looking for the minimum element and place that element at the first position. You do this again and place the next minimum next to the previous until you reach the end of the list. Since you need go through list of len n to find the min element and do this n-1 times, the Big-O of selction sort is O(n^2).
For example, given a list L = [4, 3, 1] the first minimum of the list would be 1. That would be place at L[0] to give [1,4, 3] . The next search will be in the remaining unsorted part of the list. The mimimum of 3 will be placed st L[1] to give the final sorted list of [1,3,7].
Quick sort can be implimented using recursion. It involves by choosing an item in the list as a pivot point and reording the list around that point much like how items are ordered in a binary search tree. Items creater that the pivot item go to the right and items less than to the left. After the first recursive call, a new pivot point is chosen on point side and the process is repeated. This occurs until the list is sorted. Its Big-O is O(nlogn) like a binary search tree.
Merge sort can also be implemented recursively. This algorithm invloves splitting the list in half until it is a single element list and sorted the list. Its Big-O is O(nlogn) as well.
There are cases when merge sort will be more efficient than quick sort(and vice versa!) In very rare cases , quick sorts BigO is O(n^2).due to the pivot positon. If the the pivot chosen is always the next smallest element, it becomes equivalent to Insertion sort.
Any more insight into why merge or quick sort is more efficienct in certain cases?
In selection sort you iterate through a given list looking for the minimum element and place that element at the first position. You do this again and place the next minimum next to the previous until you reach the end of the list. Since you need go through list of len n to find the min element and do this n-1 times, the Big-O of selction sort is O(n^2).
For example, given a list L = [4, 3, 1] the first minimum of the list would be 1. That would be place at L[0] to give [1,4, 3] . The next search will be in the remaining unsorted part of the list. The mimimum of 3 will be placed st L[1] to give the final sorted list of [1,3,7].
Quick sort can be implimented using recursion. It involves by choosing an item in the list as a pivot point and reording the list around that point much like how items are ordered in a binary search tree. Items creater that the pivot item go to the right and items less than to the left. After the first recursive call, a new pivot point is chosen on point side and the process is repeated. This occurs until the list is sorted. Its Big-O is O(nlogn) like a binary search tree.
Merge sort can also be implemented recursively. This algorithm invloves splitting the list in half until it is a single element list and sorted the list. Its Big-O is O(nlogn) as well.
There are cases when merge sort will be more efficient than quick sort(and vice versa!) In very rare cases , quick sorts BigO is O(n^2).due to the pivot positon. If the the pivot chosen is always the next smallest element, it becomes equivalent to Insertion sort.
Any more insight into why merge or quick sort is more efficienct in certain cases?
Saturday 30 November 2013
Reading and Understanding Recursive Functions
Writing a recursive code is one thing but understanding someone else's code can be really confusing. This is something I struggled with on Term Test 1. I saw the first question, the several lines of code doing something funky, tried to make sense of it all but realised "Aint nobody got time for that". After the exam I got some useful tips from Danny and I realised I was confusing my self.
I had already figured out what the base case was doing but each time I called the recursive function in my mind, I started ALL the way from the base case and worked up to the current call. This was wasting a lot of time and was unnecessary as I already knew what the base case produced.Now when I see a recursive code, I calculate the value of the base case and input that into each call. Likewise for the previous call.
For example, in Term Test 1
s(1) returns (1,1)
When s(2) is called, the for loop evaluates the expression (2 * s(1)[0]+ 2**(1-1),1 )
I already know that s(1) is (1,1) therefore s(1)[0] is 1 and the whole expression evaluates to (3,1)
When s(3) is called the first run of the for loop evaluates the expression (2 * s(2)[0] + 2**(1-1),1)
I already know that s(2) is (3,1) therefore s(2)[0] is 3 and the whole expression evaluates to (7,1)
Plugging the previously calculated run of the recursive code keeps things from getting unnecessarily complicated.This has helped me node get lost in the code.
Any other tips to keep your sanity when reading recursive codes?
P.Jiggly
I had already figured out what the base case was doing but each time I called the recursive function in my mind, I started ALL the way from the base case and worked up to the current call. This was wasting a lot of time and was unnecessary as I already knew what the base case produced.Now when I see a recursive code, I calculate the value of the base case and input that into each call. Likewise for the previous call.
For example, in Term Test 1
def s(n: int) -> tuple:
if n == 1:
return (1, 1)
else:
return min([(2 * s(n - i)[0] + 2**i - 1, i) for i in range(1,n)]) #upper limit of range not evaluated
When s(2) is called, the for loop evaluates the expression (2 * s(1)[0]+ 2**(1-1),1 )
I already know that s(1) is (1,1) therefore s(1)[0] is 1 and the whole expression evaluates to (3,1)
When s(3) is called the first run of the for loop evaluates the expression (2 * s(2)[0] + 2**(1-1),1)
I already know that s(2) is (3,1) therefore s(2)[0] is 3 and the whole expression evaluates to (7,1)
Plugging the previously calculated run of the recursive code keeps things from getting unnecessarily complicated.This has helped me node get lost in the code.
Any other tips to keep your sanity when reading recursive codes?
P.Jiggly
Writing Recursive Functions
As mentioned in a previous post, a recursive function is a function that calls itself. This post will focus on writing recursive functions.The logic behind the function is pretty intuitive but I have found knowing where to start when writing the function to be challenging. Danny gave me some really helpful tips for handling recursive function and with some practice, I was able to come about my own way.
When writing recursive codes, I always start with a base case that does not require recursion. I choose a base case based on the task I'm trying to do(and what I need to know). I then split the more complicated cases into pieces the base case can handle.
For example, the function below calculates the sum of the elements in a list.
The simplest cases will be an empty list and a list of a single length. In those cases the function will simply return 0 or the element of the list its self. I need to know the elements of the list so I can add them. Splitting the list into individual elements lets me know the elements so i can add them.
def summed_list(L:list) ->int:
'''Returns the sum of the elements of a list. If empty list, returns zero.'''
#note this function does not need to be done recursively
if L ==[]: #base case1
return 0
elif len(L) ==1: #base case 2
return L[0]
else:
return summed_list(L[0:1]) + summed_list(L[1:len(L)]) #split complicated cases into case base case can handle i.e. single length list
If I wanted to calculate the sum of a nested list, I need to know if the element is itself a list so I can handle that. The base case here then must be when it is not a list(simplest). When it is not a nested list, I need to find each element and add them to another list that will be summed. If it is a list, iterate through that list as well as per the base case.
def summed_nested_list(L:list)->int:
'''Returns the sum of the element in a possibly nested list. If empty, returns zero.'''
return sum([summed_nested_list(x) if isinstance(x,list) else x for x in L])
So far, creating base cases based on the task and splitting the rest of the problem into chunks the base case can handle has made it a lot easier to write recursive codes.
Any other suggestions?
P.Jiggly
When writing recursive codes, I always start with a base case that does not require recursion. I choose a base case based on the task I'm trying to do(and what I need to know). I then split the more complicated cases into pieces the base case can handle.
For example, the function below calculates the sum of the elements in a list.
The simplest cases will be an empty list and a list of a single length. In those cases the function will simply return 0 or the element of the list its self. I need to know the elements of the list so I can add them. Splitting the list into individual elements lets me know the elements so i can add them.
def summed_list(L:list) ->int:
'''Returns the sum of the elements of a list. If empty list, returns zero.'''
#note this function does not need to be done recursively
if L ==[]: #base case1
return 0
elif len(L) ==1: #base case 2
return L[0]
else:
return summed_list(L[0:1]) + summed_list(L[1:len(L)]) #split complicated cases into case base case can handle i.e. single length list
If I wanted to calculate the sum of a nested list, I need to know if the element is itself a list so I can handle that. The base case here then must be when it is not a list(simplest). When it is not a nested list, I need to find each element and add them to another list that will be summed. If it is a list, iterate through that list as well as per the base case.
def summed_nested_list(L:list)->int:
'''Returns the sum of the element in a possibly nested list. If empty, returns zero.'''
return sum([summed_nested_list(x) if isinstance(x,list) else x for x in L])
So far, creating base cases based on the task and splitting the rest of the problem into chunks the base case can handle has made it a lot easier to write recursive codes.
Any other suggestions?
P.Jiggly
Monday 14 October 2013
The Journey Begins!
Today, I begin my journey into a land I nor any of my family has ever ventured. The land of CSC148. I saw the citygates of this land at a distance 3 years ago when I stayed in the land of CSC108 but my stay was a rough and bumpy one. I was young, I was not the Sir P.Jiggly I am today and I could not appreciate all the beauty and wonders it had to offer nor did I particularly care. Ah, the days of my youth. What had occured? What tales did I learn? It is so blurry I cannot remember the events that had happened.
I hope to make this journey a memorable one.The land is ruled by a King named Heap. He is a powerful man but I have heard he is also just.
I have heard strange and scary tales about this land by my brethren that have visited. Some went and returned changed. For then better , but sometimes for the worse. Some visited for a few days but quickly fled to CSC108 while the others ran like mad-men from the land of CSC forever, always looking behind their shoulders . They swear they are chased by some loop demon that will never leave them be.
Am I frightened? Yes of course. But I am also very excited. Let's see what becomes of me at the end of this journey.
Sir P. Jiggly
I hope to make this journey a memorable one.The land is ruled by a King named Heap. He is a powerful man but I have heard he is also just.
I have heard strange and scary tales about this land by my brethren that have visited. Some went and returned changed. For then better , but sometimes for the worse. Some visited for a few days but quickly fled to CSC108 while the others ran like mad-men from the land of CSC forever, always looking behind their shoulders . They swear they are chased by some loop demon that will never leave them be.
Am I frightened? Yes of course. But I am also very excited. Let's see what becomes of me at the end of this journey.
Sir P. Jiggly
Recursion
Today's post is on recursion! This was a mind screw for me at first but now I get the concept(and the coding!) In Python recursion involves a function calling itself. Like while or for loops, recursion can be controlled.
Recursive functions can accomplish the same things as loops. They require more memory and are less efficient in a lot of cases. Then why learn / use them in the first place right? There ARE some cases when these functions are in fact appropriate and more effiencient. When solving complex problems, a recursive functions can break down the steps in to smaller more manageable ones(less mind screwing) and make it easier and simpler code.
P.Jiggly
Recursive functions can accomplish the same things as loops. They require more memory and are less efficient in a lot of cases. Then why learn / use them in the first place right? There ARE some cases when these functions are in fact appropriate and more effiencient. When solving complex problems, a recursive functions can break down the steps in to smaller more manageable ones(less mind screwing) and make it easier and simpler code.
P.Jiggly
Object-Oriented Programming
This post is on object -oriented programming. The previously learned way of program invloving procedures or functions is called procedural programming.Object-oriented programming is a way of programming that is centred on creating objects. All objects have data inside them called attributes and procedures of functions called methods. A class is a collection of objects with similar attributes and fuctions. In Python, an objects attributes and methods are specified by a class. Therefore, a class can also be seen as a model or blue-print for creating that object.
Object-oriented is more efficient than procedural programming. It makes it easier to add or modify functions by simply storing them in a class(instead of having to rewrite all your code!)
P.Jiggly
Object-oriented is more efficient than procedural programming. It makes it easier to add or modify functions by simply storing them in a class(instead of having to rewrite all your code!)
P.Jiggly
Subscribe to:
Posts (Atom)