week 11 - sorting and efficiency

Sorting and Efficiency
sorting is the process of placing elements from a collection in some kind of order. For example, a list of words could be sorted alphabetically or by length. A list of cities could be sorted by population, by area, or by zip code. There are may sorting algorithms that have been developed and analyzed. This suggests that sorting is an important area of study in computer science.
In CSC108, I have learn three sorting method: bubble sort, selection sort and insertion sort. The bubble sort makes multiple passes through a list. It compares adjacent items and exchanges those that are out of order. Each pass through the list places the next largest value in its proper place. The selection sort improves on the bubble sort by making only one exchange for every pass through the list. In order to do this, a selection sort looks for the largest value as it makes a pass and, after completing the pass, places it in the proper location. The insertion sort always maintains a sorted sublist in the lower positions of the list. Each new item is then 'inserted' back into the previous sublist such that the sorted sublist is one item larger.
In CSC148, I learn two more sort method：merge sort and quick sort. Merge sort is a recursive algorithm that continually splits a list in half. If the list is empty or has one item, it is sorted by base case. If the list has more than one item, we split the list and recursively invoke a merge sort on both halves. The quick sort uses divide and conquer to gain the same advantages as the merge sort, while not using additional storage. A quick sort first selects a value, which is called the pivot value. Although there are many different ways to choose the pivot value, we will simply use the first item in the list. The role of the pivot value is to assist with splitting the list. The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will be used to divide the list for subsequent calls to the quick sort.
When taking about the efficiency of these five sort, we need a Big O notation, which provides an upper bound for the runtime of our algorithm. For the average case, Big O of Bubble sort, insertion, selection sort is O(n^2). However, Big O of Quick sort and Merge sort in average case is O(nlog(n)). We can see that the quick sort and merge sort is more efficient than that three sort. From this, we can know that learning the efficient of a method is very important.

week 10

In this week's lecture, professor first talked about something about the assignment2. He gave some hints for the four functions we should write in the assignment. Four function is is_regex(s), all_regex_permutations(s), regex_match(r, s) and bulit_regex_tree(r). After taking about assignment2, professor some sort method which is different from the sort in CSC108. In CSC108, I have learned Bubble sort, selection sort and insertion sort. Now, professor introduce a new sort, which is quick sort. The idea of quick sort is choosing a pivot, then decide where the pivot goes with respect to the rest of the list, repeat on the partitions. After quick sort, I learned the merge sort. The idea of merge sort is dividing the list in half, then merge the sorted results.
This week's lab is very interesting. In the lab, we only need to complete two functions. One is inorder traversal and the longest path. At first, I use a intermediate list to solve the problem. But TA told us that we cannot use the intermediate list. Then this lab becomes challenges for me. In the end, we wrote a very long function to finish this lab.
In short, I have learned two sort method in this week.

week 9

In this week9, we begin to starting binary tree. we first learn some methods of binary tree. Like preorder and inorder. After that, we learn binary search tree. I don't know how this recursion work until professor show us the base case of the function. And this made me know more about the recursion. Before this lecture, I have some trouble for the assignment. But this recursion give me a big idea for the step 5 in the first assignment.  Professor also give me some example about how to find names in different scopes. I think I have some trouble in this and I will come back to read the example then ask my classmate for help.
In this week's lab,it's my first time to write recursion function by myself. At first, we need to have recursion insight.In the lab, I first use paper and pencil to do the first two exercise. I think doing these two exercise help me make the recursion insight. After this step, I write my recursion code for structured list. And this exercise did not give me any troubles.
In short, I need to comeback to see the example of find names in different scopes since I have trouble for this. And I have learned more about how to write a recursion function and do some practice on it.

wee8

In the week 8, I learned a wrapper class for list  in the lecture. In the lecture, professor used the example of 'Linkedlist' which use recursion in its method. And I have learned how to trace the recursion. I really like this part because after tracing a recursion function, I always can surprised by the result and I will know how this recursion function work. Professor always give another recursion example - draw turtles.This is very helpful for me to understand how the recursion work. And I think this week's content is easy to follow and I think I'm able to tracing a recursion function.
In this week's lab, I have written a lot of method about Linkedlist. And this lab's goal is to make me explore and understand inheritance.I have learned how to build a class and how to use subclass.
In this lab, it's my first time to use unittest framework to test my class. Then I know how to determine good test cases and use unittest.However, I think I still need some practice to remember the style of unittest framework.
In short, in this week, I start to learn recursion function and practice on building class and use unittest to test my code.

week 7

In last few weeks, I have learn a lot of things about recursion. Recursion means "defining something in terms of itself" usually at some smaller scale, perhaps multiple times, to achieve your objective. For example, we might say"A human being is someone whose mother is a human being" or "a family tree starts with a couple who have children, each with their own family subtrees.In general, recursion is a process of calling a function that is already executing. Firstly, we should include a base case which is a branch of the conditional statement in a recursive function that does not give rise to further recursive calls. So the base case is not recursive. We also should care the infinite recursion. When this happened, the function call itself recursively without ever reaching any base case. Eventually, infinite recursion causes a maximum recursion error in python.
In the lecture, professor show us two kinds of recursive data structure. One is nested list. Nested list is a list whose elements are either number or nested number lists. We have define some function for the nested list like summing the number is the nested list. For this function, we first need to think of base case, the do recursion for each nested list in nested list. So we sum each element is each nested list and then add them together. I also learn other methods about nested list like find the maximum depth. The second kind of recursive structure is trees. Trees are made up of nodes. A common kind of tree is a binary tree, in which each node contains a reference to two other nodes. The nodes is possible None. I think this is a advanced structure of nested list. The tree is a ADT and we use recursion under the object-oriented programming. We learn how to use recursion to find the height and the number of leafs of the tree, and represent the tree in different order by the recursion.
For the recursion, the professor give us a big assignment about towel of hanoi. A three stools hanoi is a very famous problem. But we need to solve the problem with four stools. That is a big challenge for me at first. After the hint from professor about the three stool, I get the idea of the recursion of four stools. At that time, I get a deep understand of how to define a recursion function.
In short, I think recursion is very helpful for some very complex programming. And the recursion is also use in mathematics. And I will spend more time on learning recursion.

week 6

In the week six, we begin to learn a recursive structure: Tree. The professor first told us some terminology of trees. Like nodes, root, path, leaf, internal node, subtree, height, arity, branching, factor. Trees are made up of nodes. A common kind of tree is a binary tree, in which each node contains a reference to two other nodes. The nodes is possible None. Then the professor show us a picture of a tree. And let us to complete three methods about three kinds of order of tree. All of these three function need to use recursion. Before the professor giving the solution, I have some confuse about the tree structure and not sure how can we express tree in python. After I solve the function of pre-order, I think I have a deep understand of the tree. Also, professor teach us some function like height, leaf_count. This is very helpful for us to practice the recursion and learn binary tree.
In this week's lab,we learn some python idioms and develop some unit testing skills. what I have to do in the lab is to re-implement some functions written using comprehensions and filter to use loops instead, and verify that I have consistent implementations using unit tests. I think this week 's lab is very easy and I have no trouble for this.

week5

In the week 5, we continuous learning recursion.I think the lecture is very helpful for our first assignment- towel of hanoi. In the lecture, professor talk about the recursion for 2, 3 cheeses case.Although in our assignment, we need to deal with 4 cheeses cases. But this is still a big help. When professor teaching this recursion, I don't know how this recursion work until professor show us the base case of the function. And this made me know more about the recursion. Before this lecture, I have some trouble for the assignment. But this recursion give me a big idea for the step 5 in the first assignment.  Professor also give me some example about how to find names in different scopes. I think I have some trouble in this and I will come back to read the example then ask my classmate for help.
In this week's lab,it's my first time to write recursion function by myself. At first, we need to have recursion insight.In the lab, I first use paper and pencil to do the first two exercise. I think doing these two exercise help me make the recursion insight. After this step, I write my recursion code for structured list. And this exercise did not give me any troubles.
In short, I need to comeback to see the example of find names in different scopes since I have trouble for this. And I have learned more about how to write a recursion function and do some practice on it.