Sorting & Efficiency

Sorting & Searches

This week's lab had us work with all sorting algorithms. These include: Insertionsort, Bubblesort, Mergesort, Quicksort, and Python's built-in sort Timsort(which you can read about Here)

I was surprised at how slow Bubblesort is. In all the tests I ran, sorted, unsorted, or random, the Bubblesort algorithm appeared to be the slowest algorithm, which made me question its purpose. Bubblesort works by looping through each element once and swapping the lowest number to the front. It keeps running this loop until everything is sorted. This means that the worst-case runtime is O(n*n), which is rather bad for a sorting algorithm.

Mergesort is an algorithm invented by John von Neumann(one of the greatest scientists). Mergesort works by taking an array and diving it into single elements, then merging these single elements into groups of two and comparing each group and then merging again. It is a rather complicated algorithm to implement, but easy to understand.

O(log(n)) and O(nlog(n)) are the two best runtime algorithms for sorting and searching. O(log(n)) is usually used for binary searches, or searches in a sorted list. This is because we can divide the list in half repeatedly to reduce the amount of steps. An example of O(nlog(n)) runtime is a good sorting algorithm such as Mergesort or Quicksort.

I am anxious about analyzing sorting algorithms because some of them are quite complicated(quicksort, I am looking at you!). If I were given an algorithm for Mergesort and Quicksort, I'm not sure I would be able to tell them apart. I would try to see if there is a pivot, which usually means Quicksort. The upside of sorting and algorithms is that there are many examples all over the internet, especially in pseudocode, which makes it easy to study. I plan to analyze all sorts of sorting efficiencies before the final exam so that I can tell if something is O(log(n)) or O(nlog(n)) just by looking at the code.

Binary Trees

A binary tree is a specialized Tree ADT where there can be at most two children(left and right). The main purpose for this type of Tree is for easy traversal of the nodes to allow for efficient searches by comparing vlues.

For example, let's suppose we have a sorted binary tree with root 1 and children, 5 and 29, who each have more children. We are searching for a specific value x, first we compare x to 29, is x less than or equal to 29? If no, then x must be strictly greater than 29 and must be in one of the children of 29.

This sort of logic is used in Binary Searches, by dividing an array in two parts continuously, we reduce the amount of searches from a linear to a logarithmic amount.

Truthfully, the coding of binary tree structure and binary search algorithms is something I am anxious about. Also, I am not certain of the purpose of pre-order, in-order, and post-order traversals for binary trees. I hope to solve these problems in the near-future, because they appear to be fundamental to understanding linked-lists at a deeper level. Another goal is to gain a better understanding of the wrapper class, and how to modify linked-lists efficiently.

Recursion & Confusion.

Recursive functions

When I first learned about recursion it was explained as follows:

1. A recursive function must call itself.
2. There must be a possible "end" of a recursion, this way the recursion can start working "backwards" and return values.
3. There must be a base case, so that the recursion may end.

This procedure can be demonstrated using a Python function:
return 1 + max([nested_depth(x) for x in L] + [0]) if isinstance(L, list) else 0

The base case is covered if there is no list, the function simply returns 0. The end of the recursion is the last list(the point when the function starts returning values). The recursive call is inside the list comprehension, and it is only called when the Ternary operator evaluates to True.

The simplest form of recursion, I believe, is a nested array: [1, [0,1]]
Suppose I wanted to sum the above array, well once we get to the second element, the type becomes a list, it is also not unreasonable to assume this breaks whatever function we have because we didn't account for a list type.

A simple solution to this problem is to simple check if the element being performed is a list, then we simple call the function again, this way we can think of the procedure being as follows:
Foo([1])
Foo([0, 1])
Now it should be clear how useful recursion is.

Trees & Children

Suppose we have a standard Tree and suppose this Tree has four Children. Let us say the values of the nodes are 1, 5, 7, and 9. There can only be many different configurations with this Tree. One possible configuration is as follows:
1 is a Root, the Children are 5 and 7, and 9 can be the child of either 5 or 7.
1 is a Root, the Child is 5, the Child of 5 is 7, and the Child of 7 is 9.

The idea behind a Tree is recursive! This is because when we want to reach a certain node, we must call recursion continuously until we reach that node, then we can return that node, or work backwards and return all the Parents of that Node.

Trees are an essential part of computer infrastructure, because they are used to store information in an organized and efficient way.

The following Tree in python uses the first element, 5, to associate itself with a data structure. Perhaps the 5 is used by other Trees. Regardless, the idea that we can associates 5 with information is essential to organization.

The following example does not have to make sense, just note the use of the Tree structure. Perhaps 5 is a client ID for a person who works for a bank, or a person who invests in a bank:
[5, ['bank_income', ['5000'], ['growth_rate',[1],[5]] ] ]

Tower of Cheeses

Hanoi Solutions

Recursive solutions are easy to understand, but hard to implement. The reason is because it is easy to create an infinite recursion, or to get confused by nested conditional statements. The solution in Python is to use a list comprehension and perhaps a ternary else. This allows for compact and easily digestible code.

Tower of Hanoi

The solution to a 3-pegged tower of Hanoi is easy for the first n's, but as pegs increase, or as the amount of stackable objects increase, the complexity increases. A recursive solution is ideal for the Tower of Hanoi because the idea of moving a small amount of n objects, isn't much different from moving n+1,n+2,...,n+m objects, this is because the steps are the same for an increasing amount of objects.

Here is how to solve a 3-peg, 3 object Tower: A to C, A to B, C to B, A to C, B to A, B to C, A to B. It follow from an induction proof that n*n - 1 steps is the least possible for a 3-pegged Tower. We can use this idea to create a recursive solution and extend it to 4 pegs, or n pegs.

OOP or ___ec_ o_i_nte_ _r_g___mi__

OOP

Object Oriented Programming refers to a programming paradigm that arose long before I was born, and will persist long after I am gone. The idea is to bundle functionality and data into Classes. Classes are the blueprints which you use to create a unique object that inherits all the functions and values of the class.

A good example is creating a Customer class, which can have attributes(values) such as: Balance, Credit, Orders, History. Also, functions in classes are called methods, which are specific to the class such as: add_balance, remove_credit, view_history. When you create a Customer object, it is said that you instantiate an object, which gives the object all the functionality of the Customer class(Methods, and Attributes). If we have customers Tom and Alison, then they will both have attributes: Balance, Orders, and the methods: add_balance, view_history. This allows Tom and Alison to be Customers, who share enough characteristics that an object oriented approach is justifiable.

Attributes & Methods

Attributes, as explained above, are simply values that are attached to a given object. We have a customer who has $50 balance, $0 credit, these are attributes of the object.

Methods are functions that are useable only by the class. We have a customer who wants to view their history to see their purchasing patterns. The customer simply uses the method view_history and can view the history associated with his object. In addition, the method for view_history would most likely have attributes that consist of a list of his recent transactions. Often methods and attributes are used together, although not always.

Inheritance

Inheritance is the idea of inheriting the methods and attributes of a given class. The idea here is that if you have two extremely similar customers, you wouldn't create another class again.

A good example is a Normal customer class(NCC) and a Business customer class(BCC). The BCC is a similar to NCC, but the BCC would need some unique features, perhaps: tax information, bulk-orders, contract information. In this case, it makes sense to define a new class, but since we want most of the features of the NCC, we inherit from the NCC. Now we create a BCC that has identical methods and attributes of NCC. Now we customize our BCC by creating attributes and methods that will supersede the NCC, or perhaps entirely new methods and attributes.

I like to think of inheritance as a "is-a,but" relationship, therefore a BCC is a NCC, but with extra features. Although, I am not sure what to do in the case where you want a class to inherit only specific features. In this case, perhaps we can define the methods and attributes and use the pass approach as placeholders.

Encapsulation

Encapsulation is the idea of only allowing methods to interact with a object. Certain languages restrict access and modification to an object, while others allow it, and hope the people using the program will understand. I agree with the former approach, it seems logical to disallow random functions to interact with objects, because it can lead to errors and frustration if someone isn't knowledgeable of how the code works. A neat idea is the public, private, and protected approach to objects that certain languages use. Although, I must confess I haven't thought much about encapsulation, which hopefully should change in the new few weeks.

Computer science, joy, and objects.

Computer Science

The first program I ever wrote was hardly anything at all, a function that displayed the sum of two numbers. This was remarkable to me; to realized that I had the ability to create things, instead of being just a bystander.

Joy

The wonderful thing about computer programming is that you can create things that people take for granted, such as: Interfaces, Cellphone apps, Social media websites, databases, and games. All of these tasks are unique and useful in their own way. The ordeal of programming involves failure, hope, frustration, pride, and ingenuity. Also, I believe programming enforces logical behavior, because it is necessary to think logically to make anything non-trivial.

Objects

Object is an ambiguous term, but it is usually implied in English that objects are tangible. This is in stark contrast to what objects represent in object-oriented programming, where an object is an abstraction or an abstract data type(ADT) that serves a purpose.