List (Python) (Stack Fix)

At the beginning of the course, I thought that Python doesn't support stack. But in fact Python's list has all the structural elements of stack. Also because of the structure of the namespace (check inheritance link) in
Python, Python doesn't need to implement a separate class for stack like Java. Python has some nice syntactic sugar for dealing with lists.

Other things that make Python great are meta-programming, closures, dynamic loading of modules and portability. It's not that  other language doesn't or can't do these things, it's that it doesn't or can't do them out of the box nor as cleanly. Moreover, you don't need to download libraries. Just install Python and go. Starting in Python and then polishing performance in C is a more efficient workflow overall. That might not be personally true for you.

Sorting (Python)

There are some slow and fast sorting algorithms. We use Big O notation to define it. Big O notation, basically it says how the time needed scales when you add more elements. So a sorting algorithm with O(n^2 ). Sorting a list with 10 elements would need - very roughly - 10^2 = 100 units of time. Big O notation can give us the average time of the sorting algorithm.

O(nlog2n). Fast

• Quicksort: Typically fastest in practice, simple to code and very processor friendly. Also doesn't need any extra space. O(nlogn) is the average case, the worst case for quicksort is O(n^2). The worst case for quicksort is when the list is ordered, since it needs to partition every item in the list. If part of the list is ordered, then we can solve this by choosing randomly a pivot.
• Mergesort: Not as common as quicksort but occasionally useful (sorting stuff on disk for instance). It needs extra memory space compare to quicksort. Mergesort efficient is same for its worst case and best case.  

O(n^2). "Slow" can be deceptive, if the data is small, or nearly sorted, these may be faster than the "fast" algorithms.

• Selection Sort: Easy to understand and commonly taught but rarely used (insertion sort better in pretty much every way). Selection sort efficient is the same with every list since it would iterate every item with any case. 
• Insertion Sort: Simple algorithm, works well for small arrays. Also runs almost linearly for nearly sorted lists. Pretty common to use this instead heavy-duty sorts for simple jobs. The best case for insertion sort is when the list is ordered, then it will be O(n). The reason is that it doesn't need to shift the items in the list when sorting, hence O(n).

Recursion Tracing (Regex Assignment 2)

Back to the post of recursion, there are two kinds to trace a recursion algorithm. Tracing step by step and tracing by faith. This assignment is about converting a string of regex to regex tree and marching a regex tree to a string of binary. Converting a string of regex to regex tree, we iterate each token of the string and build it into the tree when we counter an end parenthesis. Is not hard to trace, since being just one level. What is challenged is second part of the assignment, marching a regex tree to a string of binary, especially star node.

There is this particular example:
((1.(0|1)*).0) matches any string that starts with '1' and ends with '0'.  Lets say that is marching with '11111' and the bar and dot node work as it should be. The hard part is to implement the starnode to know where to  stop tracing the string of binary. For example if the starnode doesn't know where to stop, it will return True without checking the last dot node. The solution is to check every possible split of the string of binary:
...
        elif isinstance(tree_regex, StarNode):
            if len(partition) is 0:
                return True
            else:
                for i in range(len(partition), 0, -1):
                    if match(tree_regex.children[0], partition[:i]):
                        return match(tree_regex, partition[i:])
                return False
...

For human to trace step by step is really hard, since each split is a level deeper. Human are only good at tracing two levels of details. This case is the perfect example to trace it by faith. First, just try tracing a simple string, like '110' and '111'; if it work, then hope that it will work with complex string of binary.

This assignment helps me to realize why tracing step by step is hard for human.

Memory Model (The tour of Anne Hoy; Assignment 1)

The tour of Anne Hoy is much like the tower of Hanoi with the difference of using four pegs instead of three pegs. Starting with the assignment we have the knowledge of the algorithm for the tower of Hanoi. So the tricky part of the assignment is not implementing on how to move the disk(cheese), the tricky part is to implement the splitting part of the first peg.

Equation of TOAH

So basically find the optimal i of M(n). The solution is to pick different i and try them all to see which one is fit for n. If you didn't save the i for that particular n, every time it run to find the i for (n+1), it need to find i for n again, which is not very efficient. So the solution is memory model. It stores every i that had run before. It also called memorization. There is this function that Danny Heap wrote that you only need to input the function that you want to memorize; it will record the output for future use. With the additional advantage that it will secure the table you need to memorize, because only the function can access the table.

I can see why Danny didn't teach us the use memorization before the assignment. It will only confuse us, such as inputting a function as a parameter. After knowing how Python works around its object with namespace, this all makes sense.

Sorting

Sorting algorithm is the most essential element for computing big data or for working with large data. Think about this:

You have a list of names of 1000 people, in a random order. You need to sort this list of names into alphabetical order. You can only look at one letter in each name at a time. How do you do it in the most time efficient way? You'd probably start by running your eye down the entire list, and get everyone whose name starts with A and put them at the top. Then you'd run your eye down again and put everyone whose name starts with B underneath all the As. Do that until all the names are in first-letter alphabetical order. But then you realise the list of names starting with A isn't in alphabetical order! Azir is in front of Aaron! That's wrong! So you run your eye down each second letter of the names, and put them in order according to the second letter. But then they're still not in alphabetical order, because of the third letter in the names! Aaliyah is in front of Aaron! So then you start sorting the A's by fourth letter....

So you do this until the entire list of A's are sorted. But then you need to do the same thing for the names that start with B! And C! And D! As you can see, it would take an extremely long time to sort a large list of names. It even takes a computer, which can look at millions of names per second, a relatively long time. Especially when you have a list of 1,000,000s of names!

Essentially some clever people notice that there must be a better way to solve this. As time passes they have came up with many different ways for computers to sort large lists like these. There are many different ways (algorithms) that computers can sort, and the most efficient way depends on what kind of data is being sorted. Names? Numbers? Dates? They're all different and require different ways of sorting. Some algorithms first sort the list by length of the name, then by alphabetical. Some advance sorting would split the list in half, and get each core in your dual-core computer to sort each list individually, then combine them at the end. Some count how many unique elements exist in the list, assign it a number, then run over and over the list, averaging them, until the list is in perfect order.

Binary Tree (Python)

What is a Binary tree?

A binary tree is a collection of of nodes that are linked by node with child nodes less than the node to left and nodes more than the node to the right. Just like the linked list, binary tree has a recursive definition. The leaves of a binary tree are the node that has no children and interval node are the opposite. The level of the tree is the depth of the recursion minus the head of the tree. 

Inserting node

To insert a node in a tree, first you have to compare with the current node, if the node you are about to insert is less that the current node then insert the node in the left node if not insert to the right node. If the node then equal does nothing. 

Traversing 

Traversing into the tree can be accomplished by either preorder, inorder or postorder. Preorder means to visit the parent first the children from left to right, inorder means to visit the parent in the midway and postorder is after visit the children visit the parent. 

Deleting node

There are three situations when deleting a node. Deleting a leaf, simply remove the node from there. Deleting a node with one child, remove the node and replace it with its child. Deleting a node with two children, remove the node and replace it with its in-order predecessor node, i.e. the rightmost node from the left child. 

Application

Binary tree can be useful to store an expression that is infix. Such as x + y, x * y or (x + y) * x. Binary tree can also be used to construct yes/no conditional question. Binary Tree can be efficient when its element is sorted, and the tree is balance. When the condition is fulfilled, searching in a binary tree have the same efficiency of a binary search, which it's O(log(n)). However when constructing the tree is quite slow comparing to linked list or array list. The worst is when deleting a node from the tree, it has an efficiency of O (nlogn). 

Linked List (Python)

What is a linked list?

A linked list is a list that contains nodes that make the list itself. As you can see linked list has a recursive definition, therefore is possible to implement a linked list with recursive coding. A node within the linked list contain the value or element and a reference to the next node. The linked list contains only the head or the first node of the nodes that forms the list.

Removing a node

Removing a node in the linked list has to be done carefully. A linked list is like a chain of nodes, so removing a node you have to keep track of the rest of the chain from the node you trying to remove. 

Application

Linked list is useful to store a collection of objects, because nature that it can store any type of object in the list. Comparing to others date structure list, linked list is more efficient in various ways. Linked list doesn't have to create and copy its list again when expanding the list. The time is inserted and delete in the middle of the list is constant.  On the other hand, the disadvantages of linked list are the indexing of elements and the space its occupied comparing to an array list.  

Recursion

Recursion is useful in solving problems that will need to solve a smaller version of the problem. Recursion is so great that some computer scientist in the past thought that some problem can only be solved with recursion. Usually the recursive code is presented cleaner and easier to read. Even thought the process of coding it is a pain.  For example coding the infamous tower of Hanoi or the iteration through a tree created with recursion or creating a tree with recursion, will not need to create extra variables to keep track of it.

Fix:
There was a confusion about recursion that I made at the beginning of the course. I stated that recursion should not use selfdomly:
"Nonetheless recursion is being used only occasionally, because recursion inefficient and it takes more than it needed memory to do it. Also because our processor is not designated to run recursion, complex problem may not be handled, even if the coding is right."
I thought that a recursion would cache out all the memories of the CPU and the RAM, faster than iteration. Because I thought that each time a recursion call itself it would copy the function again into the memory address. Apparently it would just move the address pointer back to the original function code. Moreover in the lecture on map-reduce we learn that modern compiler is smart enough to recognize tail recursion and fix it for us.

Recursion (Python)

Recursion means that the code will somehow call itself, usually for some smaller scale of the program. The recursive code will run until it hit the base condition and then it will trace back to the original call. The advantage of  recursion is that it can solve a complex problem with just a few code. There are two ways to visualize a recursion program:

The high-level view

This way of thinking is recommended, because is easier to adapt this thinking without losing your mind, useless you think like a machine. First, you have to convince yourself that the function works with the base case. Then focus yourself on doing a level 1 recursive trusting that the base case would work, then solves the next level without keeping in mind all the detail of level 1 implementation. Then ask yourself, in general if I can assume than n-1 case works, then you can solve n level problem,. If not, declare more base classes or change the recursive part of the code.  

Machine-level operational view

This way of thinking, you have to trace back the whole recursion, level by level. For Example:

_____________________________________________________________________

#http://openbookproject.net/thinkcs/python/english3e/recursion.html

def koch_0(t, size): 

    t.forward(size) 

def koch_1(t, size): 

    for angle in [60, -120, 60, 0]:

         koch_0(t, size/3) t.left(angle) 

def koch_2(t, size):

     for angle in [60, -120, 60, 0]:

         koch_1(t, size/3) t.left(angle) 

def koch_3(t, size): 

    for angle in [60, -120, 60, 0]: 

        koch_2(t, size/3) t.left(angle)

________________________________________________________________________

This is the case, each call it traces back to the previous level of the call, until it hit the base case. 

Common mistakes

1. Forgetting to return the recursive call. If there is no return from the call, it will not return the base case back to the call eventought it had the result that base call. 
2. Forgetting to set a stop conditional to the recursive call. It causes the program to run until there are no more space in the memory to call the recursive function. 
3. If you are assigning the result to a variable, remember to pass the variable on the call too. Because each time the recursive function calls, it will reset the variable. 

Object-oriented programming language

Object-oriented programming language is a programming language focus on treating a set of data as an object. Programmers can freely manipulate the objects without knowing the logic behind of how to manipulate the objects. Not only that object-oriented programming model in the analysis of moving and making connection with the set of data, it also provides encapsulation and security that prevent data from accidentally accessing. Furthermore, the concept of class allows the programmer to create any new type object that is not defined in the language itself and create different kind of connection such as inheritance and polymorphism. Programmers don't have to worry about the memory space that it will need to take to store the new type object.

Object-oriented programming is good for introducing to new computer scientist into computer language or to just solve a simple problem within caring about all the detail behind. But for solving a complex problem, such that it needs to be more efficient or that is needed less memory space, object-oriented programming may not be the best option. Since it will include a lot of code that will be useless for the problem you are solving

Inheritance (Python)

If you master the skill of playing around with namespace, then inheritance in Python would make a lot more sense. Python's abstract data structure is different than Java, so if you are reading this and you had Java background, forget about the relationship of a class with its methods, and the inheritance structure of the parent class or superclass. It's easier to understand if you accept this new idea of inheritance in Python than trying to match the similarities with Java. By the way, when I say you, I meant me; is the way I take note. So when I am rereading this, I would nod to myself, and I feel like 'this guy knows all my weakness, we must be similar'.

Namespace 

To understand namespace, first you have to know that everything in Python is treated as an object. Class is an object, function is an object, attribute is an object, even module is an object, everything is treated as an object. That is why you can access pretty much everything with just dot-something, for example: math.sqrt, math.sqrt(), animal_file.Dog.bite.blood, etc. Because of that, there is no private  in Python, but is convention to state with with an underscore, _object, to indicate that changing this object might crash the code. If you afraid that someone might accidentally replace the object by having an object with the same name, then you use TWO underscores, __object, is the same as writing  Class._object. Then no matter how bad the someone is import your module, no other object can replace your object.

Now, that we clarify that everything is treated as an object in Python, lets see what is namespace. Namespace is a mapping from names to objects. Is a space where it contains the names of the objects. Imagine a grocery store, each item contains a unique bar code, now collect all the bar codes of all the items in that grocery store. The namespace is the list of all the bar codes of that grocery store. This is why Python doesn't  need you to initialize the variable. 

In a Python file, there are several namespaces on different hierarchy. On the top of the hierarchy is the module namespace, then there is class namespace and within a class there is a namespace and furthermore, each function has there own namespace. When you call __main__, there is a namespace for that module and on top of all of that there is the __builtin__ module's namespace which contain the builtin name. Namespace is a space that contain the names of the objects. A scope is a region of the code where a namespace is directly accessible. For example:

_______________________________________________________________________
class fooEx():
foo = "hello"

def foo_function():
          foo = "hey"
          return foo

>>>foo_function()
>>>print(foo)
#output: hello
_________________________________________________________________________________

The foo in the class, has a scope of the class namespace and the foo in the function has a scope of the function namescope. So that means the foo in the class is different than the foo in the function although they have the same name. However you can specify the foo in the function to be in the foo in the class, with the key word, nonlocal.

_______________________________________________________________________

class fooEx():
foo = "hello"

def foo_function():
         nonlocal foo
         foo = "hey"
         return foo

>>>foo_function()
#output: hey

_________________________________________________________________________________

If you want the variable accessible throughout the whole module, use global instead of nonlocal.

Inheritance

Let's say you have to write two classes: Iron_Man and Inception; and your classes need to included the elements that make those movies such a big hit. You will notice that most of the elements of those movies are similar, and you are tired of rewriting those elements again and again. The solution is to write a parent class for those two classes. In Python is really easy to state the class is the child of a class; you just indicate it inside the parenthesis when you are declaring the class. For example:

_________________________________________________________________________________

class Iron_Man(Action):

            pass

class Inception(Action):

            pass

class Action():

           soundeffect = ["boom!", "Whoaa!"]

           def explosion():

                         pass

_________________________________________________________________________________

Every object in the Action class can be access from the child class, so Iron_Man and Inception, both contain the object soudeffect and the function explosion. If you want to add another parent to Inception, add a coma and the name of the parent class after adding the first parent.

_________________________________________________________________________________

class Iron_Man(Action):

            pass

class Inception(Action, Mind_bending):

            pass

class Action():

           soundeffect = ["boom!", "Whoaa!"]

           def explosion():

                         pass

class Mind_bending():

                         pass

_________________________________________________________________________________

Inception class now has the access to Action and Mind_bending class. 

Exception (Python)

Beside, preventing the user to break your code, I find that exception is useful whenever there is a special case that I can't think about at the moment that is needed to be handled. You can also make it to return a message saying that it had caught a special case, then you will know where the special cases you had missed. Before showing how to catch an error, let's define what is exception.

Exception is a class in Python library, which it handles every error that occurs during the runtime. Every time an error occurs in the runtime, the program stops running and it creates an exception object, then it prints out the trackbacks which contain the code line and a message of the error. The message describes the type of error that had been thrown. Python exception's keyword are raise (thrown: java), except(catch), try and finally. When catching the thrown exception object, list the most specific exception first before the general ones, because Python will search the except from top to bottom. The following example shows that the other except will never reach cause the "except Exception" will always catch the thown error:

________________________________________________________________________________

#Danny Heap

#http://www.cdf.toronto.edu/~heap/148/F13/Lectures/W3/exceptions.py

class SpecialException(Exception):
    pass

class ExtremeException(SpecialException):
    pass

if __name__ == '__main__':
    try:
        1/0
        #raise SpecialException('I am a SpecialException')
        #raise Exception('I am an Exception')
        raise ExtremeException('I am an ExtremeException')
        #1/0

    except Exception as e:
        print(e)
        print('caught as Exception')
except SpecialException as se:
        print(se)
        print('caught as SpecialException')
        raise
    except ExtremeException as ee:
        print(ee)
        print('caught as ExtremeException')
        #raise
   

________________________________________________________________________________

Now that you recall how to use Exception, lets go back to the idea that you can catch a special case with exception. Before you go out telling your friends this great idea, let me warn you that this is not a good programming practice, it is just a quick-and-dirty way to keep your code running. If you want to test it propery, create a test class for your code. 



_________________________________________________________________________________



def mean(list, n):

    try:

         result = sum(list)/0

    except:

         print("special case in mean function")

         print("List: " + list)

         print(n)




_______________________________________________________________________________

 

Is a good practice to code in an exception handler to ever user input code to prevent them messing up with your code.

Stack (Python)

Beyond Python Stack

First of all, there is no stack class in Python library, therefore there is no way you can import stack from the library, you have to implement your own stack class. This piece of information cost my friend an hour of searching in google how to import stack from the library. But after you implemented the stack class onto your library, it will be very handy to have it around. Lets quickly define what is a stack.

A stack is a collection of objects that represents a simple last in - first out order. The collection mostly visualizes it vertically. Imagine a pile of cards, the rules are: you can only pick a card from the top of the pile and you can only put a card on top of the pile.

The functions of stack class are is_empty, pop, push, top. 

is_empty: return true if the collection is empty

pop: remove the object from the collection and then return the object

push: add the object on top of the collection

top: return the last added object of the collection

In Python, we can use a list as the collection. For push, append the new object to the list, for pop, remove last object from the list, and for top, remove the last object from the list. This is just how we learned how to implement a stack with a list. It might seems a small concept for this course and you might think why I am making stack such a big deal. It is because when we learned stack with java, we still didn't know about link. So, we have to implement stack with array. It is important to note that java has to initialize an array, so every array occupy limited amount of memory. Therefore if the array is full, we need to create another array that duplicate the data into it. Here are the code:

________________________________________________________________________________

/** http://userpages.umbc.edu/~dcarter2/workspace/Trees/src/javafoundations/ArraySta/ck.java

**/

//********************************************************************
//  ArrayStack.java       Java Foundations
//
//  Represents an array implementation of a stack. The bottom of
//  the stack is kept at array index 0.

//

//

//********************************************************************

package javafoundations;

import javafoundations.exceptions.*;

public class ArrayStack<T> implements Stack<T>
{
   private final int DEFAULT_CAPACITY = 10;
   private int count;
   private T[] stack;

   //-----------------------------------------------------------------
   //  Creates an empty stack using the default capacity.
   //-----------------------------------------------------------------
   public ArrayStack()
   {
      count = 0;
      stack = (T[]) (new Object[DEFAULT_CAPACITY]);
   }

   //-----------------------------------------------------------------
   //  Adds the specified element to the top of this stack, expanding
   //  the capacity of the stack array if necessary.
   //-----------------------------------------------------------------
   public void push (T element)
   {
      if (count == stack.length)
         expandCapacity();

      stack[count] = element;
      count++;
   }

   //-----------------------------------------------------------------
   //  Returns a string representation of this stack.
   //-----------------------------------------------------------------
   public String toString()
   {
      String result = "<top of stack>\n";

      for (int index=count-1; index >= 0; index--)
         result += stack[index] + "\n";

      return result + "<bottom of stack>";
   }

   //-----------------------------------------------------------------
   //  Creates a new array to store the contents of this stack with
   //  twice the capacity of the old one.
   //-----------------------------------------------------------------
   private void expandCapacity()
   {
      T[] larger = (T[])(new Object[stack.length*2]);

      for (int index=0; index < stack.length; index++)
         larger[index] = stack[index];

      stack = larger;
   }

   //-----------------------------------------------------------------
   //  The following methods are left as Programming Projects.
   //-----------------------------------------------------------------
   public T pop () throws EmptyCollectionException 
 {
  if(count == 0)
   throw new EmptyCollectionException("Pop operation failed. Stack is empty.");
   
  T temp = stack[count - 1];
  count--;
  return temp;
 }
   public T peek () throws EmptyCollectionException 
 {
  if(count == 0)
   throw new EmptyCollectionException("Peek operation failed. Stack is empty.");
   
  return stack[count - 1];
 }
   public boolean isEmpty() 
 {
  return count == 0;
 }
   public int size() 
 {
  return count;
 }
}

________________________________________________________________________________

You might think that this concept seems pretty lame. However, the concept of stack goes beyond every code. Almost every complex code uses stack. Everything you do on the computer uses stack, even your calculator uses stack. This is because how the assembly language create functions so that cpu knows where to go back to run the code. So that your code will be run from the top to the bottom, unless you tell is to jump to other section of the code. 

Object (Python)

Functions are objects in Python

I was playing around with objects in Python to seek out the differences between Java object. I found out that functions are objects in Python. It's useful to know; you can do all sort of despicable things that other programing languages would freak out. Let's me show you why with some examples.

__________________________________________________________________________
def happy(word = “I’m happy”):
return word.capitalize() + “!”

>>>print(happy())
# output: I’m happy!

x = happy
>>>print(x)
# output: <function happy at 0x0311D9C0>

>>>print(x())
#output: I’m happy!
______________________________________________________________________________


Since happy() is a function, it is also an object. So that means you can assign the function to a variable like any other object. Notice that it's not using parentheses, cause we are not calling the function, we are assigning the function happy to the variable x. It means you can then call the function happy from x. Moreover, you can delete the name happy and the function will still be accessible from x

____________________________________________________________________________
>>>del happy

>>>print(happy())
# output: Traceback (most recent call last File "<pyshell#9>", line 1, in <module> happy() NameError: name # 'happy' is not defined

>>>print(x())
#output: I’m happy!
______________________________________________________________________________

You may ask, what's the big deal that a function can be assigned to a variable. How about if I tell you that since a function is an object; a function can be defined inside another function, which means a function can return another function! Is pure evil doing that, but no one can stop you. Let me show you how to do it, but don't tell your professor that you learn it from here.
_______________________________________________________________________________

def punch(type="cry"):
    def cry(word="whooa!"):
        return word.capitalize() + "!"

    def punch_back(word="let's fight"):
        return word.capitalize() + "!!!!"

    if type == "cry":
        return cry
    else:
        return punch_back

>>>print( punch())
#output: Whooa!

>>>print(punch("punch_back")()):
#output: Let's fight!!!!
_________________________________________________________________________

You can even pass a function as a parameter!

_________________________________________________________________________
def greetings(word="hey"):
    return word

def foo(func):
    return func + " you!"

>>> print(greetings())
#outputs: hey

>>>print(foo(greetings()))
#outputs: hey you!
____________________________________________________________________________

Those are some examples of the power of Python variable that one can abuse.