Regardless, many thanks to all of you who have read this Slog. I hope you have a merry Christmas and happy New Year (or whatever holiday you may celebrate.)
Thursday 5 December 2013
Busy Times
Sorry for the lack of posts recently. I've been extremely busy finishing up various work, and studying for final exams. Hopefully, I'll have a chance to put up at least one more post before the deadline.
Thursday 14 November 2013
Runtimes, Big O Notation.
Simply put a programs runtime is how long it takes a given program to run.
Normally you would think of a computer running your programs near instantly, with little or no delay. This is due to the fact that the majority of programs written by beginners are simple in concept.
Runtimes become an issue when you move to more advanced programs, or begin to use more data in your program. As an example of this, assume you have a list of intergers. [1, 2, 3, 4, 5, 6]
In order to check if a certain number is in the list, a computer must check the first number, then if it is not the number you are looking for, then check the next number. It does this for every number in the list or until the number you are looking for is found.
In the worse case, it would take 6 checks to find the number you are looking for, or to determine the number is not in the list. If you had 10 items in the list, in the worse case you would need 10 checks. If you had 1000 items, you would need 1000 checks.
If you had n items, you would need n checks.
Big O notation is a way of indicateing the worse case scenario of runtimes.
This makes searching a list for one number be O(n) (Pronouced Big O of N).
O(n) is a linear runtime, meaning that if each item added has a constant increase to the number of steps needing to be preformed.
An example of a O(n^2) would be:
#Given n items
for i in n:
for j in n:
print(i, j)
This program has an O(n^2) because you must run the inner loop n times per each cycle of the outer loop. Since the outer loop also runs n times, you have n*n or n^2.
I mentioned last week that a Binary Search (using a binary search tree) has an O(lgn)
lgn is eqivilent to Log2(n). This is because in each case in the tree you are able to eliminate half of remaining tree with each check.
Normally you would think of a computer running your programs near instantly, with little or no delay. This is due to the fact that the majority of programs written by beginners are simple in concept.
Runtimes become an issue when you move to more advanced programs, or begin to use more data in your program. As an example of this, assume you have a list of intergers. [1, 2, 3, 4, 5, 6]
In order to check if a certain number is in the list, a computer must check the first number, then if it is not the number you are looking for, then check the next number. It does this for every number in the list or until the number you are looking for is found.
In the worse case, it would take 6 checks to find the number you are looking for, or to determine the number is not in the list. If you had 10 items in the list, in the worse case you would need 10 checks. If you had 1000 items, you would need 1000 checks.
If you had n items, you would need n checks.
Big O notation is a way of indicateing the worse case scenario of runtimes.
This makes searching a list for one number be O(n) (Pronouced Big O of N).
O(n) is a linear runtime, meaning that if each item added has a constant increase to the number of steps needing to be preformed.
An example of a O(n^2) would be:
#Given n items
for i in n:
for j in n:
print(i, j)
This program has an O(n^2) because you must run the inner loop n times per each cycle of the outer loop. Since the outer loop also runs n times, you have n*n or n^2.
I mentioned last week that a Binary Search (using a binary search tree) has an O(lgn)
lgn is eqivilent to Log2(n). This is because in each case in the tree you are able to eliminate half of remaining tree with each check.
Friday 1 November 2013
Binary Search Trees
As I've explained before, a binary tree is an Abstract data type (ADT) which has one root node, and (up to) two child nodes.
In a binary tree, the values or objects stored may not be in any particular order or form. This means that in order to find a specific object, you would have to traverse the entire tree.
Enter the binary search tree (BST).
A BST operates under the idea that the first value entered becomes the root node for the whole tree. If the second number entered is less than the root (first) node, then it becomes the left child. If it is greater it becomes the right child. This process is repeated for each time an object is added to the tree. It is important to note that a BST can not have duplicates of the same value.
Next, a 3 is added. Since 3 is less than 8 it becomes the left child.
Next, a 1 is added. Since 1 is less than 8, and 1 is less than 3, it becomes the left child of 3.
Next, a 10 is added. Since 10 is greater than 8, 10 becomes the right child.
Next a 14 is added. Since 14 is greater than 8, and 14 is greater than 10, it becomes the right child of 10.
Next, 13 is added. Since 13 is greater than 8, and 13 is greater than 10, it must be to the right of both 8 and 10. However, since 13 is less than 14, 13 becomes the left child of 14.
If we keep going in this fashion, we can finish building the binary search tree.
It is important to keep in mind that the order that you add items to a BST changes the shape of the tree.
When you have a BST, it makes it fast to check whether a specific value is within the tree. For example, if we are looking the number 6, the we would take the following steps to find it.
Start at the root.
If the root is greater than 6, check the left child.
If the root is less than 6, check the right child.
Since 8 > 6, check the left child (Node 3).
Since 3 < 6, check the right child (Node 6).
Congratulations, you found 6.
By having a binary search tree, we are able to eliminate one tree at each check, drastically reducing the number of Nodes we have to check in total. This means when searching, the BST has a O(lg n). (More on this later)
Thursday 24 October 2013
Linked Lists
A linked list is another form of recursive object.
Basically, it is comprised of nodes which consist of two parts.
Each node has an "item" which can be any form of object, and a "reference" which points to another node object.
The rules are that each node may only be referenced, or pointed at by one other node.
In this way, you can make a chain of nodes that reference each other. Using the logic, the last node in the linked list will have a reference value of None.
Another way of thinking of this is as a "Tree" structure, but with a branching, or arity, factor of one.
The advantages of linked lists are:
You are not required to know the number of elements ahead of time unlike in an array. (Less relevant in python)
Linked lists are also flexible in the value or types of objects they can contain.
(Again, less relevant in python)
The addition and removal of items from the middle of a linked list requires significantly less operations and time, particularly if the total number of items is very large.
This is due to the fact that items may be freely added and removed from a linked list by changing their reference pointers, but in an array all of the objects must be copied or shifted to insert or remove an element.
The disadvantages are:
Linked lists are more work to set up than a simple array.
Linked lists must be traversed linearly. That is you can not jump to the 5th node immediately.
This means that performing certain operations, such as sorting, is much more difficult or time consuming.
Basically, it is comprised of nodes which consist of two parts.
Each node has an "item" which can be any form of object, and a "reference" which points to another node object.
The rules are that each node may only be referenced, or pointed at by one other node.
In this way, you can make a chain of nodes that reference each other. Using the logic, the last node in the linked list will have a reference value of None.
Another way of thinking of this is as a "Tree" structure, but with a branching, or arity, factor of one.
 |
| A linked list. Image from c4learn.com |
You are not required to know the number of elements ahead of time unlike in an array. (Less relevant in python)
Linked lists are also flexible in the value or types of objects they can contain.
(Again, less relevant in python)
The addition and removal of items from the middle of a linked list requires significantly less operations and time, particularly if the total number of items is very large.
This is due to the fact that items may be freely added and removed from a linked list by changing their reference pointers, but in an array all of the objects must be copied or shifted to insert or remove an element.
The disadvantages are:
Linked lists are more work to set up than a simple array.
Linked lists must be traversed linearly. That is you can not jump to the 5th node immediately.
This means that performing certain operations, such as sorting, is much more difficult or time consuming.
Tuesday 15 October 2013
Object Orientied Programming
|
Friday 11 October 2013
Recursion, Recursion, Recursion
Hey all,
This weeks tutorial dealt with using recursion to solve various problems, most of which were using nested lists. The problems themselves weren't too bad, but I feel that I still need some practice. (Especially since recursion will be on the upcomming midterm)
This weeks tutorial dealt with using recursion to solve various problems, most of which were using nested lists. The problems themselves weren't too bad, but I feel that I still need some practice. (Especially since recursion will be on the upcomming midterm)
Wednesday 9 October 2013
I'm trying at least
I've been quite busy recently, but I'm getting the chance to throw up this post now.
Currently, week 5 of class is in progress, and I have had both my lectures already. My tutorial is tomorrow so I'll be posting an update on that by Saturday.
For those that don't know, I have two (1 hour) lectures and a two hour tutorial per week. In the future I'm planning on putting up a blog post directly after my first lecture, and a second post for the second lecture and tutorial.
Jumping into the content now:
For my first lecture of the week, was primarily dedicated to information/help for the first assignment. By the point this lecture was given I had completed said assignment. As such I payed almost no attention to the lecture. The majority of the questions seemed to be directed towards creating the required recursive functions.
For the second lecture of the week, after the first assignment was due, recursive structures were covered. It was opened with a look at various recursive objects in nature (such as broccoli.) Following that we covered some terminology, which I don't remember the exact terms but if I saw them I would know them (you know what I mean.) After that we moved to tree diagrams (of the binary type) and covered pre-order, in-order, and post-order.
To elaborate on this, a recursive object is an object that is made of many smaller versions of the same object. An example Sierpinski's Triangle (or any fractal really), where one large triangle is made up of smaller triangles which in turn are made up of even smaller triangles.
In programming, when you have a recursive object the standard way to deal with it is by using recursive functions.
In general, Recursive programming is a very useful tool for programmers as it allows them to repeat the same series of actions over and over without using a loop. It is also a very "human" way to look at problems, using the idea that if X solves one problem of type Y, then X will solve any number of Y-type problems.
As an example of this, let us take a look at a Binary Tree.
A binary tree is a recursive object by the principle that the whole tree can be subdivided into smaller and smaller trees.
A Binary Tree is composed of a Nodes and Edges.
A node is one of the circular objects containing any value, be it a Str, int, or Object.
An edge is a line connecting two nodes together.
A node is a Parent Node if it has an edge that points to a lower node in the tree. Conversely, a Child Node is one that has a parent.
Note that a node can both be a child and a parent.
Each node in the tree will have exactly one parent node. The node without a parent is know as the Root.
Since writing this out in paragraph form is becoming messy, I will just give the term and definition forthwith.
Terminology:
Leaf: a node with no (None Type) children
Internal Node: A node that is not a leaf node (includes root node)
Subtree: any tree formed within the larger macro structure tree
Height: Length of the longest path of edges in the tree
Arity, Branching factor: The maximum number of children any single node can have.
Note that a binary tree has an arity of 2 (hence the term binary)
In-Order: pre-order to left subtree, the root, then pre-order right subtree
Pre-Order: Root, in-order left subtree, in-order right subtree
Post-Order: Post-order left, post-order right, root
I will upload the code for each of these, and the binary tree list later. I don't have them on me at this time, and don't particularly feel like thinking about them again.
Currently, week 5 of class is in progress, and I have had both my lectures already. My tutorial is tomorrow so I'll be posting an update on that by Saturday.
For those that don't know, I have two (1 hour) lectures and a two hour tutorial per week. In the future I'm planning on putting up a blog post directly after my first lecture, and a second post for the second lecture and tutorial.
Jumping into the content now:
For my first lecture of the week, was primarily dedicated to information/help for the first assignment. By the point this lecture was given I had completed said assignment. As such I payed almost no attention to the lecture. The majority of the questions seemed to be directed towards creating the required recursive functions.
For the second lecture of the week, after the first assignment was due, recursive structures were covered. It was opened with a look at various recursive objects in nature (such as broccoli.) Following that we covered some terminology, which I don't remember the exact terms but if I saw them I would know them (you know what I mean.) After that we moved to tree diagrams (of the binary type) and covered pre-order, in-order, and post-order.
 |
| Fig. 1 Sierpinski's Triangle |
In programming, when you have a recursive object the standard way to deal with it is by using recursive functions.
In general, Recursive programming is a very useful tool for programmers as it allows them to repeat the same series of actions over and over without using a loop. It is also a very "human" way to look at problems, using the idea that if X solves one problem of type Y, then X will solve any number of Y-type problems.
As an example of this, let us take a look at a Binary Tree.
.png) |
| Fig. 2 Binary Tree |
A binary tree is a recursive object by the principle that the whole tree can be subdivided into smaller and smaller trees.
A Binary Tree is composed of a Nodes and Edges.
A node is one of the circular objects containing any value, be it a Str, int, or Object.
An edge is a line connecting two nodes together.
A node is a Parent Node if it has an edge that points to a lower node in the tree. Conversely, a Child Node is one that has a parent.
Note that a node can both be a child and a parent.
Each node in the tree will have exactly one parent node. The node without a parent is know as the Root.
Since writing this out in paragraph form is becoming messy, I will just give the term and definition forthwith.
Terminology:
Leaf: a node with no (None Type) children
Internal Node: A node that is not a leaf node (includes root node)
Subtree: any tree formed within the larger macro structure tree
Height: Length of the longest path of edges in the tree
Arity, Branching factor: The maximum number of children any single node can have.
Note that a binary tree has an arity of 2 (hence the term binary)
In-Order: pre-order to left subtree, the root, then pre-order right subtree
Pre-Order: Root, in-order left subtree, in-order right subtree
Post-Order: Post-order left, post-order right, root
I will upload the code for each of these, and the binary tree list later. I don't have them on me at this time, and don't particularly feel like thinking about them again.
Subscribe to:
Posts (Atom)