Week12 - Unittest

Hi Everyone,

This is my last post for CSC148 Winter 2014. In today's class, Danny quickly went over all the stuff that we should know for the final exam. I think the only thing that I didn't pay attention and didn't cover in my post is unittest. This explains why I passed all my example cases, but there were still some errors and failures in my assignments. I will share a typical UnitTest example from my lab work with you. In the end, I will talk about my overall thinking and growth this term.

UnitTest:

When I first unittest, I feel I don't want to use it. We need to write a more complicated code in order to test our function, which can be tested by just typing in the shell or using doctest. 

Now after I suffered some inexplicable errors and failures in my assignments, I understand why we need unittest. But I am not saying that I stopped using doctest. I use UnitTest to test my code, and use doctest to test my docstring examples. We made a big mistake in the past. We should not test our code correctness based on our docstring example, but we can check that our examples are correct based on our code. When testing a code, we need to thoroughly test every case instead of test how does our example perform. For many programmers, the unittest is written before the actual code.

unittest for class:

Following is the unittest we wrote for Motorized class in lab3:

1. import unittest module 

2. import the thing (class) that we want to test

3. write setUp first

4. write thorough test cases for each class's method

(if there is error case, test it as well)

import unittest

from motorized import Motorized, NotEnoughFuelError

class TestMotorized(unittest.TestCase):

    """Example unittest test methods for motorized."""

    def setUp(self):

        self.motor = Motorized(4, 100, 5)

    def testFillUp(self):

        self.motor.fuel_level = 20

        self.motor.fill_up()

        self.assertTrue(self.motor.fuel_capacity == self.motor.fuel_level)   

    def test_correct_TravelTo(self):

        self.motor.travel_to((1000.0, 500.0))

        self.assertEqual(25.0, self.motor.fuel_level)

    def test_error(self):

        with self.assertRaises(NotEnoughFuelError):

            self.motor.travel_to((10000.0, 20000.0))

    

if __name__ == '__main__':

    unittest.main(exit=False)

unittest for function:

The only difference between function unittest and class unittest is that function unittest does not need to setup a certain type object first. We thoroughly write test cases for the function as same as we did for class's each method.


-----------------------------------------------------------end-------------------------------------------------------------------


Well, well...
Time flies~ Now it's the end of the year
I've found slog is interesting, though I know some of you really hate slog ;)
This is my first time to manage a slog and it's in English. I am very proud that I insist on and I wrote out everything that I wanted to say and that I really learned from this course.
I wonder if there was anyone except myself has seen this slog, haha, I guess not. But I indeed enjoyed it and it helped me through my hard times and finally, I mean before the final exam, I did well.
It's also my first time to experience computer programming. Maybe it's an entry-level csc course, so I think it's interesting and not as scary as I heard before. We got lots of supplemental study materials and there were many practices as well. CSC also has very helpful and respectful professors, and I have to thank my TA for answering all the random and weird questions that I had.
I made many friends in CSC108 and CSC148, a lot more than in my other classes, maybe it's due to lots of group work. BUT NO ONE COMMENT ON MY SLOG!!!
Anyway~

Good luck on the final exam and Have a great next year!

(I just can't wait for summer!)

Week11 - Sorting and Efficiency

Hi Everyone,

This week we learned four new kinds of sorting algorithms: quick sort, merge sort, count sort and built-in sort. Quick sort and Merge sort both using a divide strategy to sort the list, which is completely new from what I've learned in CSC108. Count sort uses loops, but it is faster than both Quick sort and Merge sort since it has O(n) complexity. Built-in sort is amazing, it is the fastest sorting algorithm, but I don't really understand how it works until I reached my lab session.

In this post, I am going to talk about Sorting and Efficiency computation that I learned from my extra reading. Then I will use Quick sort and Merge sort as examples to develop their time complexity. After that I will provide a graph from my last lab to compare the efficiency of all the sorting algorithms that we've seen so far. Finally, I will show you what my TA said and what I think for the original creation of Python Built-in sort. Don't miss it!

Reflective Thinking

Danny taught us the way to see the sorting time for different algorithms to check sorting efficiency. Import time module, record the start time before running the sort, then record the end time after running the sort. The difference is the running time for the sort. The less the time, the more the efficient.

A more formal way is to compute the time complexity of a sorting algorithm. Actually, we're already seen implicitly how to compute the time complexity in CSC108. For example, we think of how many iterations are there in a insertion sort's worst for a list of length n. We conclude there will n^2 -n + 1 's iterations, and when n goes to infinity, n^2 grows a lot faster than linear functions. we just ignore these little difference. Similarity, if there are any coefficients, the coefficients can be ignored. Therefore, since we know the running time depends on how many iterations we have, we see the running time is bounded by the n^2. It's time complexity is O(n^2). Time complexity of an algorithm is defined as "to quantify the amount of time taken by an algorithm to run as function of the length of the string representing the input" (Wikipedia). It is always represented by Big-O notation, in our example it is O(n^2).

But I was wondering about some algorithms that may require more space to store values, even it is less time-consuming. So I did some research for sorting algorithms and their efficiency. Best and Worst time complexity comparison is one of those aspects that we need to consider in order to compute the efficiency. For a more complete and formal efficiency computation, we also need to consider the memory needed and whether this algorithm is stable.

I was thinking the sorting algorithm only applies to a list of integer, it only helps to develop our logic skills and there's no practical use. However, after some extra reading, I've changed my mind. For example, a list of countries can be sorted by its population, by area, by country code any so on. It is very beneficial to have a sorted list.

Divide List Sorting:

We've seen three kinds of sort in CSC108: bubble sort, insertion sort and selection sort. I think the sort in CSC108 makes more sense to me intuitively, when Danny talk about insertion sort in class, the first thing I thought of is to play poker. Haha~
But quick sort and merge sort are definitely faster and more advanced than those three sorts we've seen before. They both uses recursion and divide the list.

Quick sort:

Algorithm:

Find a pivot(always the first item in the list)

Compare every item with pivot, smaller goes to left, greater goes to right

Keep doing this until when the left/right only contains 0 or 1 values

Add left list, pivot list, and right list together

"return quick(left) + [pivot] + quick(right)"

Best case:
if the pivot always occurs in the middle of the list.
The list needed to be divided to half log(n) times.
In order to find the pivot point correct position, every item needed to be compared against the pivot value. There is (n) comparisons.
Also, every time we want to divide the list into two parts, we need to use comparisons to find the pivot point position. Therefore, the result is O(nlog(n)).
(Another way of thinking I imagine is, since there is totally n points, all points will be used once to divide the list. Therefore the total time is just the total points * every divide time)

Worst case:
if the pivot on the extreme left or extreme right, leave a very uneven division
Sorting n items divides into sorting 0 item and sorting n - 1 items, then 0 item and n - 2 items, then 0 item and n - 3 items. Therefore, the list needed to be divided (n) items.
In order to find the pivot point correct position, every item needed to be compared against the pivot value. There is (n) comparisons.
Also, every time we divide the list into two parts, we need to use comparisons to find the pivot point position. Therefore the result is O(n^2)

Code:

def quick(L: list) -> list:

    if len(L) < 2:

        return L[:]

    else:

        i = 0

        return (quick([x for x in L if x < L[i]]) +

                [L[i]] +

                quick([x for x in (L[0:i] + L[i+1:]) if x >= L[i]]))

Merge sort:

One main difference between merge sort and quick sort is that merge sort requires more extra memory space. Also, merge sort best case and worst case have the same time complexity.

Algorithm:
Divide the list into half
Keep doing this until when left or right contains 0 or 1 item
Start from this point to merge the divided list together orderly
  Compare left and right, and add item orderly one by one to a new list, as a new left/right
  Compare each item in the new left/right with its corresponding right/left, add item one by one to a new
  list
Keep doing this until all the item are put back

Best Case & Worst Case:
The algorithm for best case and worst case for merge sorting is exactly the same. Since no matter what, we divide the list completely to each single list by each time dividing to half,  then put them back one by one.
The length n list will be divided log(n) times. Then since for each division, we use comparison to compare every item and put them back to a new list. There will be (n) times comparison for every time division.
Therefore, the time complexity for merge sort is O(nlog(n)) in both best case and worst case.

Graph Illustration

Since we didn't save the graph that we did in lab, so I will just post my hand drawing graph. It is not accurate, but the general shape and the growth tend of the function won't be affected too much. We tend to choose some large length list, since we are more interested in the sorting performance when n goes to infinity. I will explain why some sort have the same time complexity but there is still a difference in the following.

We have seen before that Bubble, Insertion and Selection sort all have O(n^2) time complexity. Merge, Quick and built-in sort all have O(nlog(n)) time complexity. In generally, the graph coincides with our computation. Bubble, Insertion, Selection obviously take more time than Merge, Quick and Built-in.

*I will explain Built-in sort after

Bubble > Insertion > Selection:

Bubble checks the entire list every time, and swap items that out of order. 

Insertion only checks some part of sorted list, and insert the first item in the unsorted list to its correct position in the sorted list by swap items with their neighbours. 

Selection find the minimum value in the unsorted list and swap it with the first item in the unsorted list. 

Bubble swaps most, then insertion then selection. Therefore, even though they all have O(n^2), Bubble is the slowest, selection is the quickest.

Merge > Quick > Built-in:
I feel very weird Merge is greater than Quick by compare their complexity, since Quick's worst case is O(n^2), Merge's worst case is O(nlog(n)).
So I go back to think over those two functions.
Merge divides the list to random order single list, then add them one by one to a new list orderly.
However, Quick sort first separates the list into halves less than or greater than the pivot. So the pivot position is already decided simultaneously. At the end the list is divided out, but at the same time all the items have been used as a pivot once, and they are at the position that they should be.
That's what I why merge > quick.

Built-in sort:

Now... We come to the hardest part I thought...

I was frustrated about what indeed the built-in sort is, why it is so fast, what is its time complexity??

So I talked with my great TA ~~

¿Where does Python come from? 

Computer language was written based on another basic language. Python was written based on C. C was invented 1970s, very old ha, but it is the basis for many programming languages that we are using nowadays C++, Java, Python are all C-based languages. So python built-in sort was also written based on C.

¿But, C what?

So I went on googling about these stuff, and understood that Python build-in was originally written based on C's quick sort. That's why it has a complexity O(nlog(n)) the same as Quick sort's complexity. 

Since C is simple and it is a very high-speed language, so the Python build-in sort (which is C Quick sort) is faster than Python Quick Sort.

Thus we can conclude and explain why the running time Merge > Quick > Built-in Sort.

It is a long post this week~ :P
I feel sorting and efficiency is not easy to comprehend. I used to train myself to spin a globe in my head in order to do well in my Geography class. Now, yesterday once more!
How does everyone feel about sorting and efficiency?
Any comment will be appreciated~ Well, especially for the Built-in sort part :D

See you next week~

Week10 - Scope and Namespace

Hi Everyone!

In this week's lecture, Danny still kept talking of A2 implementation. We only learned a new Quick sort, I guess there will be more sorting stuff in the following weeks. So I will just skip it right now, and talk about something that we've missed in the past. 
In Week 5, we learned about Namespace & Space but I didn't talk about since it was only mentioned a few minutes in lecture. Even though this topic is not important for this course, and it takes me a long time to search for other materials to understand it; but I still want to post it here. I feel it really helps me understand more deeply about how each function works. Hope you will benefit from this as well~

Scope and Namespace

Sometimes, computer programming computations are very complex, and we want to break them down into separate steps to create a clearer code. For an example, we want to write function to evaluate the quadratic polynomial ax^2 + bx + c into several steps. (*this example comes from the book Practical Programming, Paul Gries, Jennifer Campbell, Jason Montojo)

1. Scope

def quadratic(a, b, c, x):

    first = a * x ** 2

    second = b * x

    third = c

    return first + second + third

>>> quadratic(2, 3, 4, 0.5)

6.0

Variables that are created with a function are called local variables(first, second, third in this case). Local variables get created each time that function is called, and they are erased when the function returns; therefore, they cannot be used outside the function.

>>>first

Traceback (most recent call last):

  File "<string>", line 1, in <fragment>

builtins.NameError: name 'first' is not defined

The area of a program that a variable can be used in it is called the variable's scope. For example, the scope of a local variable is from the line in which it is defined up to the end of the function. In this case, the scope for local variable first is from "first = ..." to "return..."

2. Namespace

Namespace is a space for names, which stores local variables for a function call. It is a mapping from names to objects. Whenever Python executes a function call, it creates a namespace for this function call exactly.

def f(x):

    x = 2 * x

    return x

>>>x = 1

>>>x = f(x+1) + f(x+2)

It seems confusing, but each function call f(...) has its own namespace. This namespace contains the function's own x, which means the x in every different namespace has different memory address and contains different values. That's how the function works correctly because of different namespaces.

Frames Global variables f id1 x id2 f x id4 Return value id4

Objects id1:function f(x) id2:int 1 id4:int 4

3. Python Searching Order

I was confused with why the following twin-look functions produced different results. In CSC108, Michelle told us it is because in the second function the original list L has also been modified. But I was not actually convinced at that time. Now we can explain it by Python Searching Order:

1. Innermost scope, local variables

2. Enclosing scopes, nonlocal variables

3. Global scope, global variables

4. Built-in names

*The global scope is the scope contains the  current module's global name or __main__ 

*The nonlocal scope is the scope of any enclosing functions

*The outmost scope is the corresponding namespace containing built-in names. 

def H(l):

    for x in l:

        x = x ** 2

    return l

>>>l = [1,2,3]

>>>H(l)

[1, 2, 3]

*When H(l) is called, Python looks into "for x in l" local scope first, there is x in local scope, so Python stops looking for x and operates the command for x in a local scope level. Therefore, l has not been modified. The local scope operation has no effect to nonlocal variable. H(l) returns the nonlocal l and it does not change.

def I(l):

    for i in range(len(l)):

        l[i] = l[i] ** 2

    return l

>>>l = [1,2,3]

>>>I(l)

[1, 4, 9]

* When I(l) is called, Python looks into "for i in range(len(l))" local scope first, there is no l in local scope. Then Python starts to search for l in nonlocal scope, there is l in nonlocal scope "I(l)". Therefore Python operates the command for l[i] with a nonlocal scope level l, each time the nonlocal scope l has been modified. H(l) returns the nonlocal l, which has been modified.

In addition, we can rebind variables to different scopes by using global, nonlocal or local statement as needed.  

sample code: global spam (*spam is a variable here)


That's basically what I know so far, please share with any comment and let's work on this together.
See you then!

Week9 - Binary Search Tree

Hi Everyone,

I feel this week's lab is overwhelming. I think I am good with recursion but I am very unfamiliar with the new Binary Search Tree ADT. BST seems very easy since it belongs to a tree ADT and has all the characteristic of a tree. The only difference is that its nodes are arranged in order "value of left subtree <  value of root < value of right tree". Maybe I will feel better if I practice more in the weekend :P

The logic to build a BST exactly using the logic of build LinkedList using LListNode. Instead of construct a LinkedList this time, we construct a Tree. There are several functions that lighted my mind this week and I am going to share these with you:
1. Three functions from lecture:
"_str(b: BTNode, i: str) -> str", "_find(node:BTNode, data:object)", "_height(node)"
2. One function from lab
write recursive function iteratively (use looping)

Three functions from Lecture:

1. _str

I was wondering what's the difference between  __str__ and __repr__. But since I finished reading A2 part1's requirement for __repr__ method, I started to have a little feeling of it. After I done A2 part1, I think I understand it. __str__ is only to return string of values which is clear and comfortable for human to read, while __repr__ is to generate representations which can be read by the interpreter. That's why when we use __repr__ to represent the binary search tree, "that an equivalent tree will be produced if you cut and paste the representation into a Python shell.

The first function also taught me that we can include the kind of indent we want in our string representation, by just adding the indent parameter "i" to the return statement of string operation.

def _str(b: BTNode, i: str) -> str:

    """Return a string representing self in order, indent by i"""

    return ((_str(b.right, i + '    ') if b.right else '') +

            i + str(b.data) + '\n' +

            (_str(b.left, i + '    ') if b.left else ''))

* we will call this function by _str(b, ' '), the ' ' here indicates we want our indent type be a blank. This blank will be added to anywhere we write i in the return statement. 

2. _find

The _find function indicates the main benefit of Binary SEARCH Tree. This type is very useful and fast for searching the things we want since its nodes are in order. e.g If node value is less than the item that we're searching for, next step we only search its right subtree. 

def _find(node: BTNode, data: object):

    """Return the node containing data, or else None."""

    if not node or node.data == data:

        return node

    else:

        return (_find(node.left, data) if (data < node.data)else _find(node.right, data))

_find is only the helper function of BST's find, with parameter's type BTNode. We will call this function in our BST class to create a find method for BST, which is the one that we actually want to search from. Then the parameter of  BST's method can be BST type, with helper _find function's parameter BTNode type.

def find(self: 'BST', data: object) -> BTNode:

        """Return node containing data, otherwise return None."""

        return _find(self._root, data)

3. _height

But another feature is instead of a single class, we constructed a Node and BST class, and node class is constructed as left, root, right separately. So it is easier to write recursive function and our code is made clearer by this. Let's compare the method that returns the max height of a general tree and of a binary search tree.
def _height(tree):
  """Return length of longest path of tree"""
return 1+max([height(c) for c in t.children]) if t.children else 0

def _height(node):
  """Return length of longest path of tree rooted at node."""
  return 1 + max(_height(node.left), _height(node.right)) if node else -1
This function find left subtree and right subtree separately, we are doing two recursions at the same time. Even though the efficiency is less than we do recursion on the same size, one subtree; the total time spending to find the max height is less than single recursion.

Also, notice we have 0 for base case in _height(tree) but -1 for base in _height(node), this is because we check t.children in tree, we check node(root) in node. If the node has no children, there will be no more height and no extra-added height, so we return 0. If the node does not exist, then we return 

One Function From Lab:

We implemented the count_less method for BST in 4 different ways in this weeks's lab:

1. Recursive Function: 
For this part, we leave our BTNode class unmodified. In BST, we implemented a nested helper function _count_less within our count_less function, and then we called our _count_less within count_less.

2. Recursive Method: 
This time we added a _count_less method to our BTNode class. In BST, we call this method and applied to our self.root. This is exactly followed from the Recursive Function part, simply by removing the "_count_less(root.left, item) + 1 + _count_less(root.right, item) if root.item < item else 0" line to BTNode class. 

3. Recursive Method without None: 
Well, this was easy once we've successfully developed Recursive Method, but it took us some time to figure it out. HAHA~ We implemented it by just deleting the None case from Recursive Method, since now we know our node will never be None.

4. Iteratively with Looping: 

We finished the above three implementations in the first hour and we spent an hour for the last implementation! I can't see why we need to change a recursive function to a looping function, since recursion seems simplified our code a lot and it is easy to write than a loooong looping. But I'd like to talk about our thinking for this function here, for seeking the comment of our TAs and looking for yours! :))

We thought of adding item to the stack to store it first, then we can use pop method to get the node that we want to check with a loop. We decided to push self.root first then consider the different conditions for self.root, if self.root is less than item, then there is a chance the right subtree values are also less than item. We can also push the right subtree to the stack to be checked later. No matter self.root is greater than, less than or equal to the item, we need to check the left tree always. Therefore, if node.item < item, we push (node.right) to the stack, then out of the condition we push(node.left) to the stack. Then we start to check, we pop the end of stack. Since we added node.left every time no matter we added node.right or not, therefore before node.left is None, the poped item will always be node.left.
Then our code actually check all the left subtrees first, then after Stack poped out all "node.left"'s, we started to check "node.right"'s. When the Stack is empty, we did our check for all the potential <item nodes. 
My partner and I had an argument when we've done our codes. She was thinking that we check all the nodes of the BST, which is not efficient since we have an ordered BST. However, I thought we didn't check all, we only check those Potential nodes that have chance to be less than item. We only push node.right if node.item < item. Node.right always has a value greater than node, so once we find node.item is = or > item, we won't push this Node's right subtree.



We also talked Binary Search Tree's searching algorithm this week, but I feel I didn't really get it. Danny has posted a sorting function for next week's lecture, so I guess we will learn more about sorting next week. So I will just skip it here and added to my next post~

How's everyone's summer plan? My friends and I are thinking of going to Banff. I love Luis Lake, it is gorgeous! :D

Week8 - LListNode and Wrapper

Hi Everyone!

I am very confused by the Assignment2 handout, what should we do in Part1?? Any suggestion??
Btw, I am also worried about how our slogs will be marked? Since the handout says we are also going to be marked on our interactions with other classmates, we need to comment and reply to comments. I am actually looking my friends' slogs but I never left a comment. I suppose now I should start to comment :P

Anyway...

I will say the way to build LinkedList with the help of LListNode is not very difficult since we've implemented tree and LinkedList class already, and the logic to write methods is pretty much the same. But I didn't finish lab on time, and this is because of only one method for LinkedList that I didn't pay attention to in last week's lecture -- "__getitem__"

So I am going to focus on Wrapper & Helper, and the "__getitem__" method followed by three very logic-similar methods from lab: "__setitem__"," __delitem__", and "insert".

LinkedList with LListNode:

I was wondering why we learn LinkedList immediately after the tree but it seems more like a list or Stack. This week we construct LinkedList in a new way -- as nodes with a value and a reference to other nodes. I think this LListNode & LinkedList structure is more like a tree.

LinkedList(3, LinkedList(2, LinkedList(1, LinkedList(0, LinkedList()))))

LListNode(3, LListNode(2, LListNode(1, LListNode(0))))
'3 -> 2 -> 1 -> 0 -> None'

Wrapper & Helper:

We've seen helper functions in CSC108 last semester, at that time, we only write function A in global scope and call A in a global scope function B. The function A can be the helper function for any function in global scope. If two or more functions used the same computation, then the helper function can be computation function, and those functions can just call function A for their own use.
In this week's lecture, we learned to write the function A within function B, then the function A is in a nonlocal scope of function B. Therefore, the function A can only be the helper function for function B. Both kind helpers can be used in our programming, but I suppose the second kind will be more common in our class construction. Since we will try to avoid build an extra method for our class in order to let our type make sense.

Wrapper seems like a very new stuff, but we already learned in CSC108 as well. For example, there are  three functions A, B, C. We will can only reach C by B, B by A.
A -> B -> C: then B is the wrapper function for C, helper function for A.
Now we give the formal definition for wrapper: a method that acts as a middleman between a caller and a helper method, often making the method easier or less error-prone to invoke.
I think wrapper here is not well-defined. I would see wrapper as "a function that acts as a middleman....", since we can consider method as a special function that only applies to a certain type. Since wrapper can be used in functions as well.

In this new way to construct LinkedList, we define class LListNode first then define class LinkedList, LinkedList class is the wrapper for LListNode.

__getitem__:

There is one more method for LinkedList that first come up in a ADT: __getitem__(self: 'LinkedList', ind: int) -> object. This method takes an index parameter and returns the corresponding item in the LinkedList. I am only going to talk about the logic here, please see the specific code in the following examples. When I first see a function, I always consider it's special case, it's normal case and in what condition it fails.
First, let's consider the simplest case. It is when index is 0, we return the head of the LinkedList. This is very easy to achieve by returning self.head.
Second, we are going to handle a complicated case. Now, we use recursion. Since every LinkedList has only one rest and self.head is very easy to find, we think of returning the (n-1)-th self.rest.head for the n-th self.rest. For example, for the ind = 3 we will return self.rest.rest.head.
"return self.rest.__getitem__(ind - 1)"
Then, when the function fails?? Since we cannot search for item in an empty LinkedList and LinkedList cannot be indexed backwards. If the LinkedList is empty and when the index is negative, the functions fails and we raise IndexError.

__setitem__:

    def __setitem__(self: 'LinkedList', ind: int, val: object) -> None:

        """Replace element at position ind by val.  

        Raise exception if ind is out-of-range.

        """

        if self.empty or ind < 0:

            raise IndexError

        elif ind > 0:

            self.rest.__setitem__(ind - 1, val)

        else:

            self.item = val

__delitem__:

    def __delitem__(self: 'LinkedList', ind: int) -> None:

        """Remove item at position ind, shifting every item

        after that down by 1.  Raise an exception if

        ind is out-of-range.

        """

        if ind < 0 or self.empty:

            raise IndexError

        elif ind > 0:

            self.rest.__delitem__(ind - 1)

        else:

            self.decapitate()

insert:

    def insert(self: 'LinkedList', ind: int, val: object) -> None:

        """Insert val at position ind, shifting the current occupant

        and all subsequent indices up by 1.  Raise an exception

        if ind is out-of-range.

        """

        if ind < 0 or (ind > 0 and self.empty):

            raise IndexError

        elif ind > 0:

            self.rest.insert(ind - 1, val)

        else:

            self.prepend(val)

* We see these three functions use the exactly same logic as __getitem__, the only difference between them is the last line - Base Case. So we see Base Case is the one that determines what the function actually does and recursive steps are only apply the same operation nested and over and over again.

These are what I benefited most from this week's lecture and lab. Every function is important, I think I will be careful next week try not to skip anything in lecture's materials. 

Hope everyone is doing well in Assignment 2, and please help me if you have any good suggestion~~

See you next week~

Week7 - LinkedList ADT

Hi Everyone!

This week we learned LinkedList ADT it reminds me of Stack ADT though it was generated from Tree ADT. I am not very good at it right now. We didn't finish this topic in lecture. Therefore, I will only talk about LinkedList's basic definition, its  __init__ method and its difference with Stack. At the end I will share with you my lab work for implementing Queue with LinkedList. I didn't finish the lab work during the lab time, so I spend extra hours to work on that. Any comment will be appreciated.  Hope I can say more in next week's post~

LinkedList Definition:

This kind of ADT is generated from Tree ADT, since we can think the LinkedList as a linear tree --- the tree only has one branch and every node has exactly one child. Therefore a LinkedList is a sequence of list each with a head (value) and a reference to rest (its successors).

LinkedList reminds me of Stack and Queue ADT that we learned from lecture and lab. They have very similar characteristic in the form of a linear "list". In addition, their methods such as __repr__, __eq__, is_empty are very similar. Even though some of these methods only appear in one ADT, I guess these methods can be implemented to other ADTs by the same logic. Therefore, I am not going to talked about them here. I will list the main difference between them as following and I will provide the corresponding functions after. 

__init__ method:

def __init__(self: 'LinkedList', head: object=None,

             rest: 'LinkedList'=None) -> None:

    """Create a new LinkedList"""

    self.empty = (head is None) and (rest is None)

    if not self.empty:

        self.head = head

        if rest is None:

            self.rest = LinkedList()

        else:

            self.rest = rest

I thought this __init__ method has no difference with those __init__ methods we implemented before. However, when I got to preprend method's "self.empty = False" I was confused. I thought the "self.item = item" has already showed that head is not None. But after I delete "self.empty = False" and rerun the code with the same example, I understood that only when self.empty = True, the code under this condition will run, self.item can be assigned with item. Otherwise, values cannot be assigned to variables and both self.head and self.rest are still None, as before.

Prepend Method with self.empty = False:

>>> lnk = LinkedList()

>>> lnk.prepend(7)

>>> lnk

LinkedList(7, LinkedList())

Prepend Method Code without self.empty = False:

>>> lnk = LinkedList()

>>> lnk.prepend(7)

>>> lnk

LinkedList()

LinkedList vs Stack: 

Stack: add item to the end, delete item from the end

LinkedList: add item to the front, delete item from the end

As for a LinkedList, the most difficult part I feel is their are linked. In Stack, we can add or delete item by simply attach or detach. In LinkedList, every time we change it, we need to consider both the head and the rest, modify the LinkedList as a whole.

Stack (push, pop):

def push(self: 'Stack', o: object) -> None:

        """Place o on top of the stack."""

        self._data.append(o)

def pop(self: 'Stack') -> object:

        """Remove and return the top item."""

        return self._data.pop()

LinkedList(prepend, decapitate):

def prepend(self: 'LinkedList', head: object) -> None:

    """Add new head to front of self """

    self.head, self.rest, self.empty = head, copy(self), False    

def decapitate(self: 'LinkedList') -> None:

    """Delete head from LinkedList self."""

    if self.empty:

        raise Exception("Can't decapitate empty list!")

    elif not self.rest.empty:

        self.head, self.rest = self.rest.head, self.rest.rest

    else: #self.rest.empty

        self.empty = True #if delete this line,  AttributeError: self has no attribute head

        del(self.head)

        del(self.rest)

*The logic for decapitate is first check if the LinkedList is empty, if it's empty raise error. If it's not empty, then we check if self.rest is empty. If self.rest is empty, the if we decapitate the LinkedList it will be empty. Therefore, we let self.empty = True, and then delete self.head and self.rest. If self.rest is not empty, then decapitate is equivalent to shift the LinkedList one unit to the left. Therefore, self.rest.head become self.head, and self.rest.rest = self.rest.

Implement Queue with LinkedList:

Queue ADT we've seen in our first lab, but at that time we implemented with reference to Stack ADT. In this week's lab, we implemented it with a LinkedList.

Queue: add item to the end, delete item from front

Queue(enqueue, dequeue) *implement by a linkedlist:

    def enqueue(self: 'Queue', item: object) -> None:

        """ Add item to the back"""

        if self.linked_list.empty:

            self.linked_list.prepend(item)

        else:

            self.back = self.back.rest

            self.back.prepend(item)

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

        """ Delete item from the front"""

        a = self.front()

        self.linked_list.decapitate()

        return a

We went to skiing during the reading week~ How's everyone's vacation?
I think the midterm is ok and I did well. How does everyone feel >< ?

Hope I will be more familiar with LinkedList next week~ See you there!

Week6 - Binary Tree ADT

Hey Everyone,

This week we learned a new kind of ADT -- Tree. By learning this ADT, I am more and more familiar with creating a class to represent a type. This Tree ADT leads to a new way of thinking problems. Like Stacks ADT, add to top & move from top; Tree ADT is also well-represented by its name. Tree has branches(subtree), leafs(node with no children) etc. A common kind of tree is a binary tree which contains at most two subtrees.

In this post, I am going to clarify several terminology that bothered me in past few weeks, then I will introduce a implicit recursion, finally I will talk about an important logic to write recursion function from binary Tree type object (simultaneously showing how to traversal a tree).

1. Module vs Class; Method vs Function

When we are implementing class Tree this week, we not only create class method but also outside class, in module functions.
Module is a collection of functions, variables grouped together n a file. Class  is another kind of object that is similar to module, it contains functions and variables. More important, a class is how Python represents a type.
A method is another kind of function that is attached to a particular type. Therefore, only the functions inside a class can be called methods of that particular class.

In particular, __contains__(self: 'Tree', value: object) is method. arity(t: Tree) is a function.
Note another difference in type contract, in method 'Tree' has quotation mark with it whereas in function Tree has no quotation marks. In my opinion, this is because when a method is defined in a class, its first parameter must be variable that represents the object the method is being called on (by convention this called self). This quotation mark is used to separate this particular parameter with others.
Any comment will be appreciated :))

2. __repr__ method

This function shows how to use implicit recursion in a function, which means the exactly function name does not appear in the function but it also calls itself. This is very common when we create class method by modifying special methods.

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

      """Return representation of Tree as a string"""

      return ('Tree(' + repr(self.value) + ', ' +

              repr(self.children) + ')')

3. Traversal a tree

We also learned how to "climb a tree" in different orders, that is what traversal a tree means. The most important thing I learned from this part is to use left tree and right tree to a separate a Tree and recurse a Tree. Instead of just recursing a method within Tree class, I guess this new logic is will be very useful in future studies.

There are three typical traversal: preorder, inorder and postorder.

Preorder: visit root first, then preorder left tree, finally preorder right

Inorder: visit inorder left tree first, then root, finally inorder right

Postorder: visit postorder left tree first, then right tree, finally root

I will provide the Preorder Traversal here since other two uses exactly same logic and their codes are very similar to this one.

def preorder(tl: 'TreeList') -> list:

    """

    Return list of values in tl in preorder

    >>> preorder([5, [4, None, None], [3, [2, None, None], [1, None, None]]])

    [5, 4, 3, 2, 1]

    """

    return [] if tl is None else ([tl[0]] + preorder(tl[1]) + preorder(tl[2]))

This is the first week we see the Tree ADT, I may add more thinking in future posts, if there is some~

We're going to have our 1st term test next week, GOOD LUCK TO EVERYONE!