WEEK 11: Sorting and Efficiency

    In general, a sorting is arranging collected elements or data in certain orders by comparing each other. There are many different types of sorting such as bubble, selection, insertion, merge, shell, and quick sorts. Each type has different efficiency, which is algorithmic efficiency as the size of the input grows larger, and is based on a number of elements to sort. Most sorts have algorithmic efficiency of either O(n^2) or O(n log(n)).

    Among the different types of sorting algorithms, the first three sorts: bubble, insertion, and selection consider as simple sorts. They perform differently, but they perform better on a small list or a list that is almost sorted, rather than a large list. A bubble sort is repeatedly swapping adjacent elements that are unsorted until the whole list of items in a certain order. An insertion sort repeatedly goes through all the items in an unsorted list each time, and inserts an item into its correct position. Similar as the insertion sort, a selection sort also repeatedly goes through a list to select an item according to its order, and place it in the correct position. All of three sorts have similar efficiency, O(n^2) on average, best and worst test cases except the insertion sort has O(n) on best case. As well as their stability is stable and their space is constant.  

    Unlike those three sorts, merge, shell, and quick sorts are more efficient on a list containing a large number of items in random order. As well as they do not use comparison, and are more complex algorithms. A shell sort compares elements far apart in the beginning, and then compares elements less far apart. At the end, it compares adjacent elements similar as the insertion sort. A quick sort divides the list of items into two sub-lists based on a pivot element. In one of the sub-lists, elements are arranged to be smaller than the pivot element, and in another sub-list, elements are placed to be larger than the pivot element. This process continues on the resulting sub-lists until the whole items are sorted. A merge sort is similar as the quick sort. It also divides a list, but it does not have a pivot elements. In the beginning, it divides the list into n sub-list with only 1 element. And then it merges a sub-list with another sub-list to produce new sorted sub-lists, and this process repeats until all the sub-lists are merges together and sorted. For these three sorts, their efficiency is O(n log(n)) on best case. For merge sort, it has O(n log(n)) efficiency on best, average, and worst case, but the other two sorts are different. The quick sort has O(n log(n)) on best case, but has O(n^2) on worst case. The shell sort has O(n^2), too, but on the average case, it has big o notation depends on gap sequence. The space complexity for quick sorts is constant, but merge sorts is depends on whether it deals with linked list or arrays.

    I have learnt about insertion, selection, and bubble sorts in CSC 108, so I was familiar with those three, but not with the other three sorts. I was confused by just looking at the codes of the three functions that I learnt in this course, but the link on the course website helped me a lot. The link explains what they are, and also shows the pictures of how they work. However, understanding big oh notation was hard for me and it is still hard. I also learnt about efficiency in CSC 108, but I did not fully get from that course, so I had hard time with big oh notation. So, I looked up about the big oh notation and how they are different on different test cases and on different sorting algorithms. As well as this week lab was little helpful to understand the concept. I should keep practice on it as I tried to understand the recursion. When I prepare for the final exam, I should focus more on this topic and binary tree.

Missing Weeks

From week 8 to 10 I learnt about a binary tree, a linked list and a binary search tree.

A linked list is a linear data structure containing elements. Each element contains a data and a reference to the next node. The first node in the linked list refers as head, and the last node points null. The advantage of a linked list is that the number of nodes in the list is not fixed, and can add or delete the node. However, it cannot directly access to the individual elements. To find a particular element, need to go through from the head and the reference until it reaches the element.

The binary tree is made up by nodes, where each node contains element, left and right references (or subtree). This tree has many terms. First, the node at the top is called root. Parent is a node directly connected from one other node. Children are an arbitrary number of nodes connected branched off from parent. The number of children has to be either 1 or 2. If a node does not have children, it is called leaves. It represents data in hierarchical form, and does not allow duplicate values, so it will be easier to find a certain element in tree structure.

The binary search tree is similar as the binary tree except a left sub-tree contains a number less than a root while a right sub-tree contains a number bigger than the root. Both sub-trees also have to a binary search tree. As similar as the binary tree, it is easier to find an element since elements in left sub-tree are smaller than an element in root while the right sub-tree contains bigger elements. It is also efficient on memory space, because it does not reserve more memory than it needs to. It can act as a list, so it can split, remove or insert an element faster.
In general, I think the computer science topics are hard for me to understand and apply knowledge to write a code. Most of time, I need to practice and go over what I did or learnt in labs or class to fully understand. I looked up the idea and practiced, so I think I can do it now, but I think I need more practices. 

WEEK 7:RECURSION

   Recursion is a useful method that calls itself. It breaks down a complicated problem into smaller part to solve some and to approach the problem easier. We have learnt and practiced this topic for few weeks but I am still struggling with the recursion. I thought I was able to use this method to write a function during labs. But I guess I was able to do because I was working with my partner. Whenever I work on a recursive function by myself, it takes more times to figure out the problem and the solution. I do not know if this is normal for everyone. Among many functions, concepts and topics learnt so far, I think the recursion is the hardest topic. I should keep practicing on it until I become comfortable with recursive function.

WEEK 5

I worked on the assignment 1 during this weekend. While I was working on it with my partner,  both of us were confused and had hard time working on it. We discussed many things such as deciding between a dictionary and a list, but we ended up using a list. When we finished the first part up of it, but the graphic of this game did not work. So we had hard time to figure out the problem and to fix the codes. We still need more steps to finish, but I think we might have difficult time to complete the A1. So after this assignment, I need to go over all the concepts and to practice more.

WEEK 4

   This week lab was helpful for me to practice writing a unittest.  I have learnt and also have seen what unittest is and what it does in csc108 course, but I didn’t have any experience writing it. During the lab, I and my partner had to write one, but both of us didn’t know what to write. So we looked up how to write and the examples we went over during a lecture. I was not sure the way I wrote is right or not but since it worked without raising an error, I thought it was ok. I need more practice on this. New stuffs I learnt were an importance of tearDown method in unittest and a proper way to write a super method. The first method clears up all the data at the end to return to its initial state. Another method is super (SubClass, instance).method (args). This one is similar as using Class.method(args). I was not sure about the super method, but since I know it I should get used to using it. As well as, I should practice more on writing a unittest, too!

WEEK 3: Object-Oriented Programming

   Object-Oriented Programming (OOP) is basically how Python works. This organizes a program by creating an object, because objects contain both data and functionality. The main key idea of this programming type is using classes, which create a new type and an instance of a class, object. Objects can store data using a variable belong to the object and also can have a functionality using functions (methods) within a class. A class contains methods such as an initializer, a string method, and a represent method etc. The structure of this programming is that many methods contain variables are within a class. This type of a structure makes a complex function to be easier to read and to trace back the code the user typed. As well as it helps to define an error easier.

   I learnt writing classes in CSC108 so I was familiar with the concept of classes and importing a class into another class except the way of writing the function. In the first lecture, the example the professor showed made me confused because the type contract for a function was written in the parameter. I have never seen those kinds of examples in CSC108 course, so I was wondered if it works or not. I tried to write a random class and methods as the examples to see if it works and liked the shorter way to write a function. As well as I found a new code fragment that I have never seen, which is isinstance(). I looked up the use of isinstance(), and found out it checks if a given object is an instance of a class. Now I am familiar with new style of writing a function and a new code. So far I am okay with examples, but if I am confused or cannot figure out something, I might just look up and figure out the way it works.