One of the main reasons why i love computer science or programming is problem solving, back to school i used to memorise everything that come within my eye sight which translated in bad grades because learning or knowledge is not a standalone process it dependent process and if you're going to memorise these prerequisite you will eventually forget them and will suffer in a more advanced levels due to lack of knowledge.
this changed in college when i got to my first computer science class and started to grasp the ideas of deduction and understanding and experimenting for example you don't have to memorise the proof just fully understand it and deduce it based on your understanding.
without going into further details this post contain list for some of my favourite Algorithms this list by no mean is Exhaustive or intended for a certain learning pattern it's just for sharing my own thoughts
Sieve of Eratosthenes:-
this Algorithm was developed by a greek mathematician.
Explanation
it's used to find the number of prime numbers for a given a range (N) between 2 and (N) with a complexity of O(Log(n)N) normally to find prime numbers within a range will requires a complexity of O(N*2)
so how this Algorithm works is that you loop over the Range Log(N) which is the first loop then in the second you will over the N the idea here is mark all non-prime numbers to true then check for false value and count them to be prime.
to do so we can get the range of number which divides i then set it to true.
let take 3 for example when i is 3 then j will be 9, 12, 15,18,etc..
do you see the pattern it will set every multiple of 3 to true so this is the general idea of the Algorithm turning every multiple of i to true(non-prime) because if a number if multiple of a number it means it can be divides by it and prime number only is divisible by itself and 1
Note :- There's a developed version of this Algorithm with a complexity of O(N) feel free to check it
** :power sign
Code :-
func Calculate_prime(n int)int {
var count int
var i,j int
var arr[1000000] bool
var number float64
number = float64(n)
number = math.Sqrt(number)
number1 := int(number)
if(n > 1000000){
fmt.Println("The Number has to be less than 1000000")
return -1;
}
for i = 2; i < number1 ; i++ {
for j = i * i; j < n; j = i + j {
arr[j] = true
}
}
for i = 0; i < n ; i++ {
if(!arr[i]){
count++
}
}
return count
}
Counting Sort
Despite this Algorithm is not widely because of it's not good complexity but the idea behind this Algorithm is both Simple and beautiful i don't know but i find it a beautiful algorithm.
Counting Sort was invented by Harold H. Seward, it's complexity is O(n+m).
Explanation
Counting Sort from it's name is a sorting algorithm, the main idea behind this Algorithm is to count the number of occurrence of a number and put every number in an array with an index similar to it's value.
so if we have an array looks like this {7,5} then the first array which map every number to an index with same value will look like this
Numbers = {0,0,0,0,1,0,1,0} if the array is {7,5,5} then it will look like this
Numbers = {0,0,0,0,2,0,1,0} where the number 2 is the occurrences of 5 in the array Numbers
Code :-
func sort(Array[1000000]int)[] int{
var indices[1000000]int
max := Array[0]
var i,j int
for i=0; i < 1000000; i++ {
if(max < Array[i]){
max = Array[i]
}
}
new_Array := Array[0:max]
for i =0 ; i < max; i++ {
if(new_Array[i] != 0){
indices[new_Array[i]]++
}
}
for i=0; i <= max; i++ {
for x := indices[i]; x > 0; x-- {
new_Array[j] = i;
indices[i]--
j++
}
}
return new_Array
}
Explanation
1) find the maximum number in the array and assign the size of array to it + 1
2) loop over the maximum number and position every element according to it's value
3) loop over the array where elements sorted based on the position
4) loop over the number of occurrences of element till it's zero
5) Elements is sorted in new_Array
Naive Pattern Searching
This Algorithm is used for searching a certain character or string or to put is simply a substring in a string.
let's say we are looking for the word "Algorithms" in sentence "I Love Algorithms"
Explanation
we are going to map every Characters to check if it does exists or not
for Example when the Algorithm start it will compare I with A then it will break but it will shift to the next index so it scans every index, if the index doesn't match it will break from the loop, the reason for loop condition to be text.length() - Pattern.length() is that in the last loop in the second loop the index of i will be equals to the text.length() so to avoid IndexoutofBound Exception.
Note :- This Code is written in java because i have more experience solving problems with java and i couldn't find a way to access character like .charAt() in java(I was Lazy)
Code:-
public void naiveSearc(String text, String Pattern){
for(int i=0 ; i <= text.length()-Pattern.length();i++){
int j ;
for(j=0 ; j < Pattern.length();j++) {
if(text.charAt(i+j) != Pattern.charAt(j)) {
break;
}
}
if (j == Pattern.length()) {
System.out.println("Pattern found at " +i);
}
}
}
Sorry for any Typos
Top comments (1)
Thanks