Week 12 Material

The professor introduce the fibonacci sequence this week and implemented an algorithm for us to find the nth item in the fibonacci sequence. He also revisited the quick sort method and discussed its efficiency. We are also taught how to randomize an sorting algorithm.

In addition, If i could be informed about the TA hours for next week that would be greatly appreciated.

Week 11 Material

The main focus of the week is the regular expression tree node that we used in assignment 2. I think the by using the regular expression tree node, we form a unique tree which symbols are restricted to 6 kinds.

We came up with several different functions for the regextreenode class. For instance, the built-in equivalency function for the class. Since different tree node would have different memory addresses, therefore the function __eq__ is crucial otherwise, the nodes would not be equal even when the symbols and the children are the same.

I still have trouble processing how does the map reduce works and its difference toward a list comprehension. To me, they look very similar. I think I will need to take some time and figure it out. I would also like to know the office hours for the beginning of next week.

The algorithms of selection sort, merge sort, quick sort and their efficiencies

The selection sort method is dividing the list into two parts, a sorted part and a unsorted part. We choose the minimum of the unsorted part and added to the sorted part. The algorithm follows a O(n^2).

The quick sort method is choosing a pivot and place the items smaller than the pivot on the left side of the pivot and the items larger than the pivot on the right side of the pivot. This method belongs to O(nlgn).

The merge sort method is to use a function that merging two sorted list together into a single new sorted list in order to sort a list. This function belongs to O(nlogn)

By comparing their time complexity, merge sort is the most efficient sorting method and the selection sort method is the least efficient sorting method. In addition, both algorithms of selection sort and merge sort makes good sense to me but the I am having trouble understanding the algorithm for quick sort. To my understanding, in the recursed function, we make a list of the elements that are smaller than the pivot on the left side and a list of elements that are larger on the right, and we quick sort both lists until we get a sorted list.

Week 9 Material

The main issue being discussed this week is run time analysis, different sort method and the efficiency of the sort methods.

We spent more time on run time analysis this week but the instructor did not discuss in great details how do we find the big-oh of a certain algorithm except for the selection sort. I am hoping to get some instructions on how to practice this problem more and the way that we are going to be tested on finals.

In addition, we have seen examples of different sort algorithm including selection sort, merge sort and quick sort.

PS: I have a question about the code on def merge(L1, L2). What does 'while L1 and L2' means?

Week 8 Material

We have started to learn how to evaluate the efficiency of an algorithm and tried to come up with a more efficient binary tree this week.  Deleting and inserting a note into a existing tree is also discussed this week. In addition, the topic of run time analysis has been introduced to us and it is quite similar from the materials that i have been learning in CSC165, however, csc165 gave a more comprehensive introduction toward this topic. 

We constructed a binary search tree with the binary search node with the functions insert and delete and we used nested functions to accomplish out goals. I don't understand why some time when we are initializing a class, we put underscore _ in front of a argument. (i.e. self._root)

Week 7 Material

This week the topic being discussed is Linked-list. I find linked list easier to understand as oppose to Tree List while representing a tree. Linked-list has a recursive data structure because it has a recursive definition, therefore it helps me to understand recursion better. And we re-implemented the class stack using linked-list. We also learned a new way to assign values(tuple unpacking).

I also realize that the tree we have learned is a special case with the arity(branching factor) of 1. There are also trees with other branching factor which makes the scenario much more complicated.

Week 5 Material

I am looking at the Tower of Anne Hoy example. I do understand the literal meaning behind the code but I am still having trouble understanding how it would execute. First we move the first n-1 cheeses to a intermediate stool, then we move the last piece of cheese which is also the biggest cheese that we intended to move to the designation stool, and at last we move the cheeses on the intermediate stool to the designation. However, I have a few confusions. When n = 1, I think we would still have to move the cheese from the source stool to the designation stool, but in the else clause, we are simply printing that we made such action.

I find it very not helpful if I could not understand the execution since I would not know the output for each step.