Algorithms League

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

Dear reader,

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

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 i
function A = cocktailShakerSort(A)
#`beginIdx` and `endIdx` marks the first and last index to check
beginIdx = 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;
end
end
function 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.

Image for post
The binary tree for In-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.

Image for post
Image for post
The binary tree for Pre-order

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.

Image for post
Image for post
The binary tree for Post-order

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.

Image for post
Image for post
Level order traversal of a binary 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.

Image for post
Image for post
ReLU Visualization and function

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.

Image for post
Image for post
Sigmoid function and visualization

Softmax:-

Image for post
Image for post
Softmax visualization
Image for post
Image for post
Softmax function

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.

Image for post
Image for post
TanH visualization

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 x
return 1/1+e^x
function softmax x
y = []
for i in range n(x)
eq = x[i]/sum(x)
insert eq into y
return y
sub-function sum x
tmp = 0
for i in x
tmp+=i
return tmp
function ReLU x
if x > 0:
return x
else:
return 0
function TanH x
y = (1/2*(e^x-e^-x))/(1/2*(e^x+e^-x))

TanH function code in python:-

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

Thank you for reading:-

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

Written by

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

Get the Medium app