Saturday, April 4, 2015

Week 12

This week we learned about the big-O notation, which I have already learned in another course CSC165 in last semester. This is the big-O notation:

Big-O notation was not the only knowledge we`ve learned. A new Queue method should be the most important one.
# implement Queue using linked list node
from node_sol import LLNode


class Queue:
    ''' Represent a FIFO queue.
    '''

    def __init__(self):
        ''' (Queue) -> NoneType

        Create and initialize new queue self.
        '''
        self._front = self._back = None

    def enqueue(self, o):
        ''' (Queue, object) -> NoneType

        Add o at the back of this queue.
        '''
        new_node = LLNode(o)
        if self._back:
            self._back.nxt = new_node
            self._back = new_node
        else:
            self._back = self._front = new_node            

    def dequeue(self):
        ''' (Queue) -> object

        Remove and return front object from self.

        >>> q = Queue()
        >>> q.enqueue(3)
        >>> q.enqueue(5)
        >>> q.dequeue()
        3
        >>> q.enqueue(7)
        >>> q.dequeue()
        5
        '''
        new_value = self._front.value
        self._front = self._front.nxt
        return new_value

    def is_empty(self):
        ''' (Queue) -> bool

        Return True queue self is empty, False otherwise.

        >>> q = Queue()
        >>> q.enqueue(5)
        >>> q.is_empty()
        False
        >>> q.dequeue()
        5
        >>> q.is_empty()
        True
        '''
        return self._front == None


if __name__ == '__main__':
    import doctest
    doctest.testmod()
    q = Queue()
    for num in [1000, 10000, 100000, 1000000]:
        q = Queue()
        for i in range(num):
            q.enqueue(i)
        import time
        start = time.time()
        for n in range(1000):
            q.enqueue(n)
        for n in range(1000):
            q.dequeue()
        print('Enqueue and dequeue 1000 items')
        print('starting with {} items in {} seconds.'.format(
            num, time.time() - start))
Finally we approach the end of the term. Final exam is incoming, I am a little bit afraid about it. Just keep calm and carry on, wish I can get a good mark on it.

Thursday, March 26, 2015

Revisit an earlier SLOG

The time passing faster and now is almost the final week of winter semester. Through the computer study at short time, I achieved a lot. I know how to choose a topic and make some preparations for it, also know how to deal with the assignment we solved. What`s the most important is I enjoyed the process working together with my teammates and I think a group`s success is true success, the success belongs to every member. It comes the final of this term. Looking backward to so many things happened during the past three months. I suddenly felt I grew up quickly from the series of problems I had ever met. Life is so difficult at sometimes, putting a lot of troubles together in front of you. I still remembered the midnight three of us were typing on the computer and confused with the extremely hard method—‘Minimax’. Our team fight for it to three a.m. in morning and finally solved it. It was such an excited time I`ve met in my university life. Looking back for the past sLog, I`d found some of my old idea was funny. However some of them were eligible to nowadays computer scientist`s ideology. Wish the strike ended soon and be fast to give my mark of my assignment 2.           :)

Week 9

We took second term test in week 9 and it seems not harder than the first term test. I am guessing it was affected by the strike. Wish it can stop as soon as possible. In week 9 we learned the BTNode again and I know that insert must obey the BST condition. here is the example:
def insert(node, data):
    ''' (BTNode, object) -> BTNode

    Insert data in BST rooted at node if necessary, and return new root.

    >>> b = BTNode(8)
    >>> b = insert(b, 4)
    >>> b = insert(b, 2)
    >>> b = insert(b, 6)
    >>> b = insert(b, 12)
    >>> b = insert(b, 14)
    >>> b = insert(b, 10)
    >>> print(b)
            14
        12
            10
    8
            6
        4
            2
    <BLANKLINE>
    '''.
After the example is the function code of def insert:
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)
    else:  # nothing to do
        pass
    return return_node

Sunday, March 15, 2015

Week 8

Finally!! We solved the minimax problem and the game can run perfectly, uhmm, just in the size of game board for 9 and 16 which means the length of the square was 3 and 4. If the length became larger, the tracing time of the game will growing explosively. Sometime the game will cost 20 minutes of half an hour to decide the next step. Though the time cos a lot, the game can still run in the best way. You will love this game if you have enough time! Last assignment we forgot to run pep8 in our project. This small negligence made us miss the full mark! This time we will not make this stupid mistake and try to get a full mark in assignment2.


This week we learned linked list in our class. It`s not so hard to comprehend. Also we`ve learned how to build a tree when you have some numbers. I thought it was easy but I messed it up at first. Fortunately I knew how to write it in right way.
# On Wednesday (4 Mar) we
# - traced prepend
# - wrote __contains__ from scratch
# - figured out that delete_back needs to find the node one before the end.
#   This can be done by having two pointers traverse the list,
#   with one a step behind the other.

# Exercises
# - write and test delete_back
# - write append (I gave out a handout for that one)
# - Use all the methods.  See how you can use "in" syntax, since we have defined
#   the special method __contains__

class LLNode:
    '''Node to be used in linked list

    nxt: LLNode -- next node
                   None iff we're at end of list
    value: object --- data for current node
    '''

    def __init__(self, value, nxt=None):
        ''' (LLNode, object, LLNode) -> NoneType

        Create LLNode (self) with data value and successor nxt.
        '''
        self.value, self.nxt = value, nxt

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

        Return a string representation of LLNode (self) that can yields
        an equivalent LLNode if evaluated in Python.

        >>> n = LLNode(5, LLNode(7))
        >>> n.nxt
        LLNode(7)
        >>> n
        LLNode(5, LLNode(7))
        '''
        if self.nxt is None:
            return 'LLNode({})'.format(repr(self.value))
        else:
            return 'LLNode({}, {})'.format(repr(self.value), repr(self.nxt))

    def __str__(self):
        ''' (LLNode) -> str

        Return a user-friendly representation of this LLNode.

        >>> n = LLNode(5, LLNode(7))
        >>> print(n)
        5 -> 7 ->|
        '''
        if self.nxt is None:
            return '{} ->|'.format(str(self.value))
        else:
            return '{} -> {}'.format(str(self.value), str(self.nxt))

    def __eq__(self, other):
        ''' (LLNode, object) -> bool

        Return whether LLNode (self) is equivalent to other.

        >>> LLNode(5).__eq__(5)
        False
        >>> n = LLNode(5, LLNode(7))
        >>> n2 = LLNode(5, LLNode(7, None))
        >>> n.__eq__(n2)
        True
        '''
        return (type(self) == type(other) and
                (self.value, self.nxt) == (other.value, other.nxt))



class LinkedList:
    '''Collection of LLNodes organized in a linear sequence.

    front: LLNode -- front of list
    back:  LLNode -- back of list
    size: int -- number of nodes in the list'''

    def __init__(self):
        ''' (LinkedList) -> NoneType

        Create an empty linked list.
        '''
        self.front, self.back = None, None
        self.size = 0

    def __str__(self):
        ''' (LinkedList) -> str

        Return a human-friendly string representation of
        LinkedList (self)

        >>> lnk = LinkedList()
        >>> lnk.prepend(5)
        >>> print(lnk)
        5 ->|
        '''
        return str(self.front)

    def __eq__(self, other):
        ''' (LinkedList, object) -> bool

        Return whether LinkedList (self) is equivalent to
        other.

        >>> LinkedList().__eq__(None)
        False
        >>> lnk = LinkedList()
        >>> lnk.prepend(5)
        >>> lnk2 = LinkedList()
        >>> lnk2.prepend(5)
        >>> lnk.__eq__(lnk2)
        True
        '''
        return (type(self) == type(other) and
                (self.size, self.front) == (other.size, other.front))

#    def append(lnk, value):
#        ''' (LinkedList, object) -> NoneType
#
#        Insert a new node with value at back of lnk.
#
#        >>> lnk = LinkedList()
#        >>> lnk.append(5)
#        >>> lnk.size
#        1
#        >>> print(lnk.front)
#        5 ->|
#        >>> lnk.append(6)
#        >>> lnk.size
#        2
#        >>> print(lnk.front)
#        5 -> 6 ->|
#        '''

    def prepend(self, value):
        ''' (LinkedList, object) -> Nonetype

        Insert value at front of LLNode (self).

        >>> lnk = LinkedList()
        >>> lnk.prepend(0)
        >>> lnk.prepend(1)
        >>> lnk.prepend(2)
        >>> str(lnk.front)
        '2 -> 1 -> 0 ->|'
        >>> lnk.size
        3
        '''
        self.front = LLNode(value, self.front)
        if self.back is None:
            self.back = self.front
        self.size += 1

#    def delete_front(self):
#        ''' (LinkedList) -> NoneType
#
#        Delete front node from LinkedList (self).
#
#        self.front must not be None
#
#        >>> lnk = LinkedList()
#        >>> lnk.prepend(0)
#        >>> lnk.prepend(1)
#        >>> lnk.prepend(2)
#        >>> lnk.delete_front()
#        >>> str(lnk.front)
#        '1 -> 0 ->|'
#        >>> lnk.size
#        2
#        '''
    
#    def delete_back(lnk):
#        ''' (LinkedList) -> NoneType
#    
#        Delete back node of lnk, if it exists, otherwise
#        do nothing.
#    
#        >>> lnk = LinkedList()
#        >>> lnk.prepend(5)
#        >>> lnk.prepend(7)
#        >>> print(lnk.front)
#        7 -> 5 ->|
#        >>> delete_back(lnk)
#        >>> lnk.size
#        1
#        >>> print(lnk.front)
#        7 ->|
#        >>> delete_back(lnk)
#        >>> lnk.size
#        0
#        >>> print(lnk.front)
#        None
#        '''

#    def __getitem__(self, index):
#        ''' (LinkedList, int|slice) -> object
#
#        Return the value at index.
#        # Don't worry about slices for now
#
#        >>> lnk = LinkedList()
#        >>> lnk.prepend(1)
#        >>> lnk.prepend(0)
#        >>> lnk.__getitem__(1)
#        1
#        >>> lnk[-1]
#        1
#        '''

    def __contains__(self, value):
        ''' (LinkedList, object) -> bool
    
        Return whether LinkedList (self) contains value.
    
        >>> lnk = LinkedList()
        >>> lnk.prepend(0)
        >>> lnk.prepend(1)
        >>> lnk.prepend(2)
        >>> lnk.__contains__(1)
        True
        >>> lnk.__contains__(3)
        False
        '''
        current_node = self.front
        while current_node:
            if value == current_node.value:
                return True
            current_node = current_node.nxt
        return False    

if __name__ == '__main__':
    import doctest
    doctest.testmod()

Week 7

In week 7 all of us learnt the new knowledge of Binary Tree Node. Binary tree is harder enough to understand and it cost me a lot of times to consider about it. This was the code of a basic btnode function:
class BTNode:
    '''Binary Tree node.'''

    def __init__(self, data, left=None, right=None):
        ''' (BTNode, object, BTNode, BTNode) -> NoneType

        Create BTNode (self) with data and children left and right.
        '''
        self.data, self.left, self.right = data, left, right

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

        Represent BTNode (self) as a string that can be evaluated to
        produce an equivalent BTNode.

        >>> BTNode(1, BTNode(2), BTNode(3))
        BTNode(1, BTNode(2, None, None), BTNode(3, None, None))
        '''
        return 'BTNode({}, {}, {})'.format(repr(self.data),
                                           repr(self.left),
                                           repr(self.right))

    def __str__(self, indent=''):
        ''' (BTNode) -> str

        Return a user-friendly string representing BTNode (self) inorder.
        Indent by indent.

        >>> b = BTNode(1, BTNode(2, BTNode(3)), BTNode(4))
        >>> print(b)
            4
        1
            2
                3
        <BLANKLINE>
        '''
        right_tree = self.right.__str__(indent + '    ') if self.right else ''
        left_tree = self.left.__str__(indent + '    ') if self.left else ''
        return right_tree + '{}{}\n'.format(indent, str(self.data)) + left_tree


if __name__ == '__main__':
    import doctest 
doctest.testmod() 
Fortunately our assignment do not required btnode inside. Although it do not need it, I and our team were absolutely stuck in the assignment part minimax. It`s so hard that let us working on it for two nights, both night we stay in the lab till three A.M.. At last we still not solved the problem and our team feel disappointment. It`s almost the due date we have to finished it. Wish next night we can finish it..

Sunday, March 8, 2015

Abstract Data Types

In computer science, Abstract Data Types (ADT) is a programming methodology where one defines not only the data structure to be used but the processes to manipulate the structure.

Same as the progress abstraction, ADT can be directly support by any programming languages. To support the ADT, there needs to be mechanisms for defining data structures, which is the basis and the primary in ADT. Second encapsulation of data structures and their routines to manipulate the structures into one unit. It can be compiled at one time by placing all definitions in one unit.


In programming languages, there are some common types of ADTs such as Associative Array (we called it Dictionary in Python), method ‘append’, list, queue and priority queue, storage, method ‘pop’ and ‘push’ (in python), string and the tree we have recently learned it. The data structure should only be accessible from code encapsulated with it so that the structure is hidden and protected from the outside. Users need only care for the interface but not how to realize. This means that as long as the users follow the interface, the ADT can be implemented by any method and will never affect the users.
picture from http://www.cafepy.com/article/python_types_and_objects/python_types_and_objects.html

Monday, February 23, 2015

Week 6 Summary of Object-Oriented Programming concepts

For last week, a new method Tree had been lead into our world of knowledge. Also the tracking recursive functions help us a lot in coding. Mr. Heap said we have learnt all the knowledge we need in assignment 2, there is a bit regret that our team just missed 3 docstring in the last 3 functions which made TA took away 2.5 points in our total marks. However it`s good enough for me and our team will try our best in assignment 2 to get a full mark.

Summary of Object-Oriented Programming concepts

After the learning of chapter 1, as the name indicates that the object-Oriented Programming working around the objects but not the functional action. 
I`ve found some interesting graph on this website:
(www.ldodds.com/lectures/intro2java/OOP_Terms.doc)

Saturday, February 7, 2015

Week 5

Week 5
This week I did not learn so much because of the first term test was hold on Wednesday night. I took the early course which taught by Mrs. Diane but not Mr. Heap because I had to take MAT137 test that night. Mrs. Diane told us about the unit test, which we`ve learned in CSC108. She show us an example of insert_after (L, n1, n2) and run it in unit test. The function was like this:
def insert_after(L, n1, n2):
    """
    (list, int, int) -> NoneType
    
    After each occurrence of n1 in L, insert n2.
    
    >>> L = [5, 1, 2, 1, 6]
    >>> insert_after(L, 1, 99)
    >>> L
    [5, 1, 99, 2, 1, 99, 6]
    """
    
    i = 0
    while i < len(L):
        if L[i] == n1:
            L.insert(i+1, n2)
            i += 1
        i += 1

if __name__ == "__main__":
    import doctest
    doctest.testmod()

The unit test is this:
import unittest
from insert import insert_after

# Note: this test suite does not contain a complete set of test cases.
# Challenge: Extend it to the point that either you are convinced the
# function works as advertised in the docstring, or you have demonstrated
# that it doesn't.

class TestInsertAfter(unittest.TestCase):

    def test_insert_after_at_front(self):
        """ Test insert_after with one occurrence of n1 in L, at the front."""

        input_list = [0, 1, 2, 3]
        return_value = insert_after(input_list, 0, 99)
        expected = [0, 99, 1, 2, 3]
        self.assertEqual(input_list, expected)    
        self.assertEqual(return_value, None)
        
    def test_insert_after_at_back(self):
        """ Test insert_after with one occurrence of n1 in L, at the back."""

        input_list = [0, 1, 2, 3]
        return_value = insert_after(input_list, 3, 99)
        expected = [0, 1, 2, 3, 99]
        self.assertEqual(input_list, expected)    
        self.assertEqual(return_value, None)
        
    def test_insert_after_middle(self):
        """ Test insert_after with one occurrence of n1 in L, not on 
        either end."""

        input_list = [0, 1, 2, 3]
        return_value = insert_after(input_list, 1, 99)
        expected = [0, 1, 99, 2, 3]
        self.assertEqual(input_list, expected)    
        self.assertEqual(return_value, None)
        
if __name__ == '__main__':
    unittest.main(exit=False)

Unit test is not hard enough but it was always the necessary one in function testing. Wish I can get a good mark in test.

Saturday, January 31, 2015

Week 4

The assignment one was due on Thursday night and I handed it in with my workmates on time. We worked on it for more than 2 days, During we were working on it, we smashed it once because we found a extremely mistake which may ruin the game. Really, the progress was painful but we have to do it unless we will fail the first assignment. Although I was sure there must have some mistake in the program(maybe not) will pull the grade down, we were still happy because our game can run in regular way. If you are really thinking about it, I am pretty sure you will be the winner of our game. 
This is week four`s out line, The most important we learn in this week is how to use the subclass. The picture blow can tell us how subclass worked:
In assignment one, we use some subclass in it because we have to guide the function in our program. It was useful and will be the main force in future programming. Not only subclass, raise was also a new knowledge of week 4. sum_list was the new method which was telling us how computer tracing the method. Actually we can realized the answer in our mind, but we still need to know the rules and procedures of computers because we need to be a computer scientist but not a mathematician.

Saturday, January 24, 2015

Week 3

Why geeks should write?

Nowadays, the youth with clear writing style and distinct thought has become less and less, the youth who had grandiose aims but puny abilities become more common. More writing practice can give us a great help in our university life. So why should us, the geeks, need start writing our own blog now? 

Generally, writing blog have a lot of advantages. For instance, you can use your blog to record the valuable idea which was just like a spark, bright and transient. Write it down can make you keep it in mind longer. It does not matter if you forget it, you can still recheck it on your blog. Let somebody read your blog publicly can bring them more idea and thought. Also you can read their blog to absorb other idea that you have ever had before. You may find someone who have the same idea with you and in this case, you can make friend with him or her. Over the network we can find more friends, blog is one of the best idea to find like-minded friend.

Writing is in order to better thinking. Same as memorizing words, watch-only cannot memorized them very well, writing and reading are more helpful to our remember. Although the blogs are posting on the website, not on newspapers or magazines, it is still perfect because of the wide transmission. Besides, teach is the best learn. Once you find you do not know some strange question which you cannot find the answer of it in both book and asking experts. It means your friend zone is not big enough and you need to post your question online, there are more and more talent people can help you. They may teach you how to solve it and finally you learn the knowledge. 

Communicate is an extremely well self-examination. After you absorb the knowledge and solve a question that worried you a lot, you may feel happy and tell your friend who is also confused on this question or the one who is in the same level of thought with you. In fact, if you publish your idea, you must find some other different idea than you. After compared your idea with them, you may find the origin of their answer is totally different than you. So where is the difference? In further communication, both of your guys can compel other sides to give out more deep level reason. The result is both of your guys can learn more and more knowledge which is out of the origin question.

Overall, writing blog can also teach you how to continue a thing in a persistent way. It is hard for me but I will try my best to finish it.