In the past few weeks we have revisited some previously learned sorting algorithms: Selection, Insertion and Bubble sorts and also learned some new sorts like Quick, Merge and Python's built in Timsort.
Rather than just learning the concept and implementations of these algorithms, we looked instead at the 'efficiency' of these algorithms. Efficiency is, in essence, measured in the time and space complexity of the algorithms. We focused on time complexity - the typical run-time of the algorithm and specifically, the upper bound on this run-time (the worst case, denoted using Big-Oh).
We saw that bubble and insert have the smallest time complexity in the best case (the case of an already, or nearly, sorted list) of big O of n, or O(n). But, in the worst case (a reverse sorted list) they fare worst with a time complexity of O(n^2)
Selection sort, as expected, came out at bottom with best and worst case time efficiencies of O(n^2).
Having worked with these algorithms before, the results weren't all too surprising. What was interesting though was seeing how small changes in their Python implementations could speed up their runtimes (though time complexity remains the same). For instance, calls to repeated calls to len (in loops) would slow down the runtime but this could be remedied by introducing a temporary variable to only have to call len once.
Other tweaks to improve runtime were less useful: Trying to end bubble sort early by seeing if the last scan of the list had any swaps didn't cause a significant boost to runetime.
Ofcourse, the most interesting part of the last few weeks has been working with mergesort and quicksort. I will breifly re-iterate their algorithms in my own words and the comment on any interesting aspects of them.
Both of these new algorithms are recursive. Mergesort cuts the list to be sorted into two halves, then recursively calls mergesort on the halves and finally, 'merges' the two halves back into a single list. The splitting into two halves has a time complexity of log(n) and the merge operation runs in time complexity of n. So altogether mergesort runs in best and worst case of O(nlog(n)). Like the previous algorithms, we also explored ways to speed up mergesorts runtime: By continually updating the original list and not replacing it, we were able to significantly cut down average runtime (though still O(nlog(n) ofcourse).
Quicksort first chooses a 'pivot' (any item in the list) and then splits the list into two galves: items bigger than pivot and smaller than pivot. It then (recursively) calls quicksort on the two sub lists. Quicksort is nearly identical in time complexity to mergesort except in the worst case it has a time complexity in O(n^2). We explored a similar improvement technique as the one to mergesort but it yeilded no benefits for quicksort.
All in all, this part of the course really helped solifidy my understanding of these sorting algorithms - we really got into the fundamental workings of them, took them apart, analysed them, compared them to others and explored techniques of improving them.
Thursday 27 March 2014
Tuesday 11 March 2014
Linked Structures
The central topic of Week 8 has been linked lists and a variant of binary trees - binary search trees (BSTs). Both these data structures are related by one particular property: each node (or element) of these data structures contains a reference to one (in the case of linked lists) or more (two in the case of BSTs) 'child' node(s).
For linked lists, we considered two definitions:
1. Lists containing an item (head) and the remaining linked list (rest).
2. As individual objects (nodes) containing some value and a reference to another node.
Though we saw in class that both these definitions employ similar functions - some functions are implemented quite differently, however the general structure/usage of linked lists stays the same.
Speaking of linked list usage, one interesting point mentioned in lecture this week was different usages of prepend(head).
In past weeks you would make a copy of the linked list and assign this copy as 'rest'. Then 'head' would become the new head being prepended. However, an alternative implementation was to make a new linked list in the prepend function where 'head' is the new head and 'rest' is self. Then this new linked list was returned. This seems a lot cleaner but requires the client to update their linked list every time prepend it called. I.e. x.prepend(1) becomes x = x.prepend(1).
Besides linked lists we looked at BSTs, a variant of binary trees already seen in past weeks. We looked at BSTs of the following kind: binary trees with the constraint that the left child is smaller than the root and the right child is larger than the root.
It was claimed that this would allow for more efficient searches. At first I didn't see how this claim was true, but thinking recursively I realized that when we say the left child is always smaller than the root, the entire left subtree will contain elements smaller than root and vice versa for the right child/subtree.
This all relies on the recursive insert(item) function that ensures that the constraint holds. Observing the way insert worked really helped solidify my understanding of recursion in binary trees and now we have a neat O(log n) search algorithm to make use of!
For linked lists, we considered two definitions:
1. Lists containing an item (head) and the remaining linked list (rest).
2. As individual objects (nodes) containing some value and a reference to another node.
Though we saw in class that both these definitions employ similar functions - some functions are implemented quite differently, however the general structure/usage of linked lists stays the same.
Speaking of linked list usage, one interesting point mentioned in lecture this week was different usages of prepend(head).
In past weeks you would make a copy of the linked list and assign this copy as 'rest'. Then 'head' would become the new head being prepended. However, an alternative implementation was to make a new linked list in the prepend function where 'head' is the new head and 'rest' is self. Then this new linked list was returned. This seems a lot cleaner but requires the client to update their linked list every time prepend it called. I.e. x.prepend(1) becomes x = x.prepend(1).
Besides linked lists we looked at BSTs, a variant of binary trees already seen in past weeks. We looked at BSTs of the following kind: binary trees with the constraint that the left child is smaller than the root and the right child is larger than the root.
It was claimed that this would allow for more efficient searches. At first I didn't see how this claim was true, but thinking recursively I realized that when we say the left child is always smaller than the root, the entire left subtree will contain elements smaller than root and vice versa for the right child/subtree.
This all relies on the recursive insert(item) function that ensures that the constraint holds. Observing the way insert worked really helped solidify my understanding of recursion in binary trees and now we have a neat O(log n) search algorithm to make use of!
Sunday 2 March 2014
Definition of Recursion: See "Recursion".
The past few weeks of CSC148 have involved a Mid-Term, the due date of Assignment 1, some interesting labs on recursive data structures (trees, linked lists) and the beginning of Assignment 2 part 1. I think now is a good time to reflect back on one of the core concepts that has permeated all the topics of the past few weeks: Recursion.
In past weeks' SLOGs, I have discussed some of the introductory concepts of recursion - from base and recursive cases to modelling a problem recursively. In what follows, I will seek to elaborate more on this latter topic as well as some applications of recursion that I found interesting.
The tour of four stools in our Tours of Hanoi assignment was the first major application of recursion - besides lecture/labs - we had to do individually. The first step of the algorithm obviously recursive (it was in the assignment handout!) - we had to attain a value for 'i' which would allow the rest of the algorithm to run most effectively. I toyed with this a bit until I decided to implement this recursive algorithm in a brute force manner - I had my program shift through all legitimate 'i' values until an optimal one was found. The recursive call here was simple: it was written write in the formula!
Next we had the actual four peg algorithm itself. With the value of 'i' selected, these 3 recursive calls worked to shift the blocks of cheese to the destination. Here is where I saw the key to the entire algorithm: the three peg algorithm was simply a sub-part of the four peg algorithm. Once I moved n-i cheeses to an intermediate stool, I called the three peg algorithm to do the work of bringing the i cheeses to the destination. In essence, I thought of it as 'recursion within 'recursion'. "Recurception" if you will ;)
Though this seems overwhelming for an introductory recursion assignment, struggling through it really helped to see the way recursion provided a neat and intuitive solution to an otherwise difficult problem.
Alas, my thirst for more recursive insights was not quenched and immediately began thinking of other problems that could have very elegant recursive solutions. What came to mind was the fundamental theorem of arithmetic: that every integer greater than 1 can be written as a unique factorization of prime numbers. I decided to put my recursive knowledge to the test and design an algorithm to produce the prime factors of some n.
First I wrote a function to generate prime numbers from 1 to n and then I began work on the recursive function. The algorithm is rather simple and elegant with recursion: Loop through the list of generated primes and if a prime divides n, add it to the list of factors and then recursively call the algorithm to generate the prime factors of what is left when that prime factor divides n. And so, a list of prime factors for some n are generated.
This algorithm really helped to affirm my grasp of the recursion learned so far: You choose your base case and recursive call - trace a few simple cases and then hope for the best! Of course, a great deal of thought needs to go into choosing your recursive calls but once you have it for one, you may assume it will work for the cases that will follow - a lot like inductive reasoning!
In past weeks' SLOGs, I have discussed some of the introductory concepts of recursion - from base and recursive cases to modelling a problem recursively. In what follows, I will seek to elaborate more on this latter topic as well as some applications of recursion that I found interesting.
The tour of four stools in our Tours of Hanoi assignment was the first major application of recursion - besides lecture/labs - we had to do individually. The first step of the algorithm obviously recursive (it was in the assignment handout!) - we had to attain a value for 'i' which would allow the rest of the algorithm to run most effectively. I toyed with this a bit until I decided to implement this recursive algorithm in a brute force manner - I had my program shift through all legitimate 'i' values until an optimal one was found. The recursive call here was simple: it was written write in the formula!
Next we had the actual four peg algorithm itself. With the value of 'i' selected, these 3 recursive calls worked to shift the blocks of cheese to the destination. Here is where I saw the key to the entire algorithm: the three peg algorithm was simply a sub-part of the four peg algorithm. Once I moved n-i cheeses to an intermediate stool, I called the three peg algorithm to do the work of bringing the i cheeses to the destination. In essence, I thought of it as 'recursion within 'recursion'. "Recurception" if you will ;)
Though this seems overwhelming for an introductory recursion assignment, struggling through it really helped to see the way recursion provided a neat and intuitive solution to an otherwise difficult problem.
Alas, my thirst for more recursive insights was not quenched and immediately began thinking of other problems that could have very elegant recursive solutions. What came to mind was the fundamental theorem of arithmetic: that every integer greater than 1 can be written as a unique factorization of prime numbers. I decided to put my recursive knowledge to the test and design an algorithm to produce the prime factors of some n.
First I wrote a function to generate prime numbers from 1 to n and then I began work on the recursive function. The algorithm is rather simple and elegant with recursion: Loop through the list of generated primes and if a prime divides n, add it to the list of factors and then recursively call the algorithm to generate the prime factors of what is left when that prime factor divides n. And so, a list of prime factors for some n are generated.
This algorithm really helped to affirm my grasp of the recursion learned so far: You choose your base case and recursive call - trace a few simple cases and then hope for the best! Of course, a great deal of thought needs to go into choosing your recursive calls but once you have it for one, you may assume it will work for the cases that will follow - a lot like inductive reasoning!
Sunday 9 February 2014
A Look Back at Week 5: Scopes and Assignment 1!
Hello readers!
We're into week 5, steam-rolling through the winter term and the assignments and tests are sure piling up! The latest (well first really) CSC148 assignment is based on the famous Towers of Hanoi game. Instead of the usual 3 pegs, our version has us dealing with 4.
What's really interesting about this is that the most optimal solution to Towers of Hanoi with more than 4 pegs has yet to be proven! Many great minds have probably tried solving this problem and it feels great knowing that we are going through the same thinking process they went through!
I chose to work alone as I usually do for CS assignments; though I was first a bit frustrated with understanding how assignment one was meant to be structured, I did eventually figure it out (thanks to everyone on the Piazza forums!). It was nice to see how the different topics we discussed in class so far (inheritance, basic data structures, recursion etc.) fit together to make up a working solution.
Although I haven't yet managed to find the most optimal algorithm for solving the 'four stool (or peg)' Towers of Hanoi game, I have come quite close to it. Hopefully, I will discuss my solution (and alternatives) more thoroughly after the assignment deadline has passed ( to give everyone a fair chance of course :-] ) - but the hardest part by far has been figuring out what values of 'i' to use; I think the answer to the most optimal solution lies there - though I haven't found it yet.
Besides the assignment, the other highlight of the week was the lecture topic on scope. This is yet another familiar topic for me though I haven't used it much in the past. My past instructors told us to avoid using global variables (most of the time at least) as they can make code harder to understand and can start polluting namespace.
Is was a little difficult, but after looking through the examples (of predicting outcomes) in lecture, I was able to refresh most of my memory on this topic.
I've also finally had a chance to read through some other Slogger's posts. A couple that really caught my eye were: cynnGAH's Slog (http://148journey.blogspot.ca/) and Ada Ene's Slog (http://adauoftcsc148.blogspot.ca/). They were definitely fun and informative reads. cyannGAH's Slog was particularly fun to read as they summed up the weeks topics in a rather witty and fun way. It's nice to see how these Slogger's and others have dealt with understanding the topics discussed in class and it definately gives you a neat sense of perspective to see the topics through someone else's eyes!
That's all for this week - good look on your mid-terms everyone!
We're into week 5, steam-rolling through the winter term and the assignments and tests are sure piling up! The latest (well first really) CSC148 assignment is based on the famous Towers of Hanoi game. Instead of the usual 3 pegs, our version has us dealing with 4.
What's really interesting about this is that the most optimal solution to Towers of Hanoi with more than 4 pegs has yet to be proven! Many great minds have probably tried solving this problem and it feels great knowing that we are going through the same thinking process they went through!
I chose to work alone as I usually do for CS assignments; though I was first a bit frustrated with understanding how assignment one was meant to be structured, I did eventually figure it out (thanks to everyone on the Piazza forums!). It was nice to see how the different topics we discussed in class so far (inheritance, basic data structures, recursion etc.) fit together to make up a working solution.
Although I haven't yet managed to find the most optimal algorithm for solving the 'four stool (or peg)' Towers of Hanoi game, I have come quite close to it. Hopefully, I will discuss my solution (and alternatives) more thoroughly after the assignment deadline has passed ( to give everyone a fair chance of course :-] ) - but the hardest part by far has been figuring out what values of 'i' to use; I think the answer to the most optimal solution lies there - though I haven't found it yet.
Besides the assignment, the other highlight of the week was the lecture topic on scope. This is yet another familiar topic for me though I haven't used it much in the past. My past instructors told us to avoid using global variables (most of the time at least) as they can make code harder to understand and can start polluting namespace.
Is was a little difficult, but after looking through the examples (of predicting outcomes) in lecture, I was able to refresh most of my memory on this topic.
I've also finally had a chance to read through some other Slogger's posts. A couple that really caught my eye were: cynnGAH's Slog (http://148journey.blogspot.ca/) and Ada Ene's Slog (http://adauoftcsc148.blogspot.ca/). They were definitely fun and informative reads. cyannGAH's Slog was particularly fun to read as they summed up the weeks topics in a rather witty and fun way. It's nice to see how these Slogger's and others have dealt with understanding the topics discussed in class and it definately gives you a neat sense of perspective to see the topics through someone else's eyes!
That's all for this week - good look on your mid-terms everyone!
Monday 3 February 2014
Recursion and Cheese!
Week 4 has come and gone: The central topic this week was recursion. Though it was an overwhelming idea at first, there was one example that stood out amongst the rest in it's explanatory power: Thinking of a problem as a set of smaller but similar problems. Then, consider the subsets of the same problem within those subsets. You carry on this process until the base case is reached and then add everything together to solve the problem.
Working through some recursive examples was a bit difficult at first since I was treating every subset of the problem individually rather than seeing the same solution work for every subset and then ultimately culminate to the final solution.
All in all, recursion is definately a great addition to my 'programming toolbox' and I see many uses (both past and present) for it.
Speaking of present uses of recursion, the next topic of the week was Assignment 1.
A1 is based on the famous Towers of Hanoi problem. This assignment has us trying to move stacks of cheese with towers of hanoi-esque rules.
Though the assignment (currently working on it) seems quite challenging, I like seeing all that I've learned being put to use in one exercise.
I recognize that many aspects of the programming world emphasize teamwork and coordination, but I have decided to (for now) work alone. This will give me the oppurtunity to test my comprehension of learned topics in a rigourous way. Hopefully that will be good prep for the upcoming mid-term.
Well, that's all for this week - good luck to all on assignment 1!
Working through some recursive examples was a bit difficult at first since I was treating every subset of the problem individually rather than seeing the same solution work for every subset and then ultimately culminate to the final solution.
All in all, recursion is definately a great addition to my 'programming toolbox' and I see many uses (both past and present) for it.
Speaking of present uses of recursion, the next topic of the week was Assignment 1.
A1 is based on the famous Towers of Hanoi problem. This assignment has us trying to move stacks of cheese with towers of hanoi-esque rules.
Though the assignment (currently working on it) seems quite challenging, I like seeing all that I've learned being put to use in one exercise.
I recognize that many aspects of the programming world emphasize teamwork and coordination, but I have decided to (for now) work alone. This will give me the oppurtunity to test my comprehension of learned topics in a rigourous way. Hopefully that will be good prep for the upcoming mid-term.
Well, that's all for this week - good luck to all on assignment 1!
Wednesday 22 January 2014
Object-Oriented Programming
Having worked with the concepts of inheritance, composition and exceptions in the past, the third of week of CSC148 felt like, in general, an effective and comprehensive review. Being new to Python, it was, as one might expect, interesting to compare the ways in which Python implements these programming concepts in contrast to other OOP languages like C++ and Java.
Generally speaking, I find making use of classes in Python to be easy and intuitive. I particularly enjoy the way in which Object-Oriented Programming works to structure my solutions in a coherent manner - for example, instead of outright treating an ADT, like a list, as a stack, it is much more intuitive to encapsulate all methods related to stacks in a single class and then call on that class as needed in the future.
I felt that, not only is it less tedious to code in such a paradigm, but it is also easier to understand and make future use of chunks of code relating to a particular ADT or set of methods (i.e. stacks, queues or a class of mathematical operations). In other words, the aspect of reuasbility - just as in procedural programming - is perhaps one of the most appealing features of OOP. In summary, the amount of structure and coherence that OOP brings when coding a solution to a problem is what I think is the most enjoyable aspect of coding with an OOP paradigm in mind.
Now that my general overview/ analysis of this the OOP discussed thus far in the course is over, I will now move on to some challenges that arose during my experiences with OOP in these first few weeks.
My first challenge was centered around the concept of 'flexibility' of my classes: How might I structure my classes in way where others, and myself, could use those same classes for solving a variety (of different) problems? What I mean is this: I know that I am writing a certain class to help with my solution to one particular problem, but isn't one of the central ideas of OOP reusability? Will this same class benefit me in other cases, or will I (or others) need to modify it later to suit my (new) purpose?
What these questions lead me to was the idea that, when I write my classes, I should bear in mind different ways in which someone (or myself) might want to interact with this class. I should then code my classes in a way that is not just tied or suited to the problem at hand - i.e. I should include helpful methods that can may be used to manipulate the class in different ways than what I currently need. Of course, I needn't stress over every possible use of this class but, at the very least, the class should be (except in special cases) general enough that it is able to be used in different ways.
Am I putting too much emphasis on reusability? Perhaps. But I believe firmly that this should be an idea at the back of the mind of any serious user of a OOP paradigm.
I will mention one other OOP challenge I encountered these past few weeks: the fact that, unlike C++ or Java, Python does not consider access levels in classes (private, public variables etc.). This is a concept that I learned to work with when I first started with the OOP paradigm in other languages - and it is a concept that I stuck with throughout my studies in computer science.
Though it is not a major issue, I know that it will take me a while to adjust to thinking object-orientedly without considering access levels, I feel that it also somewhat liberating to know that I don't need to worry about programs that might access a variable their not supposed to and hence, not use the class as intended. On the flip side, I will need to more careful when I use my own (or other's) classes!
Generally speaking, I find making use of classes in Python to be easy and intuitive. I particularly enjoy the way in which Object-Oriented Programming works to structure my solutions in a coherent manner - for example, instead of outright treating an ADT, like a list, as a stack, it is much more intuitive to encapsulate all methods related to stacks in a single class and then call on that class as needed in the future.
I felt that, not only is it less tedious to code in such a paradigm, but it is also easier to understand and make future use of chunks of code relating to a particular ADT or set of methods (i.e. stacks, queues or a class of mathematical operations). In other words, the aspect of reuasbility - just as in procedural programming - is perhaps one of the most appealing features of OOP. In summary, the amount of structure and coherence that OOP brings when coding a solution to a problem is what I think is the most enjoyable aspect of coding with an OOP paradigm in mind.
Now that my general overview/ analysis of this the OOP discussed thus far in the course is over, I will now move on to some challenges that arose during my experiences with OOP in these first few weeks.
My first challenge was centered around the concept of 'flexibility' of my classes: How might I structure my classes in way where others, and myself, could use those same classes for solving a variety (of different) problems? What I mean is this: I know that I am writing a certain class to help with my solution to one particular problem, but isn't one of the central ideas of OOP reusability? Will this same class benefit me in other cases, or will I (or others) need to modify it later to suit my (new) purpose?
What these questions lead me to was the idea that, when I write my classes, I should bear in mind different ways in which someone (or myself) might want to interact with this class. I should then code my classes in a way that is not just tied or suited to the problem at hand - i.e. I should include helpful methods that can may be used to manipulate the class in different ways than what I currently need. Of course, I needn't stress over every possible use of this class but, at the very least, the class should be (except in special cases) general enough that it is able to be used in different ways.
Am I putting too much emphasis on reusability? Perhaps. But I believe firmly that this should be an idea at the back of the mind of any serious user of a OOP paradigm.
I will mention one other OOP challenge I encountered these past few weeks: the fact that, unlike C++ or Java, Python does not consider access levels in classes (private, public variables etc.). This is a concept that I learned to work with when I first started with the OOP paradigm in other languages - and it is a concept that I stuck with throughout my studies in computer science.
Though it is not a major issue, I know that it will take me a while to adjust to thinking object-orientedly without considering access levels, I feel that it also somewhat liberating to know that I don't need to worry about programs that might access a variable their not supposed to and hence, not use the class as intended. On the flip side, I will need to more careful when I use my own (or other's) classes!
Saturday 18 January 2014
Subscribe to:
Posts (Atom)