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.

A linked list. Image from c4learn.com

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.

Object Orientied Programming

What is Object Oriented Programming? In my own words, it is simply a way of classifying data. Just like in the real world, objects have specific attributes. They also have specific methods, or functions. An example of this would be a Car. When I say car, you have a rough idea of what I am speaking about, but you don't know all the details. For example, is the car red or blue? Is it a minivan or a sports car? These details are the attributes, or characteristics of a specific object. Objects also have methods or functions. A car wouldn't be very useful if all it did was sit there. You'd expect the car to be able to move, to be able to transport people or goods from point A to point B. What an object does can be considered its functions (known as a method in programming.) Object oriented programming is an extremely valuable tool for all programmers. It allows you to save a large amount of time, since rather than defining every single object individually, you can define an entire group (or class) of objects which are can be used at will.

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)

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.

Fig. 1 Sierpinski's Triangle

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.

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.

Study Habits

With mid-terms coming up shortly, I've decided to get a head start on studying. Hopefully, I'll be able to avoid last minute cramming this year. Sadly, I make these declarations and never follow through with them. I guess the saying 'Words are cheap' is true.

So following that Idea, I'm going to be posting, right here on this slog, any information that I end up picking up from lectures. I feel that this will help me remember content and encourage me to review.

Something to look forward to in the future eh?