Binary Search Tree

Binary Search Trees are an implementation of LinkedList. 

We have seen implementation of List representation of trees. Much like LinkedList, they contain a node which has a root(contains information) and then a self.left which represents the left branch of the tree and self.right which represents the right branch of the tree. 

Ex// 

Tree[3, Tree[5,Tree[6, None,None], None], Tree[8,None, None]]

                                                  3

                                               /     \        

                                             5        8

                                           /   

                                         6      

The implementation of a binary search tree is very similar in its implementation. The requirements of a binary search tree are that there are no repeating node values and any values which are less than the root go to the left branch and a node with a value greater than the root must go to the right branch. This repeats for each subtree. 

More linked list

Last week I though I understood Linked Lists but this week's lab proved that I really did not grasp the concept of linked list.

For some reason, my mind can't grasp the concept of the LLNode referring to a new LLNode, and the concept of replacing such link to reference a new one really blows my mind.

I will try looking it up and read more about it this week and hopefully have more to say about it next week!

Linked List --> Linked List --> Linked List

This week, Linked List were introduced.

Linked lists are made up of Nodes. Each node contains a reference to the next node in the list. In addition, each node contains a unit of data which contains the information such as a string, a integer or a symbol.

A linked list is considered a recursive data structure because it has a recursive definition. The linked list calls itself every time it moves onto the next node.

A linked list is either:

 - the empty list, represented by None, or

 - a node with a root and a reference to the next node.

Lists are useful because they provide a way to assemble multiple objects into a single unit often referred to as a collection. They are, in many ways, very similar to list because they contain a collection of information. What makes them arguably better is that they take less time to manipulate. They are more easily traversed that lists. Modifying a linked list also takes less time that modifying a list.

Take the example of wanting to add the integer 1 to the beginning of a list.

list = [2,3,4,5]

LinkedList = LLNode(2, LLNode(3, LLNode(4, LLNode(5, None))))

In the list, you would have to add the item 1 to index 0, and then move each index to a new one.

In the LinkedList, one simply has to take the head of the list LLNode(2, LLNode(3, Etc.)) and save that as the link and then create a new head LLNode(1) which now points to the new link.

LLNode = LLNode(1, LLNode(2, LLNode(3, LLNode(4, LLNode(5, None)))))

Recursion(Recursion(Recursion)))

Recursive code... where to begin...?

Think of recursive code as one big circle - in order for a function to run it calls on itself.

Take this example that I found

source: http://www.loyalty.org/~schoen/python/class-4-recursion.txt 

def factorial(n):
 if n == 0:
  return 1
 else;
  return n*factorial(n-1)

The function factorial(n) takes a number n, and then calls on itself with in its body.
The body also requires a base case, in this case if n == 0, which stops the recursive circle. If not the circle will continue until eventually the computer runs out of memory space - which leads to a very ugly output in the python shell. Other wise, it runs through the code until the (n-1) conditions leads to n being equal to 0, in which case it returns 1.

Towers of Hell... i mean Hanoi

Ok... so last week I claimed I found the Tower of Hanoi interesting. Working on the assignment has led me to have very, very , very, VERY different feelings towards it. Or towards the assignment in general.

First of all it was the error message we were getting in part 1... Error: type CheeseView is not highlight-able..
A) what is a type CheeseView
B) Why is it NOT HIGHLIGHT-ABLE?!?

A little while later that problem was solved thanks to the Q&A page on Piazza. Turns out we were replacing the string that we had built with a new CheeseView - 2 hours of debugging later our cheese moves!!

And then we get to the small problem of the recursive part of this assignment.
Oh Reve's puzzle how I hate you.
I understand the code.. I understand what it is supposed to do... I just don't understand why it is not working!!
move4(n, origin, second, destination, third)
Why is it going to the second?

Another 3hours of debugging later and a camp out session at office hours we were missing a helper funciton to move the cheese using three stools - and that is where the Tower of Hanoi code comes in.
The code works! and now all that there is left to do is edit.
YAY!

Towers of Hanoi

This week we went over the concept behind the Towers of Hanoi. The only back ground information I have on them is the version of the puzzle I played as a kid. The most efficient number of moves was definitely not the main goal - instead simply moving all the rings was the objective. 

With more of an in depth look at them, concept behind the Towers of Hanoi to be really interesting.  It is one big logic puzzle, very similar to programming.It also reminds me of programming in the sense that you are trying to complete the given problem in the most efficient way (i.e.: least amount of code) and in the least amount of time (similarly to how programmers want to run the most efficient code). 

I took the time to read up on the background of the Tower of Hanoi puzzle. The most basic way to solve the puzzle requires 2^(n-1) moves, n being the number of rings. This how ever does not provide the most efficient way to move the rings. The most interesting part is that there is no actual formula to provide the most efficient way to move all the rings. 

There are Ph.d level scholar articles written about proving the most efficient way to move the rings. It will be interesting to see how completing this assignment will give me more insight in regards to the Tower of Hanoi. 

PostingError

A little late, but I guess late is better than never! This blog covers material covered during week #4, which is the week that we had Exercise #2 due. 

I found this exercise easy enough... or at least part 1. That part of the code ran first shot - how ever problems arose when I tried implementing the second part. For some reason, it would run for me when I tried it in the python shell yet it failed the majority of the auto-testers. I know my error was in the way I implemented the return statement and how it caught the wrong exception due to the inheritance of other Exceptions.  Time to read up on inheritance...