This is it! The final hurrah! In my last (thankfully) Slog post, I will be doing essentially what amounts to a recap, of everything that I have done in the course so far.
I started out this course, having learnt only the bare minimum of programming. I knew how to make lists, knew the basics of unit testing-but beyond that I was a mess. I hadn't scored a very high mark in 108, but I've begun to change that around.
In 148, we started off by learning all about OOP, which was the foundation for essentially everything else that we had done in the course up to this point. OOP is amazing, and it really lends itself to a lot of situations in which the variables, and the tools that you are programming with can be applied.
Next, we learnt an assortment of other python techniques, such as errors and namespaces. These little techniques I really found interesting, since they are the foundation of the python language itself, so it was cool learning about these things.
Following this, we spent the rest of the course on recursion and trees (including linked lists). This is where the material in the course became extremely difficult for me, as I had trouble picturing a lot of the material in my head. Luckily, I had a super awesome TA, who guided me through this process-talked me through labs and give me extra help through the course.
As always, for the last time, I would to mention a post on a fellow classmates blog: http://47tulips.wordpress.com/. I really felt that this student put in a ton of work in this slog, and really communicated to me on a basic level how programming works. I commend him for his effort.
That's all for now!
Am I finally a pythonista by now!?
Saturday, 29 March 2014
Week 9
This week, I would like to talk about sorting algorithms. Now, if there was one thing that I had learnt about these sorting patterns we could choose, is that we should NEVER use bogo sort, since apparently my partner and I learned about during the lab-it would take literally forever to sort even a list of 10 elements.
In this Slog, I would like to touch upon, the major sorts that we had learnt this week-merge sort, quick sort and selection sort. Instead of talking about how each of them specifically works (which would be a waste of time), I will instead talk about their efficiency. You see, the key part in any type of sorting pattern, is to do it in the quickest amount of time possible. In theory, that time is constant time, that is every list can be sorted in 1 second, regardless of size. Unfortunately, that is not always possible. In order to measure the time it takes, we use the notation big Oh or O(n) , which is used to show how effectively the pattern can sort a list. When we have complexity of big O, like lgn(O) or O(n), that is considered good, and shows that this pattern is efficient at sorting a list.
Starting off with selection sort
Selection sort improves on bubble sort considering the number of passes, it swaps the largest in the list with the smallest consistently, however, the runtime is still O(n**2) and so is the runtime of insertion sort at the worst case which inserts a value in its correct place from beginning to end.
Shell sort is also O(n**2) at worst - it splits a list into sublists and sorts the sublists before piecing the list together again. Merge sort is a recursive algorithm which constantly splits a list in half and sorts smaller lists before rearranging the split list together with a worst case runtime of O(nlogn).
Quicksort improves upon merge sort because it does not use additional storage, it uses a pivot point, a value that is used to split the list and then calls itself recursively to sort smaller lists. Quicksort is on average O(nlogn) and faster than most O(nlogn) algorithms although, the worst case runtime, O(n**2), is rare.
There is also Timsort (O(nlogn)), a hybrid sorting algorithm that merges insertion sort and merge sort. You can also measure the best case runtime (represented by big omega) and the average case runtime (represented by big theta). However, if someone needs a sorting algorithm to sort a lot of information at once or in various different orders, then an algorithm is only as good as its worst case.
And there we have it!
In this Slog, I would like to touch upon, the major sorts that we had learnt this week-merge sort, quick sort and selection sort. Instead of talking about how each of them specifically works (which would be a waste of time), I will instead talk about their efficiency. You see, the key part in any type of sorting pattern, is to do it in the quickest amount of time possible. In theory, that time is constant time, that is every list can be sorted in 1 second, regardless of size. Unfortunately, that is not always possible. In order to measure the time it takes, we use the notation big Oh or O(n) , which is used to show how effectively the pattern can sort a list. When we have complexity of big O, like lgn(O) or O(n), that is considered good, and shows that this pattern is efficient at sorting a list.
Starting off with selection sort
Selection sort improves on bubble sort considering the number of passes, it swaps the largest in the list with the smallest consistently, however, the runtime is still O(n**2) and so is the runtime of insertion sort at the worst case which inserts a value in its correct place from beginning to end.
Shell sort is also O(n**2) at worst - it splits a list into sublists and sorts the sublists before piecing the list together again. Merge sort is a recursive algorithm which constantly splits a list in half and sorts smaller lists before rearranging the split list together with a worst case runtime of O(nlogn).
Quicksort improves upon merge sort because it does not use additional storage, it uses a pivot point, a value that is used to split the list and then calls itself recursively to sort smaller lists. Quicksort is on average O(nlogn) and faster than most O(nlogn) algorithms although, the worst case runtime, O(n**2), is rare.
There is also Timsort (O(nlogn)), a hybrid sorting algorithm that merges insertion sort and merge sort. You can also measure the best case runtime (represented by big omega) and the average case runtime (represented by big theta). However, if someone needs a sorting algorithm to sort a lot of information at once or in various different orders, then an algorithm is only as good as its worst case.
And there we have it!
Saturday, 22 March 2014
Week 8
This week, I will be talking about "linked lists". I used to hate linked lists (and recursion in general), but now I finally realize how useful they can actually be.
Linked lists basically work on the principle, that you have an element, and that element is connected in a fashion to the other parts of the list, which in terms is connected (linked) to other parts of the list. Essentially, what we are doing is making a recursive definition for a linked list.
The true purpose of a linked list comes in to play, when we consider how a programmer would add and remove elements from a list. The way in which this happens with a traditional list is through shifting all the elements and then inserting the element that we require at the place in the list that we require. When we do this with a linked list however, we see that we don't have to worry about the references to the rest of the list, and we can simply only focus on the parts of the list that we are inserting/deleting items from.
I had some practise this week with linked lists- in particular, with how a linked list can be used to adapt to various functions. I did have difficulty with the lab #6, that focused on this particular topic, however by using the TA's suggestions of writing out the linked lists using diagrams and pictures, and thinking of the topic in a recursive fashion, I was a master at this in no time at all.
I would like to make a comment on one other blog this week- from http://adauoftcsc148.blogspot.ca/. He talked about the manner in which we view a linked list as a "head" and a "tail", which is another way to visualize these types of lists. I enjoyed learning about this representation since it seems very intuitive to me, how to create a linked list, by just worrying about this two parts,and how they are connected through our coding of the recursive linked nodes in the list.
Linked lists basically work on the principle, that you have an element, and that element is connected in a fashion to the other parts of the list, which in terms is connected (linked) to other parts of the list. Essentially, what we are doing is making a recursive definition for a linked list.
The true purpose of a linked list comes in to play, when we consider how a programmer would add and remove elements from a list. The way in which this happens with a traditional list is through shifting all the elements and then inserting the element that we require at the place in the list that we require. When we do this with a linked list however, we see that we don't have to worry about the references to the rest of the list, and we can simply only focus on the parts of the list that we are inserting/deleting items from.
I had some practise this week with linked lists- in particular, with how a linked list can be used to adapt to various functions. I did have difficulty with the lab #6, that focused on this particular topic, however by using the TA's suggestions of writing out the linked lists using diagrams and pictures, and thinking of the topic in a recursive fashion, I was a master at this in no time at all.
I would like to make a comment on one other blog this week- from http://adauoftcsc148.blogspot.ca/. He talked about the manner in which we view a linked list as a "head" and a "tail", which is another way to visualize these types of lists. I enjoyed learning about this representation since it seems very intuitive to me, how to create a linked list, by just worrying about this two parts,and how they are connected through our coding of the recursive linked nodes in the list.
Subscribe to:
Posts (Atom)