Big Ohhhhh and Sorting

So my title seems a bit ambiguous because of  'Big O'. I know. So let me explain Big O notation first. When we think of efficient something is, we would normally look at the worst case run time and the best case run time. The best-case run time is the time is takes for an algorithm to run under optimal conditions, and the worst-case run time is the opposite, i.e. the worst/longest time, it takes for an algorithm to run. Big O is simply the worst run time. 

Big O isn't simply a number. Its describe the type worst-case run time we expect, i.e. if we have to  run through every element in a list we would say it is in O(n); which just means it is in Big O of n, and n describes that it is a linear function.

Imagine a pile of ten cards, from Ace to ten, all of the same kind. I then come along and shuffle them up. Think of how many ways we could put them back into order. We have a similar concept in Python. When given an object with similar elements that can be sorted, they are multiple ways to sort these objects in python. The most common sorting algorithms are merge sort, bubble sort, selection sort, quick sort, insertion sort and tim sort (python's built-in sort). All these algorithms have different methods of sorting. And all have particular cases in which they would work best. One thing to note is a lot of either recursion or looking through elements of what it being sorted happens when we call on sort.

Merge sort

Merge sort works in pairs, sorts the pairs and once all the pairs are sorted, it will form a new pile of cards from the already sorted pairs.

Insertion sort

Insertion sort is good for lists in python that are short. We look at our pile of cards. What insertion simply does it looks at each card and sees where it should be and places it in its correct place but in a new pile.

Bubble sort

Bubble sort is simpler than some of the others I have and will explain. You could say it is similar to insertion sort that compares cards in pairs. What it does is compares the first two cards in the pile, and if the second card is smaller in value than the first, it will swap them, if not it will leave them as is. It then moves compares the second and third cards in the piles and swaps them if the third card is small then the second. This process continues until the list has been sorted.

Selection sort

We will look through all the cards until we find the Ace i.e. the smallest card. When it is found, we just move it to the top of the pile. Because we know that the first card is in its correct position, we can start with the second card of the pile, and we will look through all the cards until we find the card with two on it. That card is then moved to the second position ( or you could think of it as the card is moved to the top of the unsorted part of the pile). This process continues to happen until all the cards are sorted.

Quick sort

Quick sort works similarly to a binary search tree. It gets a pivot, for example the card five. It  then compares the elements with the pivot and all the elements that are less than five will be moved before it and all those larger that five will be moved after 5 in the pile. It then analyses smaller piles i.e. all the card before 5 are a sub-pile and all the cards after 5 are another sub-pile. This is done until all the cards are organised.

Tim sort

Tim sort is awesome. That’s first. Tim sort is an algorithm that was derived from both merge sort and insertion sort. Python uses this list to sort as it is the most efficient. I am not too sure how it works but I have attached a link for anyone interested in finding out the mechanics behind it.

http://en.wikipedia.org/wiki/Timsort

The table below is something I found on Wikipedia and edited a little bit. Shows a little insight

Name	Best	Worst	Method	Other notes
Merge sort			Merging	Highly parallelizable (up to O(log n) using the Three Hungarian's Algorithm or, more practically, Cole's parallel merge sort) for processing large amounts of data.
Timsort	n		Insertion & Merging	Makes n comparisons when the data is already sorted or reverse sorted.
Bubble sort	n		Exchanging	Tiny code size.
Insertion sort	n		Insertion	O(n + d),where d is the number of inversions.
Quicksort			Partitioning	Quicksort is usually done in place with O(log n) stack space.] Most implementations are unstable, as stable in-place partitioning is more complex. Naïve variants use an O(n) space array to store the partition. Quicksort variant using three-way (fat) partitioning takes O(n) comparisons when sorting an array of equal keys.
Selection sort			Selection	Stable with O(n) extra space, for example using lists.[3]

Recursion

Week 7 already. We are almost done with this course! We had the test last week as all of you know. How did you find it? Any thing challenging? The question about trees was a bit hard for me to answer as I am still struggling with that. But it was a fair test. Labs the week of the test, I didn't mind. The lab itself was hard. No one in my lab could do the Queue with linked lists which was annoying because I spent 2 hours stuck!

Recursion! Where to start. Let's start with the basics. Recursion is when you define a function, and in its code, it calls on itself. It always has a base case, which is the simplest case that it can call on and usually it will return something here or do something i.e. add to a list. Then when we have more complicated calls on the function i.e. nested listed, or lists with a length larger then n, and this is when the recursion happens. An example is a nested list, the base case would be when we have having a list where none of the elements are lists, and then the more complex cases, where we would use recursion, would involve at least one element in the list being a list. We can have multiple elements that are lists, we can have an element in the list that is a list that contains a list, ie, a nested list.

Here is a sample of code:

def code(x: list) :
      '''Returns the max number in a list.

    
    >>> code([5, 21, 10])
    21
    >>> code([5, [11, [27, 6]], 10])
    27
    """
    return max([code(x) if isinstance(x, list) else x for x in L])
    

This code is an example of what I explained above. What it does is it looks at every element in the list and if it is not a list, it will simply add it to a new list, this is the base case. If the element is a list, then it will call on itself, and read through every element in this list. In short it will keep on going deeper and deeper into a nested list, recursion, until it finds a non-list element , base case.

Post Reading Week

So first thing, I had no idea that we were supposed to post articles on our blog weekly, so I have practically missed the whole of first semester :(. I will try a super crash course and write up as much as I can.

As you all know we have a test on Wednesday, our first test. I had hoped that more past tests would have been posted but sadly we have very few to work with. Honestly, I'm terrified for this test because I can write code on my computer and run through the errors and debug it, but I'm not very keen on the idea of writing code on paper. Even though it does help us become more accurate, I feel after this course I will never actually have to write code on paper when I have me beautiful laptop to write it on. On a brighter note, to study for the test I went over all the slides, and tried my best to re- attempt all the labs (which was quite time consuming, but helpful) and tomorrow I will go over the past tests. I'm also pretty happy about the cheat sheet though I have no idea what to put on mine. Anyone have any ideas, or would like to share what they put on their sheet?

Before the break, we went over trees. The idea is similar to linked lists (so I was told by an engineer). It is interesting because the root is at the top of the tree and the leaves at the bottom ie it grows downward. The terminology  we reviewed was pretty simple to understand; root - the top of the tree, node, path, length, arity - max number of leaves, leaves- nodes that have no children. The easiet way to traverse a tree is recursively, (I read that somewhere). They are two ways to traverse a tree: post-order and in-order. We went over the code, (though it didn't stick to me, I should go over it again).

Object-Oriented Programming (OOP)

Object-Oriented Programming (OOP)

Whist learning about python in CSC108, Paul just brushed the surface of Python, but I feel the skills we learnt are very useful. In one of the readings we were given, it talked about using a tuple or a class to create the compound object. Which do you prefer between tuples and classes? What are the reasons that you prefer tuples over classes, or classes over tuples? I personally do not like tuples because they are immutable so when the idea of creating a class was pushed forward, I was all for it. It is easier to create the method for the class and I feel they are more specific for the object you created. It also provides a sense of organization if you are writing a lot of methods. I also like the fact that we can return instances as return values. Working in pairs in the lab was good revision on writing classes because I had actually forgotten a little bit of it. My partner was still familiar with the basics (thank God), so where I had problems with my functions, he was more than willing to help.

When defining the methods, we now write the type contract differently. I think it is a more effective and clear way of writing it, so as a pythonista, this was preferable. I would find it interesting to hear how others feel about this. Were you taught other ways of writing type contracts? Do you prefer the way we were taught in CSC108 or how we were taught in CSC165?  I do not understand why we were only taught about this now. It would be easier to simply teach us these things from the get go.

Last week, we had a mini exercise to find the nouns and its important attributes. It was fun looking at this paragraph and thinking about possible classes and possible methods, being able to apply the knowledge in Python to real life situations. This helped me realise all the practical uses of Python and all the other programming languages we will learn. This Monday, we learnt about exceptions and I had no idea what was going on. Did anyone else feel this way or was I alone. Hopefully, before the end of the week, I’ll re-read the material and see what I can pick up. Also asking my TA and my lab partner may be some help. The idea of subclasses and superclasses was also very thought provoking. It made me look through the previous functions and assignments I had written about and how I could have applied all these new things I have learnt. That’s something all you Pythonista’s could think about.

Have an awesome week.