# Algorithms League

## A small and fun competition between the algorithms of different tasks.

This will be a fun blog on how the best algorithms work and how to implement them in pseudo-code and a few details on them.

So 1,2,3 go….

Rules and steps in the competition:-

• There will be 3 rounds
• Every algorithm will be judged on time complexity and space complexity
• Every reader will be given a token of certification for participation
• The first round will be of Sorting algorithm
• The second round will be of the tree traversal algorithm
• The third round will be a bonus round with no winners or losers only players on my favorite activation functions

First round:-

We need sorting techniques mostly every day for data cleaning and for reading data and sometimes processing and sorting huge messy datasets.

Our nominees are Quicksort, odd-even sort, and the Cocktail sort I know they are not common.

Quicksort:-

Quicksort is an efficient sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.

odd-even sort:-

In computing, an odd-even sort or odd-even transposition sort is a relatively simple sorting algorithm, developed originally for use on parallel processors with local interconnections. It is a comparison sort related to bubble sort, with which it shares many characteristics.

Cocktail sort:-

Cocktail shaker sort, also known as bidirectional bubble sort, cocktail sort, shaker sort, ripple sort, shuffle sort, or shuttle sort, is an extension of bubble sort. The algorithm extends the bubble sort by operating in two directions.

code in python at:-

Pseudo-codes

`function quicksort(A, lo, hi) is    if lo < hi then        p := partition(A, lo, hi)        quicksort(A, lo, p - 1)        quicksort(A, p + 1, hi)function partition(A, lo, hi) is    pivot := A[hi]    i := lo    for j := lo to hi do        if A[j] < pivot then            swap A[i] with A[j]            i := i + 1    swap A[i] with A[hi]    return ifunction A = cocktailShakerSort(A)#`beginIdx` and `endIdx` marks the first and last index to checkbeginIdx = 1;endIdx = length(A) - 1;while beginIdx <= endIdx    newBeginIdx = endIdx;    newEndIdx = beginIdx;    for ii = beginIdx:endIdx        if A(ii) > A(ii + 1)            [A(ii+1), A(ii)] = deal(A(ii), A(ii+1));            newEndIdx = ii;        end    end    #decreases `endIdx` because the elements after `newEndIdx` are in correct order    endIdx = newEndIdx - 1;    for ii = endIdx:-1:beginIdx        if A(ii) > A(ii + 1)            [A(ii+1), A(ii)] = deal(A(ii), A(ii+1));            newBeginIdx = ii;        end    end    #increases `beginIdx` because the elements before `newBeginIdx` are in correct order    beginIdx = newBeginIdx + 1;endendfunction oddEvenSort(list) {  function swap(list, i, j) {    var temp = list[i];    list[i] = list[j];    list[j] = temp;  }  var sorted = false;  while (!sorted) {    sorted = true;    for (var i = 1; i < list.length - 1; i += 2) {      if (list[i] > list[i + 1]) {        swap(list, i, i + 1);        sorted = false;      }    }    for (var i = 0; i < list.length - 1; i += 2) {      if (list[i] > list[i + 1]) {        swap(list, i, i + 1);        sorted = false;      }    }  }}`

Quicksort has O(log n) time complexity and O(n) space complexity.

Odd-Even sort has O(n²) time complexity and O(1) space complexity.

Cocktail sort has O(n²) and O(1) space complexity.

so time for evaluation:-

The winner of the time complexity category for sorting is Quicksort.

The winner of the space complexity category for sorting is the cocktail sort.

Second round:-

Tree traversal is a very important part of any binary tree it helps us to traverse or sort a binary tree. Traversal is a process to visit all the nodes of a tree and may print their values too. Because all nodes are connected via edges we always start from the root node. That is, we cannot randomly access a node in a tree.

The nominees are Inorder, Preorder, and postorder

In-order:-

n this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself.

If a binary tree is traversed in-order, the output will produce sorted key values in ascending order.

We start from A, and following in-order traversal, we move to its left subtree B. B is also traversed in-order. The process goes on until all the nodes are visited. The output of inorder traversal of this tree will be −

D → B → E → A → F → C → G

Pre-order:-

in this traversal method, the root node is visited first, then the left subtree, and finally the right subtree.

We start from A, and following pre-order traversal, we first visit A itself and then move to its left subtree B. B is also traversed pre-order. The process goes on until all the nodes are visited. The output of pre-order traversal of this tree will be −

A → B → D → E → C → F → G

Post-order:-

# Post-order Traversal

In this traversal method, the root node is visited last, hence the name. First, we traverse the left subtree, then the right subtree, and finally the root node.

We start from A, and following Post-order traversal, we first visit the left subtree B. B is also traversed post-order. The process goes on until all the nodes are visited. The output of post-order traversal of this tree will be −

D → E → B → F → G → C → A

Level-order:-

Level order traversal of a tree is breadth-first traversal for the tree.

Level order traversal of the above tree is 1 2 3 4 5

`Algorithm Inorder(tree)   1. Traverse the left subtree, i.e., call Inorder(left-subtree)   2. Visit the root.   3. Traverse the right subtree, i.e., call Inorder(right-subtree)Algorithm Preorder(tree)   1. Visit the root.   2. Traverse the left subtree, i.e., call Preorder(left-subtree)   3. Traverse the right subtree, i.e., call Preorder(right-subtree)Algorithm Postorder(tree)   1. Traverse the left subtree, i.e., call Postorder(left-subtree)   2. Traverse the right subtree, i.e., call Postorder(right-subtree)   3. Visit the root.Algorithm Levelorder(tree)for d = 1 to height(tree)   printGivenLevel(tree, d);function printGivenLevel(tree, level)if tree is NULL then return;if level is 1, then    print(tree->data);else if level greater than 1, then    printGivenLevel(tree->left, level-1);    printGivenLevel(tree->right, level-1);`

And now the winner is Inorder Tree traversal because it is the fastest of all of them.

Third round:-

Activation functions are the most integral and essential part of every neural network from a simple apple or banana to complex classification and climate prediction to a small device you carry with yourself and cit and chat with it.

Our nominees ReLU, Sigmoid, Softmax, and TanH.

ReLU:-

The rectified linear activation function or ReLU for short is a piecewise linear function that will output the input directly if it is positive, otherwise, it will output zero. It has become the default activation function for many types of neural networks because a model that uses it is easier to train and often achieves better performance.

Sigmoid:-

A sigmoid function is a mathematical function having a characteristic “S”-shaped curve or sigmoid curve. A common example of a sigmoid function is the logistic function shown in the first figure and defined by the formula.

Softmax:-

TanH:-

In mathematics, hyperbolic functions are analogs of the ordinary trigonometric functions defined for the hyperbola rather than on the circle: just as the points form a circle with a unit radius, the points form the right half of the equilateral hyperbola.

function:-

SinH(x) = 1/2*(e^x-e^-x)

CosH(x) = 1/2*(e^x+e^-x)

TanH(x)=SinH(x)/CosH(x)

Python code at:-

But I am sorry I have not written code for TanH in python so I will add the code in this blog only.

Pseudo-codes

`function sigmoid xreturn 1/1+e^xfunction softmax xy = []for i in range n(x)eq = x[i]/sum(x)insert eq into yreturn ysub-function sum xtmp = 0for i in xtmp+=ireturn tmpfunction ReLU xif x > 0:return xelse:return 0function TanH xy = (1/2*(e^x-e^-x))/(1/2*(e^x+e^-x))`

TanH function code in python:-

`import numpy as npdef f(x):    y = (1/2*(np.exp(x)-np.exp(-x))/(1/2*(np.exp(x)+np.exp(-x))    return y`

Stay safe during this Covid-19 pandemic situation. Thank you again or reading, stay tuned, and keep reading.

Happy blogging.

Want to get more blogs and newsletters from me subscribe

Divyosmi Goswami: A digital nomad's journal wandering through the physical and cyber city discovering himself.

## More from Divyosmi Goswami

Divyosmi Goswami: A digital nomad's journal wandering through the physical and cyber city discovering himself.