Some algorithms used in daily life.
Interesting algorithms have a look 👇 #develevate
26 November, 2022
11
11
3
Contributors
These are some of the algorithms that are used in daily life. Have you ever wondered, how shortest routes are calculated in maps, sorry, you guessed it, yeah, its Dijkstra’s algorithm, but I am sure you don’t know the next algorithm(s). So, lets introduce you some common algorithms, that you should know. These algorithms may sound interesting to you.
1. Bucket Sort:- Have you ever sorted papers, in schools according to the alphabetical order(during exams may be). You don’t but you have used bucket sort. How look at the animation here:
Bucket Sort
For more simple visualisation: https://www.youtube.com/watch?v=VuXbEb5ywrU
So, lets look at the algorithm what itsays:
Prerequisites: Lets take a unsorted array:
arr = [ 12, 34, 10, 45, 87, 34, 22, 2,42, 45, 89, 34] and, linked list of size of the array, here its 12.
Step 1:
Traverse through the array. Take each element and apply, value=(length_of_array + arr[i])/max(arr)+1. This value will give you the index of the linked list, where to store the particular arr[i] in the linked list.
Step 2:
If the value of "value" is matching with some other "value", then the next node pointer("*node") will point to the current "value" ’s address. This will create a linked list top of it. Like in the above animation see at 8th index.
Step 3:
If step 2 occurs, then sort them using insertion sort, which has time complexity of O(n2). After being sorted, move to the following step.
Step 4:
Move the head node pointer(*head) of the first linked list to first index of the linkedlist, and second to the second until, "*node = NULL". Similarly, Move to the next linked list and start
from where you left off. Finally, you have sorted the array, with
time complexity, O(n2) and space complexity, O(n+k).
Refer to the following pseudocode from javatpoint:
Bucket Sort(A[])
Let B[0....n-1] be a new array
n=length[A]
for i=0 to n-1
make B[i] an empty list
for i=1 to n
do insert A[i] into list B[(n* a[i])/max(a)+1] ·
for i=0 to n-1
do sort list B[i] with insertion-sort
Concatenate lists B[0], B[1],........, B[n-1] together in order
End
2. Luhn’s Algorithm: Do you know how to check you credit card is valid or not? Yeah it’s a new algorithm, but its done by this.
Lets take this American express Test Card no. from Paypal’s website "371449635398431".
So, how to know whether, its valid card or not.
Step 1:
Multiply every other digit by 2, starting with the number’s second-to-last digit, and then add those products’ digits together.
In this case,
3 7 1 4 4 9 6 3 5 3 9 8 4 3 1
Starting from 3( red bold marked) to 7( marked as bold) all the digits are multiplied by 2, and added together. Then,
2*3 + 2*8 + 2*3 + 2*3 + 2*9 + 2*4+ 2* 7
6+ 16 + 6+ 6+ 18+ 8+ 14,
So, now adding each separating and adding each digit,
6+ 1+ 6+ 6+ 6+ 1+ 8+ 8+ 1+ 4 = 47.
This is the result. Move to Step 2
Step 2:
Add the sum to the sum of the digits that weren’t multiplied by 2.
3 7 1 4 4 9 6 3 5 3 9 8 4 3 1
Adding all these digits we, get (3+1+4+6+5+9+4+1) which equals to 33.
Then adding it to the previous result we get
Step 3:
If the total is divisible by 10, then number is valid!
So, 47 + 33 = 80, which is divisible by 10, so credit card no. is valid.
3. Dijkstra’s Algorithm and A * search:-
Have you ever traced or searched on maps for your destination, you might have seen a route for that, in naĂŻve case, A* search is used, because Dijkstra takes more time than it. Each point on the map corresponds to a vertex of a graph and traffic and distances corresponds to edges and weight of it. And to perform both of these algorithms, we take a priority queue sorted by sum of weights or sum of weights and distance remaining. So, in Dijkstra, almost(if sum are smaller than the latter then moved to next vertex) each
vertex is traced to get the ultimate goal. Each vertex is traced from start and sum of the weights is calculated and sorted in ascending order and written to priority queue. Then, doing it recursively, we found the destination, but it traverses through almost all nodes, whenever the queue elements are longer then the path is terminated, so it takes more time. For this reason, we have a extension of Dijkstra, A* search, where sum is equal to weights of the edges and remaining paths. So, here the longest paths are eliminated first, results are quicker. The problem is resolved as the longer distance remaining are eliminated. You can learn more about these online.
4. Image Filter( Box Blur, Sobel’s Operator):-
i. Box Blur:- Ever wondered how image is blurred, its done by some algorithms such as Box Blur, Gaussian Blur etc. Lets discuss the simplest one, box blur.
So, an image or picture is divided into lots of pixels, and each pixel contains some values of Red, Green and Blue in RGB colour system, and each colour(Red, Green and Blue) contains 0 to 255, where 0 has absence of that particular colour and 255, presence of that.
Box Blur
So, how box blur works is that, each pixel contains its surrounding pixel as its obvious. So, in the above representation, we have different pixels represented as a box, and each box has its own RGB value. Lets, take the pixel b, and lets assume, it has red value b, green value b, blue value b. So, afterapplying box blur the RGB(b), the value becomes "( a1+a2+a3+a4+a5+a6+a7+a8)/number of surrounding pixels(8)".
So, its basically replacing the average of surroundingpixels, similarly for corners(a1), "(a2+b+a4)/3" and for edges(a2), "(a1+a3+a4+b+a5)/5".The averaging all the pixels and replacing the rgb value by that, will give usa blur image as integrated. Lets look onto another algorithm below.
ii. Sobel’s Operator:-
Have you seen images like this:
edges
In the right side of you can see the edges or boundaries of an image. How its done, its
simple;
Here, you can see two matrices Gx and Gy. So, as we calculated box blur we have do the same take each pixel and map into these matrices and calculate their r, g, b values respectively. Do, it for both Gx and Gy, and then do , after that you willfind the new RGB value. After calculation, if the value is above 255 or below 0, then make it to 255 and 0
respectively. The below is the convolutional Matrix:
convolutional Matrix
Lets take an example below:
example
Here, Gx of b is calculated as: -
1 * a1 + 0* a4 + 1 * a6 + -1 * a2 + 0 * b + 1* a6 + -1 * a3
+ 0 * a5 + 1* a8 +-2 * a1 + 0* a4 + 2 * a6 + -2 * a2 + 0 * b + 2* a6 + -2 * a3
+ 0 * a5 + 2* a8 + -1 * a1 + 0* a4 + 1 * a6 + -1 * a2 + 0 * b + 1* a6 + -1 * a3
+ 0 * a5 + 1* a8 and,
Gy as:- -1 * a1 + -2*
a4 + -1 * a6 + -1 * a2 + -2 * b + -1* a6 + -1 * a3 + -2* a5 + -1* a8 + 0 * a1 +
0 * a4 + 0 * a6 + 0 * a2 + 0 * b + 0 * a6 + 0 * a3 + 0 * a5 + 0 * a8 + 1 * a1 +
2 * a4 + 1 * a6 + 1 * a2 + 2 * b + 1 * a6 + 1 * a3 + 2 * a5 + 1 * a8
Then both are squared and added and squareroot is the answer, taking constraints in mind.
This is how you can calculate edges of all pixels i.e. as a image integrated, for edges and corners its done how blur was done before.
This are some of the algorithms hope you will like it.
Note:- I wanted to mention KMP algortithm, but its more complex
to mention here, so I have put a link for some resources.
KMP(Knuth Morris Prath) Algorithm:- So, how pattern matching works, Lets take an
example in real life, dna sequencing where each common pattern of A, C, T, G
are repeated like in this STR, “AAGGTAAGTTTAGAATATAAAAGGTGAGTTAAATAGAATAGGTTAAAATTAAAGGAGATCAGATCAGATCAGATCTATCTATCTATCTATCTATC”,
"TATC" is repeated. So, it’s a method to find the match. If you have ever search for a substring you might have backtracked backwards the original string, but in KMP Algorithm, you don’t have to do that. We have a lps array based on which we only backtrack the substring based on the index. As I mentioned earlier this is little complex to explain here. So, I have put resources to learn about it from here Youtube and an animation.
Huge credits goes to cs50x, it contains awesome problem sets, best problem sets ever seen in my life. Some internet guides, lots of research and efforts went through while making this blog.
Thanks, hope you will enjoy :)
#develevate #toolstipstricks
develevate
toolstipstricks