Linked lists (Week 7)

This week we learnt Linked lists.Linked lists are made up of nodes, where each node contains a reference to the next node in the list. A linked list is considered a recursive data structure because it has a recursive definition. 

A linked list is either: the empty list, represented by None, or a node that contains a cargo object and a reference to a linked list.

Here are some examples:

class LListNode:

    """Node to be used in linked list"""

    

    def __init__(self: 'LListNode', value: object =None, 

                 nxt: 'LListNode' =None) -> None:

        """Create a new LListNode"""

        

        self.value, self.nxt = value, nxt

        

    def __repr__(self: 'LListNode') -> str:

        """String representation of this LListNode"""

        

        return 'LListNode(' + str(self.value) + ', ' + str(self.nxt) + ')'

Review from Term Test 1(Week 6)

We do not have classes this week, due to Thanksgiving Day and Term Test 1.

However, I still learnt a lot from our Term Test and Lab.

Firstly, I learnt when we compare tuples, we only compare the first index. If they have the same first, then we compare the second and so on.

For example:
>>>a = (1, 2, 3)
>>>b = (2, 1, 3)
>>>c = (1, 3, 2)
>>>a > b
False
>>>a < b
True
>>> a < c
True
>>> a > c
False

Secondly, we would like to talk about a very useful thing from our lab.

def squares_build_list(n: int) -> list:
    """list the squares of first n natural numbers
    >>> squares_build_list(6)
    [0, 1, 4, 9, 16, 25]
    """
    L = []
    for num in range(n):
        L.append(num ** 2)
    return L

def squares_use_comp(n: int) -> list:
    """list squares of first n natural numbers
    >>> squares_use_comp(6)
    [0, 1, 4, 9, 16, 25]
    """
    return [num ** 2 for num in range(n)]

By looking these two functions, they do the same things, but second one only wrote 1 line. This is amazing by using List Comprehensions.

Object-Oriented Programming and Recursion(Weel 5)

Object-Oriented Programming is a programming paradigm using "object" - data structures consisting of data fields and methods together with their interactions to design applications and computer programs. Instances and classes are objects. Why it is useful for computer scientists? Because It can greatly improve the success rate of software projects, reduce future maintenance costs and improve software portability and reliability.

Recursion mean that the function of its own call to themselves or subordinates in their own function calls a function to call their own. Why it is useful (or not) for computer scientists? Using recursion can reduce a lot lines of codes. We can slove a large problem by a smaller model. However, its running efficiency is very low.

Share my experience from our A1(Week 4)

Let's read a function from DominStool.py
   

def move(self: 'DomainStools', cheese_to_move: 'Cheese',
             cheese: 'Cheese'):      
        '''
        Raise CannotMoveError if cheese_to_move is the bottom cheese, or its
        size is larger than the size of cheese, or cheese is not at the top
        of a stool. Else, cheese_to_move is removed from the original stool
        to the stool which cheese is in.
        '''                  
        for x in self.stools:
            # If cheese_to_move is the bottom, raise CannotMoveError
            if cheese_to_move == x[0]:
                raise CannotMoveError()
           
            # If the size of cheese_to_move is larger than that of cheese,
            # raise CannotMoveError
            if cheese_to_move.size > cheese.size:
                raise CannotMoveError()
           
            # If cheese_to_move is found in list x, but it is not the last one,
            # raise CannotMoveError, else: remove cheese_to_move from x
            if cheese_to_move in x:
                if cheese_to_move != x[-1]:
                    raise CannotMoveError()
                else:
                    x.remove(cheese_to_move)
                   
        # If cheese is found in list y, but it is not the last one in the list,
        # raise CannotMoveError, else append cheese_to_move to y.
        for y in self.stools:
            if cheese in y:
                if cheese != y[-1]:
                    x.append(cheese_to_move)
                    raise CannotMoveError()
                else:
                    y.append(cheese_to_move)
                    self.num_of_moves += 1

When we first wrote this function, we didn't write green part. Then we always found a bug which we move a cheese to above another, if another cheese is not the top one of that stool, it would raise CannotMoveError. However, after that Error happened, the rest of cheeses could move to any where. We tried many times, eventually we found if cheese_to_move(read part) enter the if statement, it would remove that cheese. However, if we do not have green part, it could only raise CannotMoveError. Then, the bug would produce. It was very interesting. We need to take more attention when we design.

Hello! (Week 3)

Welcome my CSC148 Blog!

I will update my experience with CSC148 regularly.