SLOG 9

This week I think I have to look back and see if I agree with my early ideas. I visited SLOG 6，and found that my comprehension on the depth of a node was totally wrong. It should be counted from the root to the node but not from the node to the leaf. Also, I visited SLOG3, and I think I have to supplement something on it. In SLOG3 I talked about the concept of Recursion, but I didn’t mention the way to write a recursion. There are quite a lot of ways to write recursion, and we have to decide which one to use. I can just make some examples to lead.

Suppose we have a nested list [3，[5，6，7],[2，[1]],2], and we want to sum the data inside. By calculating we can easily get the answer, but it is not working for a computer. So we need to write codes by using recursion. One of the skills to write a correct recursion is to find the final thing we operate. In this example, we can tell that those numbers are the so-called final things. So we start the code like this:

def   nested_list(L):

     if isinstance(L,int):

         return L

Then we have to consider about the core of the problem: the way to call the function itself.

If we call [nested_list(x) for x in L] for just once, it means we check if 3，[5，6，7],[2, [1]], 2 are int. If true, then put it into a blank list. If we call it twice, then 3，5，6，7，2，2 are in the list, and there will only be a list [1] still not there. Call it again, we have all the things in the list. All we have to do here is to sum the list. So we can write a code like this:

return sum ([nested_list(x) for x in L]).

To make it clearer, I put the codes together:

def   nested_list(L):

     if isinstance(L,int):

         return L

else:

    return sum ([nested_list(x) for x in L])

I also read the slogs written by some of my classmates, and their idea helps me a lot. Plenty of my classmates are puzzled on testing as well, and I found that we all struggled about the Minimax of the assignment2. Object Oriented Design is not a common problem, since it is the base of CSC148. But I think the easier it is, the more careful we should be. The easiest part is always the part which makes most people careless.

SLOG 8

This week is about testing. It is a really tough and complicated, and I am still very confused about it so that I cannot tell too much on it.

To start with testing, we have to know the reason we test. We test because we don’t know if our codes are running as we expected. So we have to input the expected results and see if it is same as the real answer.

To explain it better, I will make a general example, or we can call it the model.

Firstly, we write ‘ import unittest’ on the top.

Then we create a class, for instance, class TEST, with (unittest.Testcase) after it.

Then we write method.

The first method will be   def setup(self). In this function, all the codes will be operated before every testcase starts. We can initialize all the classed and variables here, and to access in other methods, all the initialized data are supposed to start with self., or be global variables.

The second method should be   def tearDown(self).   Similarly, all codes in this function will be operated before the every testcase starts, but the difference is, they will also be operated after the testcase stops. Since in the testcase, the variables starts with self. that we defined or other global variables will probably be modified by testcase for testing the results, we use tearDown function to make them nothing( self.blahblah = None), like throwing trash.

Finally, we write the key part of the test. We need a method called def test_test_case_name(self), which is allowed to be named by ourselves. Under this method, we need to write four lines of code: Actual = ______, which is the content we test

                               Expected = _______, which is the result we expected

                               Error = _____, which is a hint to let us know that there is an error

                               assert actual == expected, error  # maybe >= or <=

Above are my thoughts about test, maybe now it is still childish, but I will try to learn it

better. 

SLOG 7

This week we had our midterm exam, and we spent some lecture time doing some 

review.The new things we learnt this week is the Binary Search Tree. To simplify, I will call 

it BST and the Binary Tree BT.

The only difference between BST and BT is that there is a rule in BST : left child <node< 

right child. Since three is an order among nodes in BST, it will be an extra time for a BST to 

keep its property when doing insert and delete. Also, based on the property, we can exactly 

know whether it goes left or right. Through if statement, we can control the direction of 

Recursive steps.

For example, I would show the way I write method on BST.

def insert (node, data):

      return_node = node

      if not node : 

                     return_node = BTNode(data)

      elif  data < node.data:

                     node.left = insert(node.left, data)

      elif  data > node.data:

                     node.right = insert(node.right, data)

      

      return return_node

Above is just my way of write method insert, and there may also be some other ways. The 

most vital thing is that we create BST to search data more conveniently, so we should not 

make the method very complicated. 

SLOG 6

This week we learnt an interesting new thing called tree. Tree looks like this:

We can utilize this picture to analysis the concept of Tree. On the top, we see a node (2) with no parent but with children. This is a root. At the bottom, we can find nodes(5，11，4) with no children, and they are called leaves. A subtree is defined as trees that are formed by any tree node together with its descendants and the edges leading to them.

We are also given the concept height, depth and arity, branching factor. 

In this picture, the longest path is 2----5----9----4(or 2----7-----6----5 or 2----7-----6----11), so the height of this tree is 4. The height of a node, for instance, 6，is 3，since the maximum path to the root is 6----7----2.

The depth of a node means the height of the entire tree minus the height of a node. For example, the depth of 6 is 1，since the height of the entire tree is 4，and its own height, as we mentioned above, is 3.

Artiry, branching factor is an interesting concept. It means the maximum number of children. It is a kind of restriction. Sometimes that will be more restrictive: sometimes the right children must be larger than the left children.

This week we also learnt things about LinkedList. Basically, it is a connected list, which is connected node by node. Simply, it can be considered as a tree whose branching factor is 1. But it is not that simple as it looks like.

Generally, LinkedList is expressed in this way: 3 ->2->1->0|, which means the list [3,[2,[1,[0] ] ] ]. There are some relationship among the different parts in this list.

Wrapper class is very important for LinkedList, because LinkedList is list and we have to know its size. Size is not supposed to be in an individual node, and wrapper class can help us find the size since it can turn a single node into the whole list. Usually, we have the information of the front list and back list in a LinkedList. (front: LLNode -- front of list

back: LLNode -- back of list)

We also mentioned the method to iterate a LinkedList. There are two ways to realize it, which are, respectively, while loop and recursion. While loop is what we learnt in CSC108, and we have to focus on recursion in this course.

Here is some methods that I conclude to solve this recursion problem: No matter what we do to the LinkedList, for instance, append or delete, we have to keep an eye on its front and back Node. When appending, we have to record the Node one space ahead the Node that we are operating now. When deleting, we only need to connect the front node and the back node.

This week the assignment 2 is out as well, and my partner and I are trying to solve the problems. We are now confused about how to express the rules of the game by codes.

SLOG 5

Last week I talked about the concept of Object-Oriented Programming, so I may talk about the concept of ADT this week. I’m afraid I cannot explain it very well, since I still have a lot of questions on it.

What does ADT mean? It means Abstract Data Type, literally. But this name still cannot tell anything to a guy who does know computer science. The basic concept of ADT is a Stack that can be modified by adding or deleting the elements. Actually, we can only add or delete the first and last element of a Stack. 

This picture shows the basic meaning of Stack.

We can realize the modification by using the methods push and pop. For example, if there is a Stack like this: S = [1，2，3，4，5], we can push an element to the last of the list if we write S.append (6). Similarly, we can remove the 1 by the code S.pop (0).

SLOG 4

As we have learnt Object-Oriented Programming  for several weeks, I think it is necessary to do some summary for this part.
To start an Object-Oriented Programming, the first step is to create a class( sometimes there may be more than one class) and give its meaning. Then we can start writing the definitions. Usually, the first definition we have to write is initials. It usually includes some key information that appears later.
  then we have to write some string method and representation method, which return a string version of self and a string representation of self.
Then sometimes we may need a method called –equal--, which is created to see if two pieces of stuff in the class are the same.
After writing down these normal things, we usually focus on the method that needs our real intelligence. Since we know this kind of methods follows what we want to realize, we cannot define them as we did above. We may understand them by using an example.
If we want to create something that can calculate the area of any triangle by knowing its three nodes, we have to firstly import the method Math, and then write something like this:
return (self.base**2 * 3**(1/2)) / 4

Above is how we write basic classes. And sometimes we need to write some subclasses for further usage. The subclasses inherit all the features of the basic class, and we can add the methods in the same way.

SLOG 3

Since last week we had hand in our first assignment of this semester, we had a nice weekend that was not very busy, but we are quickly aware of a new task: the first midterm test is coming. We spent almost the whole Week doing reviews for the term test. We discussed together and figured out much knowledge that we didn't notice, or we can say, ignore the class. For example, we found that the concept of string and representation are almost the same, so we searched many websites and finally got the answer. Simply, string is written for a computer to read, and representation is used for a reader to comprehend. It was very important for us to totally understand them before the test since that can help us not mix their concept and write wrong codes.
 Another thing we met this Week is recursion. Recursion is a way of programming or coding a problem, in which a function calls itself one or more times in its body. So we can use it to express some method that may have to run infinite times, such as calculating the amount of the branches of a tree.
We learnt how to trace recursion. Suppose we have a function:

def nested_list(L):
    if isinstance(L,int)
        return L
    else:
        return max([nested_list(x) for x in L])

and we have a list: lst = [3,[2,1]], we can trace it:
Firstly, we observe the function and find out what it means. Here it means judge if L is an int,and return it if true. So call the function   [nested_list(x) for x in L] once, and we get 3 is an int and [2,1] not. The result is [3]. Call it twice, we have the result[3,2,1]. As the code says, we finally sum it, and the result 3+2+1=6.
Until now we can only read and find out the result of a recursion, but I believe that soon we will learn how to write a correct recursion on our own.