Hashing : probing methods

Let’s observe different methods to handle collisions in hash tables

When a collision occurs, the colliding element will be placed in the next available block.

Let’s imagine a hash function : h(x) = x mod 6 ;

Let’s take an array arr, with n as null

arr = [ n…

Floyd Warshall algorithm

Let’s take the directed graph ABCD , with 4 edges:

An edge AB with a weight of 5 , an edge BC with a weight of 6 , a weight CD with a weight of 3.

The point of this algorithm will be to create as many matrice as there…

Dynamic programming :

Memoization and tabulation

Let’s observe present both methods by exposing each to the same problem : how to find a specific fibonacci number?

Memoization

First, let’s use recursion to solve this matter.

Ex :

For each iteration

Function fib( ){

Ex : fib 4
===> Find the two previous toms.

Fib 3 fib 2

Topological sort :

Sorting nodes of a graph

First , in order to perform this function properly, you need to understand that graphs should be directed and acyclic.

Determine the "in degree of each vertex".

There shouldnt be any cycle inside the graph.

First, we need to define the key concept of this algorithm : indegree.

The indegree of a node represents the number of parent nodes.

Quick sort

Quicksort ls a powerful sorting algorithm

Here is how it works :

Select arbitrarily a pivot X from an array

Insert on the right of X, any serie of element being smaller than it (keeping the same order, as the original array). On the left, perform the same operation with bigger elements.

Ex :

X = 4

Arr = [ 2 1 3 6 5 4 ];

NewArr =[ 2 1 3 4 6 5]

Now, consider the obtention of such an array :

B= bigger elements array
Y = smaller elements array

[B, X , Y];

Perform recursively the same operation on both arrays , which will finally return such an array :

[sortedX , pivot , sortedY];

Depth first search

Depth first search is a search algorithm , allowing to traverse trees or graphs.

The name of this algorithm is pretty descriptive.

Indeed, the point there will be to make each node traverse the entirety of a subtree, after being visited.

Lets imagine a tree with a root A …

Prims algorithm

Prim’s is a minimum spanning tree algorithm

Here are the steps to proceed :

First, remove all “looping edge", which means edge starting from a node, to arrive to the same node.

Then, remove parallel edges (edges having common origin, and common destinations).

Select any arbitrary vertex as a source.

1)Select the minimum adjacent edge from the…

Selection sort

Slow algorithm. Indeed, important to notice that this algorithm has a worst time complexity as n^2, and that many other algorithms could be recommended to reach the desired goal (ex : quicksort…)

Here is how this algorithm works.

For a given array [7,2,8,5] ;

For an index i = 0;

Kruskal algorithm

Kruskal algorithm is a minimum spanning tree algorithm.

Here is how the algorithm works :

Let’s recall that a graph is made of 2 components : edges and nodes.

First, right down a list of all the different edges of a given graph.

Then, consider that all the nodes have…

Dijskstra

Dijsktra is a single source shortest path algorithm.

Here are basically how to perform this algorithm :

Dijskstra algorithm follows a greedy method (following a step by step procedure, to arrive to an optimal solution).

It works on directed, and undirected graphs.

It uses the same relaxation method as bellman Ford

(if vA + wAB < vB){

vB = vA +wAB

vA parent of vB

}

We first relax the adjacent nodes to the source. All the other vertexes are set to. “+infinity".

Then, start by choosing the smallest unvisited vertex value. Relax (if possible) all the adjacent nodes.

Repeat the step : visit the smallest unvisited vertex value, and perform, if possible, relaxation to adjacent edges.

When there are no unvisited vertexes anymore, the execution of the algorithm is done. 