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