Names, Tracing, Abstraction recursion @-@

Names:

- Every name → contains a value → a reference to the address of an object
- Search names in order:
  innermost scope(function body, usually) local
  ↓
  enclosing scopes nonlocal
  ↓
  global(current module or __main__)
  ↓
  built-in names


http://docs.python.org/3.3/tutorial/classes.html#python-scopes-and-namespaces

Methods:
   The first parameter, conventionally called self, is a reference to the instance:
   e.g. >>> class Foo:
         ... def f(self):
         ... return "Hi world!"
         ...
         >>> f1 = Foo()
   So now Foo.f(f1) means f1.f()


Tracing:
   Recommended:
    - Tracing the simplest(non-recursive) case
    - Tracing the next-most complex case, plug in known results
    - Same as previous step


 Use Visualizer!

Identity, Information hiding, Reduce

1.Hiding attributes:

class C: def __init__(self): self._x = None def getx(self): return self._x def setx(self, value): self._x = value def delx(self): del self._x x = property(getx, setx, delx, "I'm the 'x' property.")

If given, doc will be the docstring of the property attribute. Otherwise, the property will copy fget‘s docstring (if it exists). This makes it possible to create read-only properties easily using property() as a decorator:

Make something 'READ-ONLY':
example:

def get_children(self: 'RegexTreeNode') -> list:

"""get private children"""

return self._children

children = property(get_children, None, None, None)

2.Equality:

Want two things that point to the the same content to be equivalent!

For RegexTreeNode:
we want to check whether they have the same symbols and the same children:

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

"""is this RTN equivalent to other?"""

return (self.symbol == other.symbol and

all([c1.__eq__(c2)

for c1, c2 in zip(self.children,other.children)]))

3.Reduce:

Reduce  allows you to combine the elements of an iterable into a single, somehow reduced value.


Example: suppose you want to multiply all the numbers in a list:
from functools import reduce
reduce(int.__mul__, [1,2,3,4,5])

wiki-link for MapReduce: http://en.wikipedia.org/wiki/MapReduce

Sorting Big-Oh(Comb with CSC165)

-Methods: 

 1. The Bubble Sort:

     Go Through list, compare pair by pair. (sorted from the front)

   

  2. The Selection Sort:

      Select min/max to front/end of list at one turn.

   

  3.The Insertion Sort:

     Start from beginning, insert next to right position.

  

  4. The Merge Sort:

       split the list and recursively invoke a merge sort on both halves. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list.

  

 5. The Quick Sort:

     A quick sort first selects a value, which is called the pivot value.The role of the pivot value is to assist with splitting the list. The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will be used to divide the list for subsequent calls to the quick sort.(as shown in lecture)

    

-Codes:

  # some sorts
import sys
#sys.setrecursionlimit(1000000)

def select(L):
    """Produce copy of L in sorted order

    >>> select([3, 1, 2])
    [1, 2, 3]
    """
    L1 = L[:]
    for i in range(len(L1)):
        m = min(L1[i:])
        j = L1[i:].index(m) + i
        L1[i], L1[j] = L1[j], L1[i]
    return L1


def quick(L):
    if len(L) > 1 :
        return (quick([x for x in L[1:] if x < L[0]])
                + [L[0]] + quick([x for x in L[1:] if x >= L[0]]))
    else :
        return L

def merge(L1, L2):
    """return merge of L1 and L2

    >>> merge([1, 3, 5], [2, 4, 6])
    [1, 2, 3, 4, 5, 6]
    """
    L1.reverse()
    L2.reverse()
    L = []
    while L1 and L2:
        if L1[-1] < L2[-1]:
            L.append(L1.pop())
        else:
            L.append(L2.pop())
    return L + L1 + L2

def merge_sort(L):
    if len(L) < 2 :
        return L
    else :
        return merge(merge_sort(L[:len(L)//2]), merge_sort(L[len(L)//2:]))

def count_sort(L):
    count_list = [0, ] * len(L)
    for i in L:
        count_list[i] += 1

    L[:] = [] # blank slate!
    for i in range(len(count_list)):
        for j in range(count_list[i]):
            L.append(i) 

-Sorting( from http://bigocheatsheet.com/)

Algorithm	Data Structure	Time Complexity			Worst Case Auxiliary Space Complexity
		Best	Average	Worst	Worst
Quicksort	Array	O(n log(n))	O(n log(n))	O(n^2)	O(n)
Mergesort	Array	O(n log(n))	O(n log(n))	O(n log(n))	O(n)
Heapsort	Array	O(n log(n))	O(n log(n))	O(n log(n))	O(1)
Bubble Sort	Array	O(n)	O(n^2)	O(n^2)	O(1)
Insertion Sort	Array	O(n)	O(n^2)	O(n^2)	O(1)
Select Sort	Array	O(n^2)	O(n^2)	O(n^2)	O(1)
Bucket Sort	Array	O(n+k)	O(n+k)	O(n^2)	O(nk)
Radix Sort	Array	O(nk)	O(nk)	O(nk)	O(n+k

Binary Search Tree❤

-Definition:

a binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree.





-Properties:

1. The left subtree of a node contains only nodes with keys less than the node's key.
2. The right subtree of a node contains only nodes with keys greater than the node's key.
3. The left and right subtree each must also be a binary search tree.
4. There must be no duplicate nodes.

1&2 improve the efficiency, which allow us to ignore half the list, either left or right. ❤

 -Specific:
class BST:
    """Binary search tree."""

    def __init__(self: 'BST', root: BTNode=None) -> None:
        """Create BST with BTNode root."""
        self._root = root

    def __repr__(self: 'BST') -> str:
        """Represent this binary search tree."""
        return 'BST(' + repr(self._root) + ')'

    def find(self: 'BST', data: object) -> BTNode:
        """Return node containing data, otherwise return None."""
        return _find(self._root, data)

    def insert(self: 'BST', data: object) -> None:
        """Insert data, if necessary, into this tree.

        >>> b = BST()
        >>> b.insert(8)
        >>> b.insert(4)
        >>> b.insert(2)
        >>> b.insert(6)
        >>> b.insert(12)
        >>> b.insert(14)
        >>> b.insert(10)
        >>> b
        BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
 BTNode(12, BTNode(10, None, None), BTNode(14, None, None))))
    """
        self._root = _insert(self._root, data)

    def delete(self: 'BST', data: object) -> None:
        """Remove, if there, node containing data.

        >>> b = BST()
        >>> b.insert(8)
        >>> b.insert(4)
        >>> b.insert(2)
        >>> b.insert(6)
        >>> b.insert(12)
        >>> b.insert(14)
        >>> b.insert(10)
        >>> b.delete(12)
        >>> b
        BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
 BTNode(10, None, BTNode(14, None, None))))
        >>> b.delete(14)
        >>> b
        BST(BTNode(8, BTNode(4, BTNode(2, None, None), BTNode(6, None, None)),\
 BTNode(10, None, None)))
        """
        self._root = _delete(self._root, data)

    def height(self: 'BST') -> int:
        """Return height of this tree."""
        return _height(self._root)


def _insert(node: BTNode, data: object) -> BTNode:
    """Insert data in BST rooted at node, if necessary, and return root."""
    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

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))


def _delete(node: BTNode, data: object) -> BTNode:
    """Delete, if exists, node with data and return resulting tree."""
    # Algorithm for _delete:
    # 1. If this node is None, return that
    # 2. If data is less than node.data, delete it from left child and
    #     return this node
    # 3. If data is more than node.data, delete it from right child
    #     and return this node
    # 4. If node with data has fewer than two children,
    #     and you know one is None, return the other one
    # 5. If node with data has two non-None children,
    #     replace data with that of its largest child in the left subtree,
    #     and delete that child, and return this node
    return_node = node
    if not node:
        pass
    elif data < node.data:
        node.left = _delete(node.left, data)
    elif data > node.data:
        node.right = _delete(node.right, data)
    elif not node.left:
        return_node = node.right
    elif not node.right:
        return_node = node.left
    else:
        node.data = _find_max(node.left).data
        node.left = _delete(node.left, node.data)
    return return_node


def _find_max(node: BTNode) -> BTNode:
    """Find and return maximal node, assume node is not None"""
    return _find_max(node.right) if node.right else node


def _height(node):
    """Return height of tree rooted at node."""
    return 1 + max(_height(node.left), _height(node.right)) if node else -1


class BTNode:
    """Binary Tree node."""

    def __init__(self: 'BTNode', data: object,
                 left: 'BTNode'=None, right: 'BTNode'=None) -> None:
        """Create BT node with data and children left and right."""
        self.data, self.left, self.right = data, left, right

    def __repr__(self: 'BTNode') -> str:
        """Represent this node as a string."""
        return ('BTNode(' + str(self.data) + ', ' + repr(self.left) +
                ', ' + repr(self.right) + ')')

    def is_leaf(self: 'BTNode') -> bool:
        """Is this node a leaf?"""
        return node and not self.left and not self.right
 

27.8. Glossary

binary operator

An operator that takes two operands.

binary tree

A tree in which each node refers to zero, one, or two dependent nodes.

child

One of the nodes referred to by a node.

leaf

A bottom-most node in a tree, with no children.

level

The set of nodes equidistant from the root.

parent

The node that refers to a given node.

postorder

A way to traverse a tree, visiting the children of each node before the node itself.

prefix notation

A way of writing a mathematical expression with each operator appearing before its operands.

preorder

A way to traverse a tree, visiting each node before its children.

root

The topmost node in a tree, with no parent.

siblings

Nodes that share a common parent.

subexpression

An expression in parentheses that acts as a single operand in a larger expression.

Linked Structures

Linked lists are made up of nodes, where each node contains a reference to the next node in the list. In addition, each node contains a unit of data called the cargo.

A linked list is considered a recursive data structure because it has a recursive definition.

A linked list is either:

1. the empty list, represented by None, or
2. a node that contains a cargo object and a reference to a linked list.

i.e. sequence of nodes, each with a value and reference to next node.(Use 'next'?)

e.g.

class Node:
    def __init__(self, cargo=None, next=None):
        self.cargo = cargo
        self.next  = next

    def __str__(self):
        return str(self.cargo)

 

24.11. Glossary

embedded reference

A reference stored in an attribute of an object.

linked list

A data structure that implements a collection using a sequence of linked nodes.

node

An element of a list, usually implemented as an object that contains a reference to another object of the same type.

cargo

An item of data contained in a node.

link

An embedded reference used to link one object to another.

precondition

An assertion that must be true in order for a method to work correctly.

fundamental ambiguity theorem

A reference to a list node can be treated as a single object or as the first in a list of nodes.

singleton

A linked list with a single node.

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.

helper

A method that is not invoked directly by a caller but is used by another method to perform part of an operation.

invariant

An assertion that should be true of an object at all times (except perhaps while the object is being modified).

Object-Oriented Programming & Recursion

This week Task:

As well as your regular entries in your SLOG, this week I'd like you
to write two short paragraphs: one on Object-Oriented Programming, and
one on Recursion.
Each paragraph should state, in your own words, what the concept is
and why it is useful (or not) for computer scientists.


 Object-Oriented Programming:

 Object-Oriented Programming is like we can come up with concepts("objects, instances of classes"), also have approaches attributes to it, which is known as methods.  Languages like C++, Java are example of objext-oriented programming language. This programming paradigm makes programming more flexible and extendable as well as make people enable to simply design something and use it.


Recursion:

Recursion is like a method that repeatedly call itself.
For example, fibonacci sequences( 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...), we have maths definition:


 

we can write in python like,

def fib(n):
   if n == 1:
      return 1
   elif n == 0:   
      return 0            
   else:                      
      return fib(n-1) + fib(n-2)

so we have 

fib(0) = 0

fib(1) = 1

fib(2) = fib(1) + fib(0) = 1

fib(3) = fib(2) + fib(1) = 2

...

This approach is very convenient in programming, as it makes it possible to 

'define an infinite set of objects by a finite statement' because of repetitions. 

Recursion & Testcase

1.Recursion:

a).Recursion means “defining something in terms of itself” usually at some smaller scale, perhaps multiple times, to achieve your objective.

i.e. functions can call themselves to solve smaller subproblems. 

e.g. Fibonacci numbers

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)  for n >= 2

def fib(n):
    if n <= 1:
        return n
    t = fib(n-1) + fib(n-2)
    return t 

b). ! Nested-lists:

# some recursive functions on nested lists

def nested_depth(L):
    """
    Return if L is non-list, or 1 + maximum of depths of elements list L.
    Not defined for infinitely nested lists.

    >>> nested_depth(3)
    0
    >>> nested_depth([1, 2, 3])
    1
    >>> nested_depth([1, [2, 3], 4])
    2
    """

    return (1 + max([nested_depth(x) for x in L] + [0])
            if isinstance(L, list) else 0)

def rec_max(L):
    """
    Return the maximum number in possibly nested list of numbers.

    >>> rec_max([17, 21, 0])
    21
    >>> rec_max([17, [21, 24], 0])
    24
    """

    return max([rec_max(x) if isinstance(x, list) else x for x in L])


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

2.Testcase: 

When choosing test cases, consider the following factors:

• Size
  For collections (strings, lists, tuples, dictionaries) test with:
  • empty collection
  • a collection with 1 item
  • smallest interesting case
  • collection with several items
• Dichotomies
  Consider your situation:
  For example:
  • vowels/non-vowels
  • even/odd
  • positive/negative
  • empty/full
  • etc.
• Boundaries
  If a function behaves differently for a value near a particular threshold (i.e. an if statement checking when a value is 3; 3 is a threshold), test at the that threshold.
• Order
  If a function behaves differently when the values are in a different order, identify and test each of those orders.

There is often overlap between the categories, so one test case may fall into more than 1 category.

 - import unittest

 - if __name__ == '__main__':
     unittest.main(exit=False)

 

18.7. Glossary

base case

A branch of the conditional statement in a recursive function that does not give rise to further recursive calls.

infinite recursion

A function that calls itself recursively without ever reaching any base case. Eventually, infinite recursion causes a runtime error.

recursion

The process of calling a function that is already executing.

recursive call

The statement that calls an already executing function. Recursion can also be indirect — function f can call g which calls h, and h could make a call back to f.

recursive definition

A definition which defines something in terms of itself. To be useful it must include base cases which are not recursive. In this way it differs from a circular definition. Recursive definitions often provide an elegant way to express complex data structures, like a directory that can contain other directories, or a menu that can contain other menus.