TheAlgorithms
Documentation for TheAlgorithms.
TheAlgorithms.AbstractBinarySearchTree_arr
TheAlgorithms.AbstractBinaryTree_arr
TheAlgorithms.BinaryHeap
TheAlgorithms.DisjointSet
TheAlgorithms.abs_max
TheAlgorithms.abs_min
TheAlgorithms.abs_val
TheAlgorithms.area_circle
TheAlgorithms.area_ellipse
TheAlgorithms.area_heron_triangle
TheAlgorithms.area_parallelogram
TheAlgorithms.area_polygon
TheAlgorithms.area_rectangle
TheAlgorithms.area_regular_polygon
TheAlgorithms.area_rhombus
TheAlgorithms.area_square
TheAlgorithms.area_trapezium
TheAlgorithms.area_triangle
TheAlgorithms.atbash_encode
TheAlgorithms.bab_sqrt
TheAlgorithms.binary_search
TheAlgorithms.binary_search
TheAlgorithms.caesar
TheAlgorithms.ceil_val
TheAlgorithms.celsius_to_fahrenheit
TheAlgorithms.celsius_to_kelvin
TheAlgorithms.coin_change
TheAlgorithms.complete_pack!
TheAlgorithms.complete_pack!
TheAlgorithms.count_nucleotides
TheAlgorithms.counting_sort!
TheAlgorithms.detect_anagrams
TheAlgorithms.determinant
TheAlgorithms.dijkstra
TheAlgorithms.dna2rna
TheAlgorithms.eratosthenes
TheAlgorithms.euler_method
TheAlgorithms.exponential_search
TheAlgorithms.factorial_iterative
TheAlgorithms.factorial_recursive
TheAlgorithms.fahrenheit_to_celsius
TheAlgorithms.fahrenheit_to_kelvin
TheAlgorithms.fcfs
TheAlgorithms.find
TheAlgorithms.floor_val
TheAlgorithms.gauss_jordan
TheAlgorithms.get_dijkstra_path
TheAlgorithms.heap_sort!
TheAlgorithms.idx_for
TheAlgorithms.interpolation_search
TheAlgorithms.is_armstrong
TheAlgorithms.isbefore
TheAlgorithms.ispangram
TheAlgorithms.jump_search
TheAlgorithms.kelvin_to_celsius
TheAlgorithms.kelvin_to_fahrenheit
TheAlgorithms.krishnamurthy
TheAlgorithms.line_length
TheAlgorithms.linear_search
TheAlgorithms.lu_decompose
TheAlgorithms.mean
TheAlgorithms.median
TheAlgorithms.mode
TheAlgorithms.monte_carlo_integration
TheAlgorithms.partitions_recursive
TheAlgorithms.perfect_cube
TheAlgorithms.perfect_number
TheAlgorithms.perfect_square
TheAlgorithms.prime_check
TheAlgorithms.prime_factors
TheAlgorithms.rabin_karp
TheAlgorithms.riemann_integration
TheAlgorithms.rotation_matrix
TheAlgorithms.simpsons_integration
TheAlgorithms.sum_ap
TheAlgorithms.sum_gp
TheAlgorithms.surfarea_cube
TheAlgorithms.surfarea_sphere
TheAlgorithms.trapazoidal_area
TheAlgorithms.trapezoid_integration
TheAlgorithms.variance
TheAlgorithms.verlet_integration
TheAlgorithms.vol_circular_cylinder
TheAlgorithms.vol_cone
TheAlgorithms.vol_cube
TheAlgorithms.vol_cuboid
TheAlgorithms.vol_prism
TheAlgorithms.vol_pyramid
TheAlgorithms.vol_right_circ_cone
TheAlgorithms.vol_sphere
TheAlgorithms.word_count
TheAlgorithms.zero_one_pack!
TheAlgorithms.zero_one_pack!
TheAlgorithms.AbstractBinarySearchTree_arr
— Typearray-based binary search tree left tree values < root value < right tree values
TheAlgorithms.AbstractBinaryTree_arr
— Typearray-based binary tree
TheAlgorithms.BinaryHeap
— TypeBinaryHeap{T,HT}
A heap data structures implemented as a binary tree. It can be instantiated either as a MinHeap
or MaxHeap
. In a MinHeap
each element in the tree is smaller than its children, and similarly, in a MaxHeap
each element is greater than its children, this is called "Heap Property".
One of the most common usage of the Heaps is as a Priority Queue. Note that the element with highest priority will always be at the root of the tree.
In this implementation, the tree is store in a Vector
where the first element (index = 1
) is the root and for all elements, it's children will be at index * 2
and index * 2 + 1
. The methods are implemented just once for both min and max heap, and it relies on the multiple dispatch of the isbefore
function that will depend on the heap type.
Functions:
MinHeap{T}
/MaxHeap{T}
: constructorspush!(heap, elements...)
: push elements into the heaptop(heap)
: get the top element (smaller in aMinHeap
, greater in aMaxHeap
)pop!(heap)
: get top element and remove it from the heapisempty(heap)
: wheter theres no elemets in the heaplength(heap)
: how many elements are in the heap
Example
heap = MinHeap{Int}()
push!(heap, 4, 2, 3, 1, 5)
while !isempty(heap)
println(pop!(heap))
end
# output
1
2
3
4
5
Complexities:
- Space: O(n)
- Get top element: O(1)
- Push a element: O(log n)
- Pop a element: O(log n)
- Get number of elements: O(1)
Contributed By: Gabriel Soares
TheAlgorithms.DisjointSet
— TypeThis can contain a maximum of length(par)
parenting-relations par is an array of Int
, which is the index of the parent node.
TheAlgorithms.abs_max
— Methodabs_max(x)
Program to find the max absolute value in a vector
Example
abs_max([1,3,4]) # returns 4
abs_max([-3,1,2]) # returns -3
abs_max([-7,-3,6]) #returns -7
Contributed By:- Ashwani Rathee and Rratic
TheAlgorithms.abs_min
— Methodabs_min(num)
Program to find the min absolute value in a vector
Example
abs_min([1,3,4]) # returns 1
abs_min([-3,1,2]) # returns 1
abs_min([-7,-3,6]) #returns -3
Contributed By:- Ashwani Rathee and Rratic
TheAlgorithms.abs_val
— Methodabs_val(num)
Program to find the absolute value of a number
Example
abs_val(-100) # returns 100
abs_val(0) # returns 0
abs(123.1) # returns 123.1
-1000 == abs_val(-1000) #returns false
1000 == abs_val(1000) #returns true
Contributed By:- Ashwani Rathee and Rratic
TheAlgorithms.area_circle
— Methodarea_circle(radius)
Finds area of the circle
Example
area_circle(20) # returns 1256.6370614359173
area_circle(-1) # returns DomainError
TheAlgorithms.area_ellipse
— Methodarea_ellipse(radius_x, radius_y)
Finds area of the ellipse
Example
area_ellipse(10, 10) # returns 314.1592653589793
area_ellipse(10, 20) # returns 628.3185307179587
area_ellipse(1, -2) # returns DomainError
area_ellipse(-1, 2) # returns DomainError
area_ellipse(-1, -2) # returns DomainError
TheAlgorithms.area_heron_triangle
— Methodarea_heron_triangle(side1, side2, side3)
Finds area of a triangle using heron's formula
Example
area_heron_triangle(5,12,13) # returns 30.0
area_heron_triangle(-1,-2,1) # returns DomainError
area_heron_triangle(1,-2,1) # returns DomainError
area_heron_triangle(-1,2,1) # returns DomainError
TheAlgorithms.area_parallelogram
— Methodarea_parallelogram(base, height)
Finds area of the parallelogram
Example
area_parallelogram(10,20) # returns 200
area_parallelogram(-1,-2) # returns DomainError
area_parallelogram(1,-2) # returns DomainError
area_parallelogram(-1,2) # returns DomainError
TheAlgorithms.area_polygon
— Methodarea_polygon(V)
Finds area of any Polygon given by continuous sequence of vertex coordinates Arguments:
- coords: x,y co-ordinates of the vertices [Vector of Tuples / Matrix with 2 rows or 2 columns]
Example
area_polygon([(0, 0), (100, 0), (0, 100)]) # returns 5000.0
area_polygon([0 0;100 0;100 100;0 100]) # returns 10000.0
area_polygon([(6, 4.5), (5, 4.5), (4.5, 5.5), (5, 6.5)]) # returns 1.5
area_polygon([0 0;100 0]) # returns DomainError
area_polygon([(6, 4.63), (5, 4.63)]) # returns DomainError
TheAlgorithms.area_rectangle
— Methodarea_rectangle(length, width)
Finds area of the rectangle
Example
area_rectangle(10,20) # returns 200
area_rectangle(-1,-2) # returns DomainError
area_rectangle(1,-2) # returns DomainError
area_rectangle(-1,2) # returns DomainError
TheAlgorithms.area_regular_polygon
— Methodarea_regular_polygon(sides, side_len)
Finds area of any regular Polygon
Example
area_regular_polygon(1, 5) # returns DomainError
area_regular_polygon(3, 5) # returns 10.825317547305486
area_regular_polygon(7, 15) # returns 817.6302999003576
area_regular_polygon(-1, 4) # returns DomainError
area_regular_polygon(4, -3) # returns DomainError
area_regular_polygon(-12, -4) # returns DomainError
TheAlgorithms.area_rhombus
— Methodarea_rhombus(diagonal_1, diagonal_2)
Finds area of the rhombus
Example
area_rhombus(10, 20) # returns 100.0
area_rhombus(-1,-2) # returns DomainError
area_rhombus(1,-2) # returns DomainError
area_rhombus(-1,2) # returns DomainError
TheAlgorithms.area_square
— Methodarea_square(side)
Finds area of the area_square
Example
area_square(10) # returns 100
area_square(-1) # returns DomainError
TheAlgorithms.area_trapezium
— Methodarea_trapezium(base1,base2,height)
Finds area of the traπzium
Example
area_trapezium(10, 20, 30) # returns 450.0
area_trapezium(-1, -2, -3) # returns DomainError
area_trapezium(-1, 2, 3) # returns DomainError
area_trapezium(1, -2, 3) # returns DomainError
area_trapezium(1, 2, -3) # returns DomainError
area_trapezium(-1, -2, 3) # returns DomainError
area_trapezium(1, -2, -3) # returns DomainError
area_trapezium(-1, 2, -3) # returns DomainError
TheAlgorithms.area_triangle
— Methodarea_triangle(base, height)
Finds area of the right angled triangle with base height
Example
area_triangle(10,10) # returns 50.0
area_triangle(-1,-2) # returns DomainError
area_triangle(1,-2) # returns DomainError
area_triangle(-1,2) # returns DomainError
TheAlgorithms.atbash_encode
— Methodencode(input)
Program to implement atbash cipher for the given sentence.A full description of the algorithm can be found on wikipedia
Arguments:
input
: The sentence needed to rotate
Examples/Tests
julia> atbash_encode("test")
gvhg
julia> atbash_encode("abcdefghijklmnopqrstuvwxyz")
zyxwvutsrqponmlkjihgfedcba
julia> atbash_encode("hello")
svool
Algorithm:
for r in input
part *= xform(r)
if length(part) >= 5
push!(parts, part)
part = ""
end
end
if part != ""
push!(parts, part)
end
return join(parts, " ")
References:
https://en.wikipedia.org/wiki/Atbash
```
Contributed by:- Ihjass Thasbekha
TheAlgorithms.bab_sqrt
— Methodbab_sqrt(S::Real; tolerance = 1e-6, guess = nothing)
The Babylonian Method of calculating a square root is a simple iterative method to determine square roots. A full description of the algorithm can be found on Wikipedia
Arguments:
S
: The number to calculate the square root for.
Positional Arguments
tolerance
: How close the square of the square root needs to be from the input value.abs(S - xn^2) < tolerance
guess
: The initial value to use forxn
Examples/Tests
julia> bab_sqrt(100)
10.000000000107445
julia> bab_sqrt(100, guess = 15)
10.000000000131072
julia> bab_sqrt(π, guess = 1)
1.7724538555800293
julia> bab_sqrt(π, guess = 1, tolerance = 2)
2.0707963267948966
Algorithm:
while tolerance <= abs(xn^2 - S)
xn = (1 / 2) * (xn + S / xn)
end
References:
Methods of computing square roots
```
Contributed by:- Anson Biggs
TheAlgorithms.binary_search
— Methodbinary_search(list, query; rev=false, lt=<, by=identity)
Implement a binary search algorithm. Searching a sorted collection is a common task. A dictionary is a sorted list of word definitions. Given a word, one can find its definition. A telephone book is a sorted list of people's names, addresses, and telephone numbers. Knowing someone's name allows one to quickly find their telephone number and address.
If the list to be searched contains more than a few items (a dozen, say) a binary search will require far fewer comparisons than a linear search, but it imposes the requirement that the list be sorted.
In computer science, a binary search or half-interval search algorithm finds the position of a specified input value (the search "key") within an array sorted by key value.
In each step, the algorithm compares the search key value with the key value of the middle element of the array.
If the keys match, then a matching element has been found and the range of indices that equal the search key value are returned.
Otherwise, if the search key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right.
If the remaining array to be searched is empty, then the key cannot be found in the array and a special "not found" indication is returned. Search methods in Julia typically return an empty range located at the insertion point in this case.
A binary search halves the number of items to check with each iteration, so locating an item (or determining its absence) takes logarithmic time. A binary search is a dichotomic divide and conquer search algorithm.
Bonus task: Implement keyword arguments by, lt and rev so that by specifies a transformation applied to all elements of the list, lt specifies a comparison and rev specifies if the list is ordered in reverse.
Contributed By:- Soc Virnyl Estela
TheAlgorithms.binary_search
— Methodbinary_search(arr::AbstractArray{T,1}, l::T, r::T, x::T) where {T<:Real}
The implementation of this binary Search is recursive and requires O(Log n) space. With iterative Binary Search, we need only O(1) space. Useful for the implementation of exponential_search
.
Contributed By:- Ash
TheAlgorithms.caesar
— Methodcaesar(rot, s)
Program to implement rotational cipher for the given sentence. A full description of the algorithm can be found on wikipedia
Arguments:
rot
: The number of rotations needed.s
: The sentence needed to rotate
Examples/Tests
julia> caesar(13,"abcdefghijklmnopqrstuvwxyz")
nopqrstuvwxyzabcdefghijklm
julia> caesar(5,"omg")
trl
julia> caesar(0,"hello")
hello
Algorithm:
if r >= 'a' && r <= 'z'
v = ((r - 'a') + rot) % 26
return v + 'a'
end
if r >= 'A' && r <= 'Z'
v = ((r - 'A') + rot) % 26
return v + 'A'
end
return r
References:
https://en.wikipedia.org/wiki/Caesar_cipher
```
Contributed by:- Ihjass Thasbekha
TheAlgorithms.ceil_val
— Methodceil_val(x)
Finds the ceiling of x as an functionInteger
Example
ceil_val(1.3) # 2.0
ceil_val(2.0) # returns 2.0
ceil_val(-1.5) #returns -1.0
Reference
- https://en.wikipedia.org/wiki/Floorandceiling_functions
Contributed By:- Ashwani Rathee
TheAlgorithms.celsius_to_fahrenheit
— Functioncelsiustofahrenheit(celsius, ndigits::Int = 2)
Converts celsius to fahrenheit and round to 2 decimal places
Example
celsius_to_fahrenheit(273.354, 3) == 524.037 # returns true
celsius_to_fahrenheit(273.354, 0) == 524.0 # returns true
celsius_to_fahrenheit(-40.0) == -40.0 # returns true
celsius_to_fahrenheit(-20.0) == -4.0 # returns true
celsius_to_fahrenheit(0) == 32.0 # returns true
celsius_to_fahrenheit(20) == 68.0 # returns true
TheAlgorithms.celsius_to_kelvin
— Functionfunction celsiustokelvin(celsius, ndigits::Int = 2)
Converts celsius to kelvin and round to 2 decimal places
Example
celsius_to_kelvin(273.354, 3) == 546.504 # returns true
celsius_to_kelvin(273.354, 0) == 547.0 # returns true
celsius_to_kelvin(0.0) == 273.15 # returns true
celsius_to_kelvin(20.0) == 293.15 # returns true
TheAlgorithms.coin_change
— Methodcoin_change(coins::Vector{Int}, amount::Int)
Given a vector coins
of coin values, calculates the minimum number of coins that sums to amount
. It's considered that a unlimited number of coins for each value is available.
Arguments:
coins
: the coins values availableamount
: the total amount that need to be summed to
Examples
julia> n_coins, coins = coin_change([1, 3, 4, 7], 13);
julia> n_coins
3
julia> coins
3-element Vector{Int64}:
3
3
7
julia> n_coins, coins = coin_change([2, 4, 6], 23)
(-1, Int64[])
julia> n_coins
-1
julia> coins
Int64[]
Contributors:
TheAlgorithms.complete_pack!
— MethodThis does complete/infinite (each item can be chosen infinite times) knapsack : pack capacity = capacity weight of each item = weights value of each item = values dp array is what the function works on It returns the ans (dp[capacity])
julia> dp=zeros(Int,30)
julia> complete_pack!(20,[1,2,9],[1,3,20],dp)
43
TheAlgorithms.complete_pack!
— MethodThis does complete/infinite (each item can be chosen infinite times) knapsack : pack capacity = capacity weight of each item = weights value of each item = values
Each loop the function will find the highest value in the array and check if the capacity is enough to store it, if enough then the value will be added into the totalmaxvalue until the capacity cannot hold the weight of the highest current value. After that the highest current value will be deleted.
julia> complete_pack!(20,[1,2,9],[1,3,20])
43
TheAlgorithms.count_nucleotides
— Methodcount_nucleotides(s::AbstractString)
Given: A DNA string s
of length at most 1000 nt.
Return: Four integers (separated by spaces) counting the respective number of times that the symbols 'A', 'C', 'G', and 'T' occur in s
TheAlgorithms.counting_sort!
— MethodCounting Sort
OVERVIEW: Counting Sort is a sorting algorithm that sort elements within a specific range. The sorting technique is to count the existing element and stored its occurrence time in a new list, then only print it out.
STEPS: Assume the input as –> x=[-3, 1, -5, 0, -3] minimum = -5
STEP 1: Create a list size within the range, in this case is -5 –> 1 which have range of 7 (-5, -4, -3, -2, -1, 0, 1), so list with size 7 and assign all to 0 is created
STEP 2: Count the occurances of element in the list First number = -3 it is the third number in the range, so count[3]+=1 Final view: index : ( 1, 2, 3, 4, 5, 6, 7) range : (-5, -4, -3, -2, -1, 0, 1) count : [ 1, 0, 2, 0, 0, 1, 1] <– the list will store this occurrence
STEP 3: Make the count list accumulate the occurances The final count is (1, 1, 3, 3, 3, 4, 5)
STEP 4: Assign the elements in x into correct possition by creating a new list (will call 'output' in this sample) the 1st element in 'x' is -3, it is third in range, so it will call the index of 3 in 'count', which is 3 and assign the -3 in to 3rd position in 'output', then the third element in range will deduct by 1, so the next repeated element will get the correct position, new 'count' –> [1, 1, 2, 3, 3, 4, 5]
the 2nd element in 'x' is 1, it is last in range, so it will call the index of 7 in 'count', which is 5 and assign the 1 in to 5th position in 'output', new 'count' --> [1, 1, 2, 3, 3, 4, 4] ...... ...... *If you want the order of original array to have the same order as the output array use can change this to decremental for loop
STEP 5: Assign the 'output' list back to 'x'
FINAL RESULT –> [-5, -3, -3, 0, 1]
TheAlgorithms.detect_anagrams
— Methoddetect_anagrams(subject, candidates)
A function that checks if a list of words is an Anagram or not of a subject word.
is the original word = subject is list of words to be compared if they are an anagram of subject
= candidates
julia> subject = "listen"
julia> candidates = ["inlets", "enlists", "google", "banana"]
julia> detect_anagrams(subject, candidates)
1-element Vector{String}:
"inlets"
Contributed By:- Soc V. E. Based on my exercism's Julia track problem solution on Anagrams.
Instructions:
An anagram is a rearrangement of letters to form a new word. Given a word and a list of candidates, select the sublist of anagrams of the given word. Given "listen" and a list of candidates like "enlists" "google" "inlets" "banana" the program should return a list containing "inlets".
Inspired by the Extreme Startup game
TheAlgorithms.determinant
— Methoddeterminant(mat)
Given a non singluar matrix, calculate its determinant using LU decomposition.
L and U are lower triangular and upper triangular matrices respectively such that
A = L*U
If we want to find the determinant, then
det(A) = det(LU) = det(L)*det(U)
Determinant of triangualar matrices is the product of their diagonal entries. Hence, makes finding the determinant easy.
TheAlgorithms.dijkstra
— Methoddijkstra(graph::Vector{Vector{Tuple{Int,Int}}}, source::Int)
Given a directed graph with weights on the arcs and a source vertex, the dijkstra algorithm calculates the distance from the source to all other vertices, and the solution tree associated with those distances. The solution tree is given by a vector prev
which stores the source of the arc that arrives at each vertex. By definition: distance[source] = prev[source] = 0. If a vertex v is not reachable from the source, then distance[v] = prev[v] = -1.
Arguments:
graph
: a directed graph with weights on the arcssource
: the source vertex from which the distances will be calculated
Example
graph = [
[(2, 8), (3, 6), (4, 4)],
[(3, 1), (5, 5)],
[(5, 4)],
[(2, 3), (5, 9)],
[(1, 2), (3, 2), (4, 5)],
[(1, 1), (4, 3)],
]
distances, prev = dijkstra(graph, 1)
println("v | dist | path")
for v in eachindex(graph)
distance = distances[v] == -1 ? " NR" : lpad(distances[v], 4) # NR: Non Reachable
path = join(get_dijkstra_path(prev, v), " -> ")
println("$v | $distance | $path")
end
# output
v | dist | path
1 | 0 | 1
2 | 7 | 1 -> 4 -> 2
3 | 6 | 1 -> 3
4 | 4 | 1 -> 4
5 | 10 | 1 -> 3 -> 5
6 | NR |
Contributed By: Gabriel Soares
TheAlgorithms.dna2rna
— Methoddna2rna(s::AbstractString)
Given: A DNA string t
having length at most 1000 nt.
Return: The transcribed RNA string of t
TheAlgorithms.eratosthenes
— MethodSieve of Eratosthenes is an algorithm for finding all the primes upto a limit n
.
Reference: -https://en.wikipedia.org/wiki/SieveofEratosthenes
TheAlgorithms.euler_method
— Functioneuler_method(f, x0, span, h=1.0e-2)
Calculate the solution to a differential equation using forward euler method.
TheAlgorithms.exponential_search
— Method exponential_search(arr::AbstractArray{T,1}, x::T) where {T <: Real}
Exponential Search in 1-D array Time Complexity: O(Log n)
Exponential Search
It works in O(Log n) time Exponential search involves two steps:
- Find range where element is present
- Do Binary Search in above found range.
Time Complexity :
O(Log n) Applications of Exponential Search: Exponential Binary Search is particularly useful for unbounded searches, where size of array is infinite. Please refer Unbounded Binary Search for an example. It works better than Binary Search for bounded arrays, and also when the element to be searched is closer to the first element.
Contributed By:- Ash
TheAlgorithms.factorial_iterative
— Methodfactorial_iterative(n)
Finds factorial of a number using Iterative method
Example
factorial_iterative(5) # returns 120
factorial_iterative(-1) # returns error
Reference
- factorial of a positive integer – https://en.wikipedia.org/wiki/Factorial
Contributed By:- Ashwani Rathee and Rratic
TheAlgorithms.factorial_recursive
— Methodfactorial_recursive(n)
Finds factorial of a number using recursive method
Example
factorial_recursive(5) # returns 120
Reference
- factorial of a positive integer – https://en.wikipedia.org/wiki/Factorial
Contributed By:- Ashwani Rathee and Rratic
TheAlgorithms.fahrenheit_to_celsius
— Functionfahrenheittocelsius(fahrenheit, ndigits::Int = 2)
Converts fahrenheit to celsius and round to 2 decimal places
Example
fahrenheit_to_celsius(273.354, 3) == 134.086 # returns true
fahrenheit_to_celsius(273.354, 0) == 134.0 # returns true
fahrenheit_to_celsius(0.0) == -17.78 # returns true
fahrenheit_to_celsius(20.0) == -6.67 # returns true
fahrenheit_to_celsius(40.0) == 4.44 # returns true
fahrenheit_to_celsius(60.0) == 15.56 # returns true
fahrenheit_to_celsius(80.0) == 26.67 # returns true
TheAlgorithms.fahrenheit_to_kelvin
— Functionfahrenheittokelvin(fahrenheit, ndigits::Int = 2)
Converts fahrenheit to kelvin and round to 2 decimal places
Example
fahrenheit_to_kelvin(273.354, 3) == 407.236 # returns true
fahrenheit_to_kelvin(273.354, 0) == 407.0 # returns true
fahrenheit_to_kelvin(0) == 255.37 # returns true
fahrenheit_to_kelvin(20.0) == 266.48 # returns true
fahrenheit_to_kelvin(40.0) == 277.59 # returns true
fahrenheit_to_kelvin(60.0) == 288.71 # returns true
fahrenheit_to_kelvin(80.0) == 299.82 # returns true
TheAlgorithms.fcfs
— Methodfcfs(n, process_id, burst_time)
Implementation of first come first served scheduling algorithm
Output
Tuple of vectors (processid, bursttime, waitingtime, turnaroundtime, avgwaitingtime, avgturnaroundtime)
Example
n = 3 # number of processes
process_id = Any[1, 2, 3] # process ids
burst_times = Any[3, 4, 5] # burst times
fcfs(n, process_id, burst_times)
Reference
https://en.wikipedia.org/wiki/Scheduling(computing)#Firstcome,firstserved
Contributed By:- Ashwani Rathee
TheAlgorithms.find
— MethodFind the ancestor of node x
.
TheAlgorithms.floor_val
— Methodfloor_val(x)
Finds the floor of x as an Integer
Example
floor_val(1.3) # 1
floor_val(2.0) # returns 2.0
floor_val(-1.7) # returns -2.0
Reference
- https://en.wikipedia.org/wiki/Floorandceiling_functions
Contributed By:- Ashwani Rathee
TheAlgorithms.gauss_jordan
— Methodgauss_jordan(A::AbstractMatrix{T}) where T<:Number
Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used to compute the rank of a matrix, the determinant of a square matrix, and the inverse of an invertible matrix. https://en.wikipedia.org/wiki/Gaussian_elimination
Examples/Tests
julia> M1 = [1 2 3; 4 5 6];
julia> M2 = [1 2 3; 4 8 12];
julia> @test gauss_jordan(M1) == [1 0 -1; 0 1 2] # Test Passed
julia> @test_throws AssertionError gauss_jordan(M2) # Test Passed - Thrown: AssertionError
Contributed By:- AugustoCL
TheAlgorithms.get_dijkstra_path
— Methodget_dijkstra_path(tree::Vector{Int}, dest::Int)
Given a solution tree
from the dijkstra
algorithm, extract the path from the source to dest
, including them.
Arguments:
tree
: solution tree from thedijkstra
algorithmdest
: path's destionation vertex
TheAlgorithms.heap_sort!
— Methodheap_sort!(arr::Vector{T}, gt = >, N::Int = length(arr)) where {T}
Sort the given vector (in-place) using the Heapsort algorithm.
Heapsort consists of two stages:
- Building a (max) heap of the array
- Repeatedly extracting the largest element and inserting it at the front of the sorted part of the array
After the largest element has been extracted, the tree is updated to maintain the heap property via a "sifting" operation.
Storing a heap in an array is pretty straightforward - for every node with index n, its children are stored at indices 2n + 1 and 2n + 2 (for 0-based indices). Index 0 contains the root node. Since Julia's indices are 1-based, we need to change this a little bit. We're using a trivial helper function idx_for to convert from 0-based to 1-based.
See https://en.wikipedia.org/wiki/Heapsort for a complete explanation of Heapsort.
Contributed By:- Frank Schmitt
TheAlgorithms.idx_for
— Methodidx_for(i::Int)
Simple helper function for converting 0-based indices to Julia's 1-based indices.
TheAlgorithms.interpolation_search
— Method interpolation_search(arr::AbstractArray{T,1}, l::T, r::T, x::T) where {T <: Real}
Interpolation Search in 1-D array Time Complexity: O(log2(log2 n))
TheAlgorithms.is_armstrong
— Methodis_armstrong(x)
Program to check if a number is an Armstrong/Narcissistic number in decimal system.
Armstrong number is a number that is the sum of its own digits raised to the power of the number of digits.
Contributed By:- Ashwani Rathee
A positive integer is called an Armstrong number (of order n) if
abcd... = a^n + b^n + c^n + d^n +....
TheAlgorithms.isbefore
— Methodisbefore(heap, x, y)
Whether x
comes before y
in the heap
ordering.
TheAlgorithms.ispangram
— Methodispangram(input)
Program to determine the sentence is pangram or not.The program will return true if it is pangram and false if it is not.A full description of the algorithm can be found on exercism
Arguments:
input
: The sentence to find if its pangram or not.
Examples/Tests
julia> ispangram(Pack my box with five dozen liquor jugs)
true
julia> ispangram(The quick brown fox jumps over the lazy dog)
true
julia> wordcount(hello world!!!)
false
Algorithm:
for letter in input
if 'A' <= letter <= 'Z'
x &= ~(1<<(letter-'A'))
elseif 'a' <= letter <= 'z'
x &= ~(1<<(letter-'a'))
end
x == 0 && return true
end
References:
(https://exercism.org/tracks/julia/exercises/pangram)
```
Contributed by:- Ihjass Thasbekha
TheAlgorithms.jump_search
— Methodjump_search(arr::AbstractArray{T,1}, x::T, jump::T = Int(ceil(sqrt(n)))) where {T <: Real}
Jump Search in 1-D array Time Complexity : O(√ n) Time complexity of Jump Search is between Linear Search ( ( O(n) ) and Binary Search ( O (Log n) )
TheAlgorithms.kelvin_to_celsius
— Functionfunction kelvintocelsius(kelvin, ndigits::Int = 2)
Converts kelvin to celsius and round to 2 decimal places
Example
kelvin_to_celsius(273.354, 3) == 0.204 # returns true
kelvin_to_celsius(273.354, 0) == 0.0 # returns true
kelvin_to_celsius(273.15) == 0.0 # returns true
kelvin_to_celsius(300) == 26.85 # returns true
TheAlgorithms.kelvin_to_fahrenheit
— Functionfunction kelvintofahrenheit(kelvin, ndigits::Int = 2)
Converts kelvin to fahrenheit and round to 2 decimal places
Example
kelvin_to_fahrenheit(273.354, 3) == 32.367 # returns true
kelvin_to_fahrenheit(273.354, 0) == 32.0 # returns true
kelvin_to_fahrenheit(273.15) == 32.0 # returns true
kelvin_to_fahrenheit(300) == 80.33 # returns true
TheAlgorithms.krishnamurthy
— Methodkrishnamurthy(number)
Check if a number is a Krishnamurthy number or not
Details
It is also known as Peterson Number.
A Krishnamurthy Number is a number whose sum of the factorial of the digits equals to the original number itself.
For example: 145 = 1! + 4! + 5! So, 145 is a Krishnamurthy Number
Example
krishnamurthy(145) # returns true
krishnamurthy(240) # returns false
krishnamurthy(1) # returns true
Contributed By:- Ashwani Rathee
TheAlgorithms.line_length
— Functionline_length(f, x_start, x_end, steps=100)
Approximates the arc length of a line segment by treating the curve as a sequence of linear lines and summing their lengths.
Arguments:
- f: function that returns the arc
- x_start: starting x value
- xend: ending xvalue
- steps: steps to take for accurace, more the steps greater the accuracy
TheAlgorithms.linear_search
— Methodlinear_search(array, key)
A simple search of array
, element per element until key
is found.
TheAlgorithms.lu_decompose
— Methodlu_decompose(mat)
Decomposes a n x n
non singular matrix into a lower triangular matrix (L) and an upper triangular matrix (U)
TheAlgorithms.mean
— Methodmean(nums)
Find mean of a vector of numbers
Example
mean([3, 6, 9, 12, 15, 18, 21]) # returns 12.0
mean([5, 10, 15, 20, 25, 30, 35]) # returns 20.0
mean([1, 2, 3, 4, 5, 6, 7, 8]) # returns 4.5
Contributed By:- Ashwani Rathee and Rratic
TheAlgorithms.median
— Methodmedian(nums)
Finds median of a vector of numbers
Example
median([2,1,3,4]) # returns 2.5
median([2, 70, 6, 50, 20, 8, 4]) # returns 8
median([0]) # returns 0
Contributed By:- Ashwani Rathee and Rratic
TheAlgorithms.mode
— Methodmode(nums)
Finds mode of a vector of numbers
Example
mode([2, 3, 4, 5, 3, 4, 2, 5, 2, 2, 4, 2, 2, 2]) # returns [2]
mode([3, 4, 5, 3, 4, 2, 5, 2, 2, 4, 4, 2, 2, 2]) # returns [2]
mode([3, 4, 5, 3, 4, 2, 5, 2, 2, 4, 4, 4, 2, 2, 4, 2]) # returns [2, 4]
mode(["x", "y", "y", "z"]) # returns ["y"]
mode(["x", "x" , "y", "y", "z"]) # returns ["x", "y"]
Contributed By:- Ashwani Rathee
TheAlgorithms.monte_carlo_integration
— Methodmonte_carlo_integration(f::Function, a::Real, b::Real, n::Int)
Monte carlo integration is a very easy and scalable way to do multidimentional integrals. However, only single variable integrals are considered.
Arguments
f
: the function to integrate. (at the momment only single variable is suported)a
: start in the integration limits.b
: endin the integration limits.N
: Number of points to sample. For most simple functions, 1000 to 10,000 should be okay.
Examples
julia> monte_carlo_integration(x -> 3*x^2, 0, 1, 100000) # integrate a polynomial
1.0000037602209
julia> monte_carlo_integration(x -> sin(x), 0, pi, 1000) # integrate the sin function
2.0018927826323756
References
- https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/monte-carlo-methods-in-practice/monte-carlo-integration
- https://kingaa.github.io/sbied/pfilter/monteCarlo.html
Contributors
TheAlgorithms.partitions_recursive
— Methodpartitions_recursive(n)
Finds partitions of an integer using recursion.
A partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers.
There are 7 partitions of 5: 5 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1
Partitions of n is equal to the sum of partitions of n with k parts.
$P \left ( n \right ) = \sum_{k=1}^{n} P_{k} \left ( n \right )$
Partitions of n with k parts is the sum of partitions of n-1 with k-1 parts and, partitions of n-k with k parts.
$P_{k}\left ( n \right ) = P_{k-1}\left ( n - 1 \right ) + P_{k}\left ( n - k \right )$
Example
partitions_recursive(0) # returns 1
partitions_recursive(1) # returns 1
partitions_recursive(10) # returns 42
partitions_recursive(-1) # returns DomainError
References
- Partitions of a positive integer – https://en.wikipedia.org/wiki/Partitionfunction(number_theory)
- Partitions of a positive integer – https://www.whitman.edu/mathematics/cgt_online/book/section03.03.html
Contributor
TheAlgorithms.perfect_cube
— Methodperfect_cube(number)
Check if a number is a perfect cube or not.
Example
perfect_cube(27) # returns true
perfect_cube(4) # returns false
Contributed By:- Ashwani Rathee and Rratic
TheAlgorithms.perfect_number
— Methodperfect_number(number)
Checks if a number is a perfect_number number or not
Details
perfect_number number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself.
For example : 6 is perfect_number number
Divisors of 6 => [1,2,3]
Sum of divisors => 1+2+3 = 6
6 == sum(divisors) # which is true
Example
perfect_number(27) # returns false
perfect_number(28) # returns true
perfect_number(496) # returns true
perfect_number(8128) # returns true
perfect_number(123) # returns false
Contributed By:- Ashwani Rathee and Rratic
TheAlgorithms.perfect_square
— Methodperfect_square(number)
Check if a number is a perfect square or not.
Example
perfect_square(9) # returns True
perfect_square(16) # returns True
perfect_square(1) # returns True
perfect_square(0) # returns True
perfect_square(10) # returns False
perfect_square(-9) # returns False
Contributed By:- Ashwani Rathee and Rratic
TheAlgorithms.prime_check
— Methodprime_check(number)
Checks to see if a number is a prime or not
A number is prime if it has exactly two factors: 1 and itself.
Example
prime_check(2) # returns true
prime_check(3) # returns true
prime_check(5) # returns true
prime_check(7) # returns true
prime_check(11) # returns true
prime_check(13) # returns true
prime_check(17) # returns true
prime_check(19) # returns true
prime_check(23) # returns true
prime_check(29) # returns true
prime_check(30) # returns false
Contributed By:- Ashwani Rathee and Rratic
TheAlgorithms.prime_factors
— Methodprime_factors(number)
Returns prime factors of number
as a vector
Example
prime_factors(50) # returns [2,5,5]
prime_factors(0) # returns []
prime_factors(100) # returns [2, 2, 5, 5]
prime_factors(2560) # returns [2, 2, 2, 2, 2, 2, 2, 2, 2, 5]
Contributed By:- Ashwani Rathee
TheAlgorithms.rabin_karp
— Methodrabin_karp(text, pattern)
Brief:
A function that finds all occurrences of a pattern in the given text.
Instead of checking each character ot the pattern with each character block of the text,
for each character block calculate the hash value, and only if that value matches hash value of the pattern,
compare them character by character. These blocks are the same length as the pattern.
Returns:
A list with starting indices where the pattern was found
References:
https://www.geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching/
Contributed by: Nikola Mircic
TheAlgorithms.riemann_integration
— Functionriemann_integration(f::Function, a::Real, b::Real, n::Int, approx::Symbol = :midpoint)
a Riemann sum is a certain kind of approximation of an integral by a finite sum. The sum is calculated by partitioning the region into shapes (rectangles, trapezoids, parabolas, or cubics) that together form a region that is similar to the region being measured, then calculating the area for each of these shapes, and finally adding all of these small areas together.
Because the region filled by the small shapes is usually not exactly the same shape as the region being measured, the Riemann sum will differ from the area being measured. This error can be reduced by dividing up the region more finely, using smaller and smaller shapes. As the shapes get smaller and smaller, the sum approaches the Riemann integral.
Arguments
f
: the function to integrate. (at the momment only single variable is suported)a
: Start of the integration limit.b
: End of the integration limit.n
: Number of points to sample. (as n increase, error decrease)approx
: Indicate the method of approximation (midpoint, left or right)
Examples
julia> riemann_integration(x -> x, 1, 3, 1_000, :midpoint) # 4.0
julia> riemann_integration(x -> x, 1, 3, 1_000, :left) # 3.997997997997998
julia> riemann_integration(x -> x, 1, 3, 1_000, :right) # 4.002002002002002
julia> riemann_integration(x -> 3*x^2, 0, 1, 100000) # integrate a polynomial
0.9999999999750021
julia> riemann_integration(x -> sin(x), 0, pi, 1000) # integrate the sin function
2.0000008241146774
Refereces
- https://www.khanacademy.org/math/ap-calculus-ab/ab-integration-new/ab-6-2/a/riemann-sums-review
- https://math.libretexts.org/Courses/MountRoyalUniversity/MATH2200%3ACalculusforScientistsII/2%3ATechniquesofIntegration/2.5%3ANumericalIntegration-Midpoint%2CTrapezoid%2CSimpson's_rule
- https://abel.math.harvard.edu/~knill/teaching/math1a_2011/handouts/40-numerical.pdf
- https://en.wikipedia.org/wiki/Riemann_integral
Contributed By:- AugustoCL
TheAlgorithms.rotation_matrix
— MethodA 2D Rotation matrix is a mtrix that rotates a vector in a 2D real space by an angle theta. For more info: https://en.wikipedia.org/wiki/Rotation_matrix
This function takes the angle theta
in radians as input and returns a 2D Matrix which will rotate the vector by angle theta
.
TheAlgorithms.simpsons_integration
— Methodsimpsons_integration(f::Function, a::Real, b::Real, n::Int)
Simpson's rule uses a quadratic polynomial on each subinterval of a partition to approximate the function f(x) and to compute the definite integral. This is an improvement over the trapezoid rule which approximates f(x) by a straight line on each subinterval of a partition. For more details of the method, check the link in the reference.
Arguments
f
: The function to integrate. (ar the moment only single variable is suported)a
: Start of the integration limit.b
: End of the integration limit.n
: Number of points to sample. (as n increase, error decrease)
Examples/Test
# aproximate pi with f(x) = 4 / (1 + x^2)
julia> simpsons_integration(x -> 4 / (1 + x^2), 0, 1, 100_000)
3.1415926535897936
julia> simpsons_integration(x -> 4 / (1 + x^2), 0, 1, 100_000) ≈ pi
true
References:
- https://personal.math.ubc.ca/~pwalls/math-python/integration/simpsons-rule/
Contributed By:- AugustoCL
TheAlgorithms.sum_ap
— Methodsum_ap(first_term, diff, num_terms)
Finds sum of a arithmetic progression series
Input parameters
- first_term : first term of the series
- diff : common difference between consecutive terms
- num_terms : number of terms in the series till which we count sum
Example
sum_ap(1, 1, 10) # returns 55.0
sum_ap(1, 10, 100) # returns 49600.0
Contributed By:- Ashwani Rathee
TheAlgorithms.sum_gp
— Methodsum_gp(first_term, ratio, num_terms)
Finds sum of n terms in a geometric progression
Input parameters
- first_term : first term of the series
- raio : common ratio between consecutive terms -> a2/a1 or a3/a2 or a4/a3
- num_terms : number of terms in the series till which we count sum
Example
sum_gp(1, 2, 10) # 1023.0
sum_gp(1, 10, 5) # 11111.0
sum_gp(0, 2, 10) # 0.0
sum_gp(1, 0, 10) # 1.0
sum_gp(1, 2, 0) # -0.0
sum_gp(-1, 2, 10) # -1023.0
sum_gp(1, -2, 10) # -341.0
Contributed By:- Ashwani Rathee
TheAlgorithms.surfarea_cube
— Methodsurfarea_cube(side)
Finds surface area of a cube
Example
surfarea_cube(1) # returns 6
surfarea_cube(3) # returns 54
surfarea_cube(-1) # returns DomainError
TheAlgorithms.surfarea_sphere
— Methodsurfarea_sphere(side)
Finds surface area of a sphere
Example
surfarea_sphere(5) # returns 314.1592653589793
surfarea_sphere(1) # returns 12.566370614359172
surfarea_sphere(-1) # returns DomainError
TheAlgorithms.trapazoidal_area
— Methodtrapazoidal_area(f, x_start, x_end, steps)
Approximates the area under the curve using the trapezoidal rule Arguments:
- f: function for the
- x_start: starting value for x
- x_end: ending value for x
- steps: steps taken while integrating.
TheAlgorithms.trapezoid_integration
— Methodtrapezoid_integration(f::Function, a::Real, b::Real, n::Int)
The trapezoidal rule works by approximating the region under the graph of the function f(x) as a trapezoid and calculating its area.
Arguments
f
: the function to integrate. (at the momment only single variable is suported)a
: Start of the integration limit.b
: End of the integration limit.n
: Number of points to sample. (as n increase, error decrease)
Examples/Test
julia> trapezoid_integration(x -> 4 / (1 + x^2), 0, 1, 100_000)
3.1415926535731526
julia> trapezoid_integration(x -> 4 / (1 + x^2), 0, 1, 100_000) ≈ pi
true
References:
-https://personal.math.ubc.ca/~pwalls/math-python/integration/trapezoid-rule/ -https://en.wikipedia.org/wiki/Trapezoidal_rule
Contributed By:- AugustoCL
TheAlgorithms.variance
— Methodvariance(a)
Find the variance from a set of data.
Arguments:
a
: holds the set of data
Reference
- According to Ronald E. Walpole, `variance` is used to measure the variability of a set of data. -- Introduction to Statistics by Ronald E. Walpole
Contributors:
TheAlgorithms.verlet_integration
— FunctionVerlet integration is an integration method used to integrate newtons - law of motion. It is frequently used to find trajectories in molecular dynamics simulation. The function takes four
inputs viz,
f
: the differential equationx0
: the initial condition. This is a Vector with the first element as initial value for position (x0) and the second initial condition for velocity (v0)tspan
: is the time span for integration. It is a tuple (initial time, final time)
This functionr returns a tuple (x,t):
x
is the solutiont
is the array containing the time points
Reference:
- https://www.algorithm-archive.org/contents/verletintegration/verletintegration.html
Contributed by: Ved Mahajan
TheAlgorithms.vol_circular_cylinder
— Methodvol_circular_cylinder(area_of_, height)
Compute the Volume of a Circular Cylinder.
Examples
```julia-repl julia> volcircularcylinder(1, 1) 3.141592653589793 julia> volcircularcylinder(4, 3) 150.79644737231007
TheAlgorithms.vol_cone
— Methodvol_cone(area_of_base, height)
Compute the Volume of a Cone
Examples
julia> vol_cone(10, 3)
10.0
julia> vol_cone(1, 1)
0.3333333333333333
TheAlgorithms.vol_cube
— Methodvol_cube()
Compute the volume of a cube.
Examples
julia> vol_cube(1)
1
julia> vol_cube(3)
27
julia> vol_cube(-1)
DomainError
TheAlgorithms.vol_cuboid
— Methodvol_cuboid(width, height, length)
Compute the volume of a vol_cuboid
Examples
julia> vol_cuboid(1, 1, 1)
1
julia> vol_cuboid(1, 2, 3)
6
TheAlgorithms.vol_prism
— Methodvol_prism(area_of_base, height)
Compute the Volume of a Prism.
Examples
julia> vol_prism(10, 2)
20.0
julia> vol_prism(11, 1)
11.0
TheAlgorithms.vol_pyramid
— Methodvol_pyramid(area_of_base, height)
Compute the volume of a Pyramid.
Examples
julia> vol_pyramid(10, 3)
10.0
julia> vol_pyramid(1.5, 3)
1.5
TheAlgorithms.vol_right_circ_cone
— Methodvol_right_circ_cone(radius, height)
Compute the Volume of a Right Circular Cone.
Examples
julia> vol_right_circ_cone(2, 3)
12.566370614359172
TheAlgorithms.vol_sphere
— Methodvol_sphere(radius)
Compute the volume of a sphere.
Examples
vol_sphere(5) # returns 523.5987755982989
vol_sphere(1) # returns 4.1887902047863905
vol_sphere(-1) # returns DomainError
TheAlgorithms.word_count
— Methodwordcount(sentence)
Program to find word count in the given sentence. The program will return count with the word. A full description of the algorithm can be found on exercism
Arguments:
sentence
: The sentence to find the word count.
Examples/Tests
julia> wordcount(The quick brown fox jumps over the lazy dog)
Dict{Any, Any}("jumps" => 1, "the" => 2, "brown" => 1, "over" => 1, "quick" => 1, "lazy" => 1, "dog" => 1, "fox" => 1)
julia> wordcount(the sky is blue and beautiful)
Dict{Any, Any}("and" => 1, "the" => 1, "sky" => 1, "blue" => 1, "is" => 1, "beautiful" => 1)
Algorithm:
for word in eachmatch(reg_expression, sentence)
if !haskey(counts, word.match)
counts[word.match] = 1
else
counts[word.match] += 1
end
end
References:
(https://exercism.org/tracks/julia/exercises/word-count)
```
Contributed by:- Ihjass Thasbekha
TheAlgorithms.zero_one_pack!
— Methodzero_one_pack!(capacity::N, weights::V, values::V, dp::V) where {N <: Number,V <: AbstractVector}
This does 0-1 (each item can be chosen only once) knapsack : pack capacity = capacity weight of each item = weights value of each item = values dp array is what the function works on It returns the ans (dp[capacity])
julia> dp=zeros(Int,30)
julia> zero_one_pack!(20,[1,3,11],[2,5,30],dp)
37
TheAlgorithms.zero_one_pack!
— MethodFor greedy algorithm, it will take the element based on the optimal value in the array at each loop in the function
This does 0-1 (each item can be chosen only once) knapsack : pack capacity = capacity weight of each item = weights value of each item = values
Each loop the function will find the highest value in the array and check if the capacity is enough to store it, if enough then the value will be added into the totalmaxvalue. After that the highest current value will be deleted.
julia> zero_one_pack!(20,[1,3,11],[2,5,30])
37