10 Most Important Algorithms You Must Know

What Is Algorithm

Algorithms are a set of instructions for a computer to perform a specific task. They are written in a language that the computer can understand, and they tell the computer what to do and how to do it.
Today we understand best 10 algorithms in this post.

Algorithms are one of the most important inventions of the 20th century. They are programs that tell a computer what to do, and they can be used to solve any type of problem. For example, algorithms for chess can help computers play chess better than humans. Algorithms for Netflix can help find movies that you might like based on what you have watched in the past. Algorithms for Google can help search engines return more relevant results in response to your queries.

Algorithms are the backbone of every machine learning model. In this article, we will talk about the best algorithms you need to know to build a robust machine learning model.

The algorithms we will discuss are:

1. Binary Search Algorithm
2. QuickSort Algorithm
3. Euclid's Algorithm
4. Lee Algorithm
5. Kruskal's Algorithm
6. Union Find Algorithm
7. Flood Fill Algorithm
8. Bellmam Ford Algorithm
9. KMP Algorithm
10. Topological Sort Algorithm

Binary Search Algorithm

Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is the index of the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to search

    Step 1: set beg = lower_bound, end = upper_bound, pos = - 1  

    Step 2: repeat steps 3 and 4 while beg <=end  

    Step 3: set mid = (beg + end)/2  

    Step 4: if a[mid] = val  

    set pos = mid  

    print pos  

    go to step 6  

    else if a[mid] > val  

    set end = mid - 1  

    else  

    set beg = mid + 1  

    [end of if]  

    [end of loop]  

    Step 5: if pos = -1  

    print "value is not present in the array"  

    [end of if]  

    Step 6: exit  

QuickSort Algorithm

Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value. Quicksort is an in-place sorting algorithm.

    Step 1: Consider the first element of the list as pivot

            (i.e., element at first position in the list).

    Step 2: Define two variables i and j. Set i and j to first and last elements of

            the list respectively.      

    Step 3: Increment i until list[i] > pivot then stop.

    Step 4: Decrement j until list[j] < pivot then stop.

    Step 5: If i < j then exchange list[i] and list[j].

    Step 6: Repeat steps 3,4 & 5 until i > j.

    Step 7: Exchange the pivot element with list[j] element.

    Step 8: exit

 Euclid's Algorithm

The Euclidean Algorithm for finding GCD(A,B) is as follows:

    Step 1: If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop.

    Step 2: If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop.  

    Step 3: Write A in quotient remainder form (A = B⋅Q + R)

    Step 4: Find GCD(B,R) using the Euclidean Algorithm since GCD(A,B) = GCD(B,R)  

    Step 5: exit

Lee Algorithm

The Euclidean Algorithm for finding GCD(A,B) is as follows:

    Step 1: Create an empty queue to store the coordinates of the matrix and

            initialize it with the source cell having a distance of 0 from the source,

            marking it as visited.

    Step 2: Starting from the source cell, call the BFS procedure.

    Step 3: Initialize a boolean array of the same size as input matrix and all

            values set to false. This is used to store the visited status of

            a coordinate.

    Step 4: Run a loop till the queue is empty

    ​        Dequeue front cell from the queue

            Return if the destination cell is reached

            Otherwise, For each of the four adjacent cells of a current cell,

            if the cell value is 1 and they are un-visited, enqueue the cells and

            mark them as visited.

    Step 5: If all queue elements are processed and destination is not reached,

            return false.

    Step 6: exit

Kruskal's Algorithm

    Step 1: Sort all edges in increasing order of their edge weights.

    Step 2: Pick the smallest edge.  

    Step 3: Check if the new edge creates a cycle or loop in a spanning tree.

    Step 4: If it doesn’t form the cycle, then include that edge in MST. Otherwise,

            discard it.    

    Step 5: Repeat from step 2 until it includes |V| - 1 edges in MST.

    Step 6: exit

Union Find Algorithm

    Step 1: We need to develop a constructor first giving an input N. N is the size

            of the data as I mentioned earlier. I  am putting the name of

            the constructor as QuickFind. In this constructor first we will generate

            an array of range N. Each element is an id that is the same as the element

            position starting from 0. Such as id of position 1 is 1, id of position 0

            is 0, id of position 7 is 7.  

    Step 2: Develop a class ‘connect’ that takes two inputs p and q. It returns a

            Boolean that indicates if they are already    connected. If this class returns

            yes, then the algorithm doesn’t do anything. But if it returns no, then

            the algorithm implements the union operation that connects p and q.  

    Step 3: Develop a class named ‘union’ that connects p and q. Iterate through the

            array id. Where you find the id of p, change it to id of q.        

    Step 4: exit

Flood Fill Algorithm

    Step 1: Take the position of the starting point.

    Step 2: Decide wether you want to go in 4 directions (N, S, W, E) or

            8 directions (N, S, W, E, NW, NE, SW, SE).        

    Step 3: Choose a replacement color and a target color.

    Step 4: Travel in those directions.

    Step 5: If the tile you land on is a target, reaplce it with the chosen color.  

    Step 6: Repeat 4 and 5 until you’ve been everywhere within the boundaries.

    Step 7: exit

Bellmam Ford Algorithm

    Step 1: In this step, we would declare an array of size V(Number of vertexes)

            say dis[] and initialize with all of its indexes with a very big Value

            (preferably INT_MAX) except src which will be initialized with value 0.

            We are doing this because initially we assume that it takes infinite time

            to reach any of the vertices from our source vertex and we are initializing

            dis[src]=0 because we are already on source vertex.

    Step 2: In this step, the shortest distance is calculated. For it, we would do the

            underlying step V-1 times. For every edge u→v make dis[v]=min(dis[u]+

            wt of edge u→v, dis[v]) It means whenever we are on any vertex u we will

            check if we can reach any of its neighbors in less time it is currently

            possible to visit, we will update the dis[v] to dis[u]+wt of edge u→v.

    Step 3: In this step, we will check if there exists a negative edge weight cycle

            traversing each and every edge u→v and checking if there exists

            dis[u] + wt of edge u→v < dis[v] then our graph contains a negative edge

            weight cycle because traversing the edges again and again is beneficial

            as it is lowering the cost to traverse the graph.

    Step 4: exit

KMP Algorithm

    Step 1: In the string, you can see there’s a mismatch at ‘d’ and before character

            ‘d’ all character are matched.

    Step 2: When the mismatched character is found the KMP Algorithm – data searches

            for substring before the mismatched character.

    Step 3: We can see “acbac” matches with the given text as since they have matched

            then only we have reached the mismatched character ‘d’.

    Step 4: Again, since ‘ac’ from the substring matches with the ‘ac’ from the given

            string so we can directly skip two characters and move to the next

            character which is ‘b’.

    Step 5: Now we will compare ‘b’ and ‘x’, they don’t match. Again find out the

            longest common substring from the substring before the mismatched character,

            which is common to both suffix and prefix. Here, there is no common between

            suffix and prefix so we can say ‘previously chosen ‘a’ is not the correct

            starting position.

    Step 6: Therefore we will choose the next character after ‘x’ which is ‘a’ at index

            6 as the starting position. Compare ‘a’ with’a’ , it matches and now

            increments the position.

    Step 7: Now compare ‘c’ with ‘b’, it does not match.

    Step 8: By the rule find substring before unmatched character and find the longest

            common substring which is common to both suffix and prefix. There is no

            common such substring.

    Step 9: In this way how the KMP Algorithm – data works. Finally, we will get the

            matching substring.

    Step 10: exit

Topological Sort Algorithm

    Step 1: Find a vertex that has indegree = 0 (no incoming edges)

    Step 2: Remove all the edges from that vertex that go outward

            (make its outdegree = 0, remove outgoing edges)a

    Step 3: Add that vertex to the array representing topological sorting of the graph.

    Step 4: Repeat till there are no more vertices left.

    Step 5: exit

This article is contributed by Vk Malani If you like W3 Coding club and would like to contribute, you can also write an article and mail on w3codingclub@gmail.com. See your article appearing on the W3 Coding Club main page.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.