Selection , quick and merge sorts.

• Selection Sort

Lets think about selection sort as two lists a sorted one and unsorted one. We will first start by comparing the first two numbers. In each step, find the smallest number in the unsorted part of the list, swap it with the first number in the sorted list until the whole list is sorted (n times). 

• Quick Sort

Quick sort is a recursive sorting algorithm in which we select an element in the list as a pivot and partition the list into two sublists around it ; one that contains values smaller than the pivot and one with values larger than the pivot. As we go we apply quick sort on our sublists.The performance of this algorithm depends entirely on selecting a good pivot. 

• Merge Sort

Instead of splitting the list into sublists around a pivot, merge sort splits the list into two halves , most likely equal, and recursively sorts them using merge sort. Finally, they are recombined by repeatedly take the smallest element among the two lists.

Sorting algorithms efficiencies

So I just had my tutorial today. It was pretty simple although recording the information in the spreadsheet took a lot of time but there are important points that we should benefit from :

• The List sort is the best in all cases (random, sorted and sorted reversed ) then comes the quick sort with both it's algorithms.
• When our data is sorted , bubble sort and insertion sort benefited the most from that.
• When our data is sorted reversed bubble sort was the most affected (i.e took more time ) since a swap will occur every time since numbers are in descending order and swapping takes time.

Deletion from binary search trees

We have three cases when deleting a node from a binary search tree:

• ·      If we are trying to delete a leaf , its simple we just remove it from the tree and the property of the BST is not violated.
• ·      If we are trying to delete a node that has one subtree, we connect its parent directly to its only subtree. In the following example we are trying to delete 3 and it has only one subtree:

•      The last case is when we have two subtrees; we follow this technique we leave the node that we want to delete and rather remove its value and search for another value that can be replaced their (without violating the BST property of course ) and then we delete the node that had the new value. For example:

       If we wish to delete the 6 in the following tree --------> we delete its value but keep       the actual node.

So the hint to finding the new value is one of two options its either the largest value in the left subtree or the smallest in the right subtree. Below is an illustration of how we replaced the value 3 and deleted the actual node.  

        

Binary Trees and Binary Search Trees

A tree is a data structure that consists of nodes and connections between them.
Properties:
* Each node has exactly one parent.
* There is a path from the root to every node.
* There are no paths in the tree that form loops .

Important terms:
Height of a tree : The length of the longest path between the root and a leaf.
Depth of a node : The length of the path from the root to the node.

A binary tree is a special kind of tree with a branching factor of 2. Lets apply what we learned in recursion to recursively define a binary tree:

A binary tree is :

• either empty or

• has a node with value k (root ) with a Binary Tree as its left child and a Binary Tree as its right child.

A binary search tree however is a special kind of binary tree with all nodes in our left subtree that have values less than the value k and all the nodes in our right subtree that have values more than the value k.

As shown above we can also define a binary search tree recursively simply by adding the property we just mentioned.

There are three important operations that we are concerned about it in binary search trees :

1. Searching for a certain value. 
2. Insertion.
3. Deletion.

Searching is relatively straight forward, where we compare the target's value to the root value and decide which subtree to recurse on.

Insertion however requires us to maintain the Binary Search Tree property after inserting the new value (i.e.insert the node where you would expect it to be if you did a binary search for its value).

Therefore insertion requires searching !!

Finally deletion,, uhmm deletion has a lot of cases and I would like to represent examples of these cases in another post to keep this post brief and clear.

With all these midterms going on and assignments here and there , thought you could have time for some computer science jokes. 

And a small advice maybe ?

Linked Lists and their efficiency

Aren't Python lists just based on arrays that consist of contiguous chunks of memory? But what if they didn't have to be contiguous ? What if we just want to add new elements into the memory without having to change the location of others ?

Now we can introduce a new data structure called Linked Lists which is simply a chain of connected nodes where each node contains a data field and a next field which points to the next node in the list. How do we reach to the end of the list ? We traverse the list by following each node's next pointer until we reach the end of our linked list. In most cases we have access to the first node which is called the head.

Adding and removing from Linked Lists
Adding a node replaces the last node reference to the new node that's being added and makes our old last node point to the new node as the next node in the list.
Deleting a node is a process that iterates the list looking for the node and and we look around the deleted node to make sure that the previous node now points to the following node as its next node.

Linked list efficiency:
Most operations that we apply to either end of our linked list do not depend on the size of the list but only one operation does which is removing from the end of the list .
Why ?!
Because removing from the end of the list requires a full traversal since we can't obtain our new tail just from tail.

Difference between abstraction and encapsulation

After introducing the concept of Object Oriented Programming and its main parts, lets compare and contrast abstraction and encapsulation :

Abstraction :

• Solves our problem using an outer shell in terms of  "design"
• Its used to hide the unwanted and un relevant data from the user.
• Focuses more on what the object actually does rather on how it does it.
• Example : The display of a touch screen.

Encapsulation:

• Solves our problem in the implementation level instead.
• It is used to hide the code and data into one single unit and hide it from the external world.
• Focuses on hiding the internal details and mechanics of an object, i.e. how the object does it.
• Example : How the display screen is connected with dialling option using circuits.

Object Oriented Programming

Usually , for us computer scientists programs are organized around the idea of action and logic but Object Oriented Programming is a programming model that organizes them around objects and data.
How is that possible ?
Well , OOP allows decomposition of a problem into a number of entities called Object and then builds data and function around these objects and these objects can only be accessed by the functions associated with it. A class however is a blueprint for an object that contains variables for storing data and functions to performing operations on these data.
There are three main concepts to the understanding of the concept of object oriented programming :
1) Encapsulation
2) Abstraction
3) Inheritance
We will explain briefly each concept putting in mind that all languages that support OOP will support these three concepts.
 Encapsulation:

Wrapping up data member and method together into a single unit (e.g..class)  is called Encapsulation.

Encapsulation is like enclosing in a capsule. That is enclosing the related operations and data related to an object into that object. Encapsulation is hiding internal details of the object i.e it doesn't care how the object does something as long as it does it !!

Abstraction:

Abstraction lets you focus on what the object does instead of how it does it. It is the process of hiding the working style of an object, and showing the information of an object in an understandable manner.

Inheritance:

Inheritance is the process of reusing objects and its methods. Its how classes can acquire property from other "parent" classes.

Summary 

Unlike Structured Programming Languages, in which programs are designed with collections of functions that are called in different parts of the program, more like a script or job list , OOP programs are designed with the concept of objects, where each object contains its own set of variables and functions.