Wednesday, October 23, 2013

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.  

Friday, October 11, 2013

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.

Tuesday, October 8, 2013

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:
_____________________________________________________________________

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

Tuesday, October 1, 2013

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.