Week 11: Sorting and Efficiency

There are many ways to sort,but we can't find the best one. Every method has its advantage and disadvantage.So far, we have learnt some sort like selection sort, insertion sort, bubble sort, merge sort, quick sort and so on.

1.Insertion sort







The best case is when the list is already sorted, at this time, the complexity is O(n). While the worst case occurs when the list is sorted reversely, and the time complexity is O(n^2).

It must check all following one by one, so it is moderately inefficient. It only can be used on the list that is almost sorted or lists with very few elements.

2.Selection sort

For selection sort, no matter what the lists look like, it will run the same time. So the complexity of the best case, worst case or average case are all the same, O(n^2)

But it swap no more than n times, so if it costs a lot to swap, it will be efficient.

3.Bubble sort

For bubble sort,it compares adjacent items and exchange those that are out of order. So the complexity of the best case is O(n), and the worst case is O(n^2).

This sort is very stable.

4.Quick sort

For this algorithm, we select a middle first , and put the items that are less than middle on the left and put others right, then repeat it until the length is 1. It is an improvement of bubble sort. And the complexity of the best case is O(nlog_2 n), while the worst case is O(n^2).The best case occurs when the left and right have the same length.

5.Merge sort

In merge sort, we continually split it into two parts, it is a recursive algorithm. The best case, average case and worst case are all O(nlogn).

Summary

1.Insertion sort and bubble sort are always slow, but when the list has almost sorted, it can take very little time to sort. At this time, quick sort will waste a lot time.

2.When n is small, we can use selection sort if we don't have request on stability, and otherwise we can choose insertion sort or bubble sort.

3.When n is large, and the key elements are random, then it is suited to choose quick sort if stability is not that important.

4.When n is large, and the key elements are somehow sorted, at the same time, we want it to be stable, then the merge sort is a good choice for us.

As we can see, in different situation, we should choose different algorithm to sort a list to save time and space. The efficiency is very important for us especially when we have too many elements, if we choose the best suited way, we can save much time and space.

Week 8: Linked list

Linked list is a new class represented a lists of numbers, just like the linked list below we are looking at.




It has two parts, the first one is value and second one is its contains, which can be regarded as a sub-linkedlist. Every time we add a value to the linked list it will add on the top of it, and just like ADT, the first one to come is the last one to out.

It is really a hard work to find the deepest value, which require us to use recursion algorithm.

But the most attractive function for me in this class is the reverse function.
It can totally reverse the linked list. It is really a challenge if we want to get the deepest value and dig it out on the top.

I have been confused of the whole function for a long time, and finally figure out how it works.

As we can see, it builds a new linked list and make it equivalent to the original one, and builds a new variable named new_node to do the recursion.

It is such an amazing way to deal with that problem.

Week 7: Recursion

Recursion is a process, in which it repeats all the time until the base case occurs. It is a common application in math and computer science.

A recursive method shuould have at least two properties:
1.the base cases
2.rules that reduce all other cases toward the base case

It is useful to deal with a complex problem with countless cases. We can just simplify the complex cases into the easiest one by repeating the same method， just like peeling onions.

Another example of recursion in reality is that we put two mirrors face to face, and put a candle in the middle of them, then we can see countless candles in mirrors. It can be regarded as a recursion.

As for the Python we are learning, the Tower of Hanoi is a good example to understand.

For three stools, we have two base cases, and for four stools, we have three base cases. The "else" on the bottom is what we call recursive rules. No matter what case is given, it can always get to the base case, and get the wanted result.

On one hand, recursion can help us solve many complex problem, on the other hand, it is some kind of inefficient, for each process, it calls itself many times, so that it have much data to deal with until get the final result.

Anyway, from what we are learning now, recursion can be said as one of the most practical method.

Week 6: Binary Tree

This week we learnt about binary tree, which has three ways to be represented.

The first one is preorder.

def preorder(tl: 'TreeList') -> list:
    """
    Return list of values in tl in preorder

    >>> preorder([5, [4, None, None], [3, [2, None, None], [1, None, None]]])
    [5, 4, 3, 2, 1]
    """
    return [] if tl is None else ([tl[0]] + preorder(tl[1]) + preorder(tl[2]))

Second one is post order,like below.

def postorder(tl: 'TreeList') -> list:
    """
    Return list of values in tl in postorder

    >>> postorder([5, [4, None, None], [3, [2, None, None], [1, None, None]]])
    [4, 2, 1, 3, 5]
    """
    return [] if tl is None else postorder(tl[1]) + postorder(tl[2]) + [tl[0]]

The last one is inorder.

def inorder(tl: 'TreeList') -> list:
    """
    Return a list of values of tl inorder

    >>> inorder([5, [4, None, None], [3, [2, None, None], [1, None, None]]])
    [4, 5, 2, 3, 1]
    """
    return [] if tl is None else inorder(tl[1]) + [tl[0]] + inorder(tl[2])

Every binary tree can be represented in such ways, and if we want a certain binary tree, we only need to know the preorder list and in order list of that binary tree.

Week 5: Towers of Hanoi

This week we mainly did the assignment 1. I had to say, the first task for me is to understand what it means. Maybe because I was not native speaker or a person familiar with computer science, I couldn't even figure out what result we should get running the final file.

So at first, I was not hurry to do what we are required. I asked a mentor how to understand the whole assignment, what function is each file -- 'ConsoleController.py','GUIcontroller.py' and so on.

After struggled in so many files, I finally figured out what each file is for.

Week 4: Recursion and nested list

This week we learnt how to find the depth of nested list in a recursive way. It is the first time for me to learn recursion, it seems much more simple than for loop or while loop, because its results are always very short, maybe in one or two lines. But it is hard to figure out how it runs for me.

Let's look at an example first(which we learnt in class):

All recursion need a base case and a recursion step.

What I think difficult to do is to build the recursion step, it is really hard for me to find the relation ship between the base case and the current case. I was struggled for a long time on e2.

But fortunately, one of my friend taught me that I shouldn't think too much on the whole procedure, just figure out the relationship by simplify the current cases.

I did so, and was surprised to find I am done, I made it. It is no doubt that recursion is not that difficult, just analyse in a right way, every one can grasp it.

Week 3 : About Object-oriented programming

In Wikipedia, the definition of Object-oriented programming is showed below.

"Object-oriented programming (OOP) is a programming paradigm that represents concepts as "objects" that have data fields (attributes that describe the object) and associated procedures known as methods. Objects, which are usually instances of classes, are used to interact with one another to design applications and computer programs.[1][2] C++,Objective-C, Smalltalk, Java, C#, Perl, Python, Ruby and PHP are examples of object-oriented programming languages."

It has a series of basic theories, like class, subclass, method and so on.

Just as we learnt in Python, a class is defined as "an extensible template for creating objects, providing initial values for state (member variables) and implementations of behavior (member functions, methods)".

For example, we defined two classes as Toy and Dog in the exercise we did before. We made 'Bob = Toy()', then Bob belongs to the class 'Toy', it has the implementation of behaviour 'play',which means it can be 'play'ed.In the example above, we can also define other two things as object and method. 'Bob' is one of the Toy, it has its own properties, by which I mean, it is unique over the world, and we call it 'Object'. Maybe 'Bob' have many common properties with other 'Toys', but it is itself. Different from the abstract 'class', it is a specific concept. Just like 'class' is a set of all things around the world containing some things which have similar properties, but 'object' is the particular element in the class. As for the 'method', it defines many things that 'objects' in 'class' can do(but not have to). Let's back to the example above, all 'toys' have the 'method' play, if we make 'Bob.play()', it will return 'Squeak!\n'.

These are the basic definitions in the OOP.

I think it is a very convenient way to create a new class, for dealing with problems more specifically and easily.