Week 10

   This week, we also focused on sorting, and during the lab, we have finished coding the inorder function which returns the first node in a linked list that contains every value from the binary tree, and its longest path. The first one was easy to think up, but for the second one, we should apply the theory of big-o, and this take me more time to finish. Next week, we will have the midterm II test, so during this weekend, I should work hard to review the past materials. My weaker point is the recursion, I still could not think up a recursion in a natural and easy way by myself, as a result, I need to do more exercises, and read more examples. There are only 2 more weeks, hope everyone can get a ideal result in CSC148. Have a good weekend, but do not forget studying!

Week 9

   During Week 9, we learned about Big-O in class, and solved some BST problems in the lab. At first I had little knowledge of the helper function, but after the lab, I realized that writing a function can make the whole code easier to understand. For example, we want to calculate the factorial of n, we can write the following code:
def _fact(n):
    if n == 0:
        return 1
    return n*_fact(n-1)

def fact(n):
    n0 = int(n)
    if n0 != n:
        raise ValueError
    if n < 0:
        raise ValueError
    return _fact(n)
 
  Big O notation is used to classify algotithms by how they respond to changes in input size, and it usually provides an upper bound on the growth rate of the function. In the runtime problem of python, we call it the worst-case scenario.In CSC240 and CSC165, we have already learned about this concept, so this is easier for me to understand.
  As for the binary search tree(BST), it makes the related sorting algorithms and search algorithms (like in-order traversal) very efficient.

Week 8

  In Week 7 and Week 8, we focused on the topic LinkedList during the lecture and the lab. LinkedList is an interesting data structure, and it is recursively defined. LinkedList is made up of nodes which contain a reference to the next one, and this kind of data is called cargo. During the lab, I have learnt many methods dealing with the LinkedList, like how to add new item to front of the LinkedList, delete item from LinkedList, check whether a LinkedList contains a specific value and find out the position (index) of the value or item in the the LinkedList. The following code is an example of the class LinkedList:

class LinkedList:
    """Linked list class"""

    def __init__(self: 'LinkedList', item: object=None,
                 rest: 'LinkedList'=None) -> None:
        """Create a new LinkedList
        item - The first element of the linked list,
        Not present if self will be the empty linked list.
        rest - The linked list that contains the elements after item.
        Not present if self will be the empty linked list."""
        self.empty = (item is None) and (rest is None)
        if not self.empty:
            self.item = item
            if rest is None:
                self.rest = LinkedList()
            else:
                self.rest = rest
This week's lab is more easier for my partner and I to finish, because we have read and learnt more materials of LinkedList. To learn this stuff well, we should always think carefully about the recursion method. A few weeks are left, I think I should practise more to think up the code much more quickly and correctly.

Recursion

    The recursion method of python is very interesting, because it will call the function itself when you write the body of the function, and this makes the program much more succinct. For example, we want to write a program that reverses the string '12345' to '54321', with the help of recursion, we can write the following code to implement the request.

   def reverse(n):

    def reversestr(s):

        if s:

            return s[-1] + reversestr(s[:-1])

        else:

            return ''

    return int(reversestr(str(n)))

   

   As we can see, recursion can make a question that seems to have complicated steps easier to solve., and there must be a statement in the code to end the recursion (mainly the if or else statement), in the above example, it is the else statement that ends the recursion. Another classic example is the Fibonacci sequence 0,1,1,2,3,5,8,13,21......:

    def fib(n):

        if n<=1:

           return n

        t=fib(n-1)+fib(n-2)

        return t

   Like we want to find the 7th value of this sequence, and we need to add the 5th and 6th values together, and to get the 6th value, we need to find 4th and 5th, and so on. The two values are 0 and 1, so they are constant and will be the end of this recursion.
   Recursion is very useful, but kind of difficult for me to come up with ,so I need to read more materials and do more exercises to improve this skill.