Last impressions

CSC148 offers me an opportunity to study more deep in the filed of computer science. At the beginning of the course, we have done some reviews on class, which is the main focus in this course. To be more precise, special methods are the most fundamental methods in class, it includes __init__, __str__, __eq__. In addition, you can also define other method by yourself. Moreover, there are parent class and children class. Children will inherit everything from Parent class and it will also have its own method because there will be different cases in each children class. For example, in the parent class employee, there are hourly employee:

    def amount_of_pay(self):

        """

        (Employee) -> number

        

        Return the amount that this Employee should be paid in the next

        pay period.

        

        >>> e = HourlyEmployee(23, 'Barney Rubble', 333333333, \

        'weekly', 1.25)

        >>> e.log_hours(15)

        >>> e.amount_of_pay()

        18.75

        """

        return self.not_yet_paid * self.hourly_wage

and salaried employee:

    def amount_of_pay(self):

        """

        (Employee) -> float

        

        Return the amount that this Employee should be paid in the next

        pay period.

        

        >>> e = SalariedEmployee(14, 'Fred Flintstone', 454121883, \

        'weekly', 5200)

        >>> e.amount_of_pay()

        100.0

        >>> e = SalariedEmployee(99, 'Mr Slate', 999999999, 'monthly', \

        120000)

        >>> e.amount_of_pay()

        10000.0

        """

        

        if self.pay_period == "weekly":

            return self.annual_salary / 52

        else:

            return self.annual_salary / 12

In this two example method, they are paid differently. Therefore, different methods are applied to them separately. 

Abstract data type is one of the most important knowledge we study in CSC148. To begin with, we have studied stack, queue, and tree. The main difference between stack and queue is the data in stack is last in, but first out. Instead, the data in queue is last in, and last out. Furthermore, tree is different from stack and queue. To start with, Tree is constructed by nodes, and each node has its own children nodes, and in the end, it just grows like a tree. Additionally, there are different kinds of tree, such as binary tree and binary search tree. Binary tree is a tree with only left and right children nodes instead of multiple of nodes while binary search tree is the same structure with binary tree, but its left children is always less than its parent node, and right children is always greater than its parent node. 

Moreover, recursion is frequently used in Tree, because the construction of tree is similar to n(n-1)(n-2)...*3*2*1. To be more precise, we need to traverse each children when we are trying to search data in the tree, it is like we are going through the tree one and one step down. And lastly, we have learned big-oh notation (f in O(g)), which means f grows no faster than g, for example, n^2+1 is growing the same as n^2 -10000000, because constant becomes very small when n is huge, and we only need to look at the highest power. 

In conclusion, CSC148 benefits me a lot, and I have learned a lot of knowledge in python so that I am able to write some very simple game such as subtract square. I love programming and CSC148

Revisit an earlier SLOG

I have revisited my slog about Tree, and I agree my analysis  about Tree. To begin with, I understand tree is constructed by multiple of nodes, and in order to traverse, we have to understand the use of recursion first. To start with, the most basic example of recursion is factorial. The fundamental concept of factorial is n(n-1)(n-2)(n-3)......*2*1. Similarly, traversing each children of each nodes is like the process of factorial. Therefore, we can apply recursion in the programming of Tree. In addition, there also different kinds of tree, such as Binary search Tree, which makes sorting and searching faster because it only has left children and right children, and the left children is always smaller than its parent node while the right children is greater. In conclusion, the concept of Tree is pretty straight forward, but the only trick thing is to understand the process of recursion. Firstly, you have to implement the base case of the stop of the recursion, and then you need to write the code for the first few step. And finally, you just need to apply recursion over it. Eventually, Tree becomes easier after you fully understand the concept of recursion.

Slog 8

week9's topic is about inserting on Binary search Tree. To begin with, Binary search tree is a very special abstract data type, because the data in binary search tree is sorted. To be more precise, numbers on left children nodes are always less than their parent nodes and numbers on right children nodes are always greater than their parent nodes. Therefore, it makes easier for computer scientist to insert numbers into binary search tree. Firstly, we need to compare the number we want to insert with the number in the parent node, if the number is less than the number in the parent node, we will insert our number at the left hand side and running recursion on it, otherwise right hand side. As a result, it reduces the running time of inserting function and it will be a very useful method in the future.

Slog 7

week 8's topic is about linked list, which is another abstract data type. To begin with, linked list has some similarity to tree, which are linked is also contract by numbers of node and it is used to store data. However, the construction of linked list is different from tree. Firstly, instead of left and right children, linked list has front and back nodes. To be more precise, self.front refers to the entire linked list. In addition, self.nxt is needed to implement in order to have accesses on the next node. In conclusion, linked list is also one of the most important abstract data type in the study of computer science.

Slog 6

week7's topic is about binary Tree. Binary is a little bit different from normal tree. Firstly, instead of multiple of children nodes, binary tree only has two children nodes. To be more precise, it only has left children node and right children node for each nodes. Moreover, binary search tree is more useful than normal binary tree. In binary search tree, each left children is smaller than their parent node and right hand side children is greater than their parent node. Therefore, it makes easier for computer scientists to manage their data, and it also makes sorting faster. In conclusion, binary Tree is a very useful abstract datatype.

summary of Recursion

The Trace of Recursion:

Recursion is one of the most important methods that I learned in CSC148. To begin with, the fundamental process is to understand how recursion works. Precisely, we begin from chasing easy recursion. For example from the lab handout 3:

def count_elements(L):

    ’’’(list or non-list) -> int

    Return 1 if L is a non-list, or number of non-list elements in
    possibly-nested list L.

    ’’’

    if isinstance(L, list):

        return sum([count_elements(x) for x in L])
    else: 

        return 1 

We should start with the most base case, which is when input is not a list, such as 'hello', therefore, it returns 1 as result. Moreover, we should consider short list as input, for example, [1,2]. Because [1,2] is a list, it satisfies the if statement, therefore, it goes into the for loop which gives us 1 and 2 as input, and then we plug in 1 to the if statement, which returns 1, and so as 2. As a result, we will get a list of [1,1], and the sum of [1,1] gives us 2. Furthermore, we try more complex example, and we eventually convince ourselves that this recursive function returns the number of element inside a list. 

The Use of Recursion:

Recursion is frequently used in Tree, because tree is built with parent nodes and children nodes, and we need to search deep in children nodes to find data. Therefore, it is significant to use recursion to do the search repeatedly. For instance, this is one of the tree function in lab 05:

def list_all(t):
    ''' (Tree) -> list

    Return a list of values in t.

    >>> t = Tree(0)
    >>> list_all(t)
    [0]
    >>> t = descendents_from_list(Tree(0), [1, 2, 3, 4, 5, 6, 7, 8], 3)
    >>> L = list_all(t)
    >>> L.sort()
    >>> L
    [0, 1, 2, 3, 4, 5, 6, 7, 8]
    '''
    if len(t.children) == 0:
        return [t.value]
    else:
        all_list = [t.value]
        for c in t.children:
            all_list = all_list + list_all(c)
    return all_list
This is the completed version of the function list_all. However, there are three steps we need to do in order to finish this function. Writing out the base case is alway the first thing we need to do. In this example, we are asked to return everything in the tree. Therefore, the base case will be if there is none children in this tree, and we can just return its root. Second Step, we need to consider the typical case of this function. Thus, we assume it has one child node, which is 2. And then, the function in the else statement will be changed to all_list = all_list + t.children. In general, we have more than one child node. As a result, we should assume recursion works and apply it into the else statement.

In conclusion, the fundamental concepts of recursion are to write out the base case for the function, and then writing down the special cases with a short example, in the end, applying recursion base on that. However, it is complicated to trace recursion, therefore, we need to work on easy case and prove it works, and then assuming it works for the entire function. Recursion is a very important and useful method that we need to understand in order to solve problems in CSC148.

Slog 4

This week's lecture talks about a new abstract data type, which is tree. Tree can stores data in nodes and each child node is connected by a parent edge, to be noticed that, each node has only one parent node. Moreover, the path of a tree is the number of nodes, and the length is the number of edges. Tree is usually used to represent a hierarchical system. Furthermore, to write a class for tree, it is very important to divide it into two cases. Firstly, writing down the base case for the use of the tree. Secondly, writing the function on special case and then run recursion base on it. Consequently, tree is a very useful way to store data

 

CSC148 Slog 3

This week's lecture is mainly about recursion, which is a function calling itself in its body. And this method is useful for solving problem such as with duplicate same features, for example, calculating the sum in [1,[1,2],[[[1]]]]. In this example, square bracket appears many times and some of it is useless. Therefore, it is more efficient to solve this kind of problem with recursion. However, this kind the of problem can also be solved by using for loop, but recursion is easier to understand and trace bugs. Furthermore, during the trace of recursion, we can simply trace the easy example first, and then we can conclude the result of complicated examples by the previous result. For example, if we know the input of integer will return 1, and a list will put all integers in that list into integer, then we can conclude that the list will return number of integer in that list. In conclusion, recursion is a very useful method.

CSC148 blog2

In the first few week, CSC148 covers many knowledge, such as the recap of class, and  special methods in the class, and brief introduction of abstract data type. Importantly, inheritance is completely new to me and it is one of the most significant topic in CSC148. To begin with, inheritance separates two kind of classes, parent class and children class. To be more precisely, parent class is the supper class that including general methods, such as init, str, eq. However, some specific methods cannot be written in the parent class because it is going to be different cases diver circumstance. For example, employ can be divided into hourly employe and salaried employe. Therefore, they are going to be paid differently and methods needs to be written in specific child class. Moreover, exception is mentioned in inheritance. Firstly, exception is used to ignore some errors because it is no need to care about them but programmer still wants the code works. For example, there could be a amount of pay in the employe parent class, but it cannot be written so far due to lack of information on how employe is paid. Therefore, programmer just need to write 'Not ImplementError' under the methods, and the code will run it without errors and programmer can add more information in the children class. In conclusion, inheritance is a very important skill for designing class.

CSC148 SLOG 1

It is significant for Computer scientists to write debugging journals, because it is convenience and promotional. To start with, computer scientists may find out some bugs during designing a program, and finding out bugs and resolving the same bugs are wasting of time. Therefore, it is a good habit to keep track of debugging journals so that computer scientists can easily solve the same bugs with shorter time and fewer efforts. Moreover, it is important to write debugging journal because it can promote your knowledge and memories by making clear all the details in the codes, and it can improve the problem solving skills and the understanding of debugging. As a result, to become a computer scientist, writing debugging journals will be part of the job and it will significantly improve the quality of the coding.