Week10: Abstract Data Type

The thing I found hard is abstract data type, and also the ADT stack. However, I noticed I have not throughly talked about it yet. Thus, I decide to do some review on it.

First of all, we need to understand what is ADT. ADT is an abstract data type, it is defined by a set of operations(what it does), but without saying how they are implemented. Thus it seems abstract, and makes us wonder, if it cannot be implemented, then why it is useful. The fact is we can but we sometimes do not need to come up with methods and give specific implementation of the method at the same time. If the procedure is separated, then the task is simpler and clearer. Also, some well-known ADT can be used frequently by many people, and similarly, an algorithm can be used in many implementations. Next, there are two unfamiliar words distinguish the "idea of operations" and "implementations of operation". The first one is called the provider, the second one is called the implementor. The division of the work accelerates our process in programming. Another word is "interface", which means a set of operations that define an ADT.

One ADT we have talked for a lot of times is Stack. It consists of four operations: 1) __init__; 2) push; 3) pop; 4) is_empty. The implementation of them is called veneer, because it is very easy and using existing methods. One more thing to indicate, stack has LIFO("Last In, First Out") structure.

Here is how stack is implemented.

class Stack: def __init__(self): self.items = [] def push(self, item): self.items.append(item) def pop(self): return self.items.pop() def is_empty(self): return (self.items == [])

(Source: http://openbookproject.net/thinkcs/python/english3e/stacks.html)

Thanks for reading!!

Week9: Binary Search Tree

Hi! We learned more about Binary Search Tree this week. It is a sorted binary tree, and it is consisting of BSTNode. We also reviewed some sorting functions we have learned in CSC108 i.e. selection sort, insertion sort and bubble sort, and we examined their running time. They are relatively long.

First of all, we have a delete method for BST class and its helper function _delete. The most difficult part for me is to understand what we should do after we find the node we want to delete, when the node has two children. Usually we expect something like it is replaced by either node.left or node.right, and everything just move one step forward and the size decreases by one. Stack and some LinkedList work at that way. However, as we all noticed, the structure of the binary search tree will crash when it has more than two children. Also, we need to ensure node.left is smaller than the node and the node is smaller than node.right. Hence, we find the node with the largest value in node.left and it satisfies the properties of BST.  Moreover, I am thinking about whether we can replace the node by the smallest node in node.right; that seems work too.

As for the running time analysis, BST is sorted, therefore if we want to search a certain data, we can always decide to search either left subtree(smaller than data) or right subtree(larger than data), and the other is ignored. Thus if it is a well-balanced tree with size n, the expected running time will be O(lg(n)) which is the average running time. This is because what we are doing for searching is divide n in half until the exact value is reached, so the number of times is log2 n (2^x = n => x = log2 n ). However, in the worst case i.e. there is only left children or right children, the running time is O(n).

I need to keep working on searching and sorting. There are a lot of ways to do and we shall compare their efficiency in terms of its size n, and its running time when n is significantly large(as n approaches infinity). Thanks for reading and it will be great to receive your comments:)

Week8: Linked List

This week we are introduced to LinkedList, and again it is new and abstract. It has recursive structure. There are two ways to interpret it:

1. The list that made by two parts (1) the value or item; (2) the remaining list or rest;
2. A node or object that has a reference and a value. The reference and value are nodes as well.

In order to understand these concepts better, first we need to know what wrapper and helper are and how they work. Wrappers and helpers increase the clarity of our code, and also they are easier to come up with. For example I wrote a function that will capitalize the word:

def capitalized(word: str) -> str:
      return word.upper()

However, I want to add an explanation in front of my capitalized word. Instead of modifying my original function, I can write a wrapper function:

def capitalized_word(word: str) -> str:
      w = capitalized(word)
      return 'The word I capitalized: ' + w

Inside the wrapper function capitalized_word, capitalized is called directly as a helper function. This is a simple example, and we can just combine these two functions. However, if the case become complex, such as the LinkedList and LListNode, wrappers and helpers become necessary. LinkedList(the wrapper class) is considered as a collection of LListNode(the helper class), therefore it can be decomposed in some sense, and invokes the method of LListNode directly.

Next, we are going to examine methods applied in LinkedList. There are three methods taught in lecture: insert, delete_front, and reverse. Notice that LinkedList is first-in, first-out, therefore, we add object in front of LinkedList. The idea here is create a LListNode that has its next node refers to the LinkedList. When we delete an object, we delete the front LListNode. We implement it by replacing the front node with its next node. Moreover, reversing LinkedList is a bit more complex, so the helper function does the work of reversing LListNode, and the front node is replaced with the reversed LListNode. In addition, the pair of BST(wrapper class) and BTNode(helper class) are similar to LinkedList and LListNode. BST seems more effective in the aspect of storing values. Its nodes are ordered like nodes within a Tree.

Thus, getting familiar with properties and methods of Linked List is not enough for doing well on the course. I really need to practice on more codes and get a deeper understanding on what else it can do. Hope it works~

Finally, thanks for reading my slog and welcome the discussion:)

Week7: Recursion

    We have talked about Recursion through past weeks. This is a main new thing in CSC148 and it has brought lots of difficulties to me. It is not hard to understand; we can trace it through the general cases who ends by a base case, and then we can add them up to see the result.  However, a complex recursive function is hard to come up with.

    A function calls itself recursively is a recursive function. "Recursive" is totally different from "circular" which brought infinite loops. Therefore, I usually start with a simple base case who can stop the recursive function by returning something. Next, I write general cases by calling the function itself; at that time, we can either return final result or accumulate each one. The cases are separated by if statements as the whole function is operated once again, whereas in CSC108, we use while loop to stop repetition as codes run inside the function. Moreover, we always need to check the correctness and even the error of our recursive functions through paper and pencils because we are thinking them based on our understanding on what should our function do in various examples. It is acceptable for me to construct a basic structure of a recursive function at the beginning, and then revise to make it closer and closer to the correct answer. The reason of doing this is it is much easier to trace a recursive function to find out what I have missed than to think about some codes recursively which might start or end at nowhere.

    Recursive functions simplify our codes regards to its efficiency(a function can be used for as many times as you want). We would write recursive function when we can find some patterns from short examples to longer examples. In fact it turns out to be operating same things over and over until the base case is touched, such as it becomes empty. Also, they are good at showing the idea of how the function would run based on the previous step. Therefore, the recursive function only need relatively short codes within a function. Thus, practicing more on recursion is necessary for me as it is hard and important which requires thinking deeply, and I believe it would helps programming a lot!