Sorting

I had learned bubble, selection and insertion sort in CSC 108, and I know more about sorting efficiency and how to use a proper way to sort a list of number.


Bubble, selection and insertion sort all have to examine each element of the list, so it is really an awful waste of time. The running time for them is all O(n²), these ways of sorting are quite time-consuming. Thus, more efficient ways are introduced, they are merge sort, quick sort, and Timsort which is python standard sorting algorithm.
We describe the running time for program with 'Big Oh' notation.For example, the running time for bubble sort is always O(n²). We focused on the efficiency of merge, quick and Timsort in different situation.Merge sort a recursive algorithm that continually splits a list in half. It means if the list is empty or has one item, it is sorted by the base case L=L[:],  If the list has more than one item, we split the list and recursively implement a merge sort on both halves. The quick sort is very similar to merge sort, firstly we select a pivot point usually is the first element, and it is used to assist with splitting the list. However, quick sort does not use additional storage.
The most common way in term of list sorting is Timsort, the wrost case is , and the best case is . it is a hybrid sort, created by Tim Peters in 2002 and used as Python's built-in sorting method. Timsort is mixture of  insertion sort and merge sort, it take less time to sort sorted list than other ways.
I learned a lot about efficiency and theory of list sorting, they have own advantages in different situation, I look forward to knowing more about how to choose most efficiently way to sort list when deal with various lists.

Recursion

These weeks, I have learned a lot about recursion function.A recursion function is a function inside calling itself repeatedly until a desired value is achieved.
I found recursion is so abstract that it is the most difficult concept for me to master.

The Turtle and the nested number list are two examples of recursive function. To understand how they work, one way is to assume the function works correctly when we call it for an order 0 level, then we just need to focus on order 1 level. If they work properly, we take it to the next level. It means we can trace the recursive function every recursion it runs.This method is really helpful for me to understand how recursive functions work. Moreover, the basic structure of recursive function is usually if statement ( if: ... else:), and the function is repeated in else code unless it reach a point or value which satisfy the requirement in if code.

In my Assignment 1, recursive function is the key step to reduce steps that moves cheeses from source to destination. In the lecture, I knew the code for tower of hanoi, and this code is the basic code for move cheese function. I choosed i according to the given function, and moved n-i, i and n-i cheeses using tower of hanoi separately. Finally, I calculate the total steps which is much less than n^2 -1.

This week, we were introduced a new data structure called Tree. A common kind of tree is binary tree, like a family tree, its top node is called parent, and the nodes it refers to are its children.Tree are defined recursively like other recursive functions. The process of assembling a tree is similar to the process of assembling a linked list. There are three traversal methods pre-order traversal, in-order traversal and post-order traversal.First print the root, then print the entire left subtree, and then print the entire right subtree. This way of traversing a tree is called a preorder, conversly,in-order is to print the left tree, root and then the right tree.Post-order is from left tree, right tree to the roots.

I acquired a lot of knowledge about the recursive function, and I am getting used to using it.    
            
  

Slog Object-Oriented Programming

Although I took CSC 108 last term, CSC148 is still a big challenge for me. Especially, I had almost no confidencewith the Object oriented programming because Class is the weakest part I ever learned in CSC 108. In the first lecture, I had a short review on Class and a new things was introduced to me that was list comprehension. It can be used to created a new list by expressing every element in a list. This is method is so convenient that it really helps me simplify procedures and save time. At that time, I realize that CSC148 must be full of fun and I could do well on it as long as I work hard. However, the first week lab frustrated me a lot. During the lab, I was totally lost because I had no idea what to do. Thus, I asked my partner for help, and he taught me a lesson that read the handout and instructions carefully before you do anything. I suddenly understood that the reason why I was confused about what to do next was the lack of patience on reading. Following the instructions, everything became much easier, and with of assistant of TA, I also knew how to implement a class appropriately. However, I did not have enough time to accomplish all the work, but this lab help me review lots of material from CSC108 such as files, writing function, string manipulations. One thing really built up my confidence was that I accomplished exercise 1 without any help. At first, I ran my class program and I always got the error. In order to figure out the problem, I read my program step by step and tried examples to test each functions. Then, I find I did not use string method to represent the word in class, it was the key error caused the whole program failed. Finally, my program ran successfully and passed the tests, to be honest, it was really a achievement for me. In conclusion, I find that it is so meaningful to do python work, and I believe that I will do better in the future.