TheAlgorithms

array-based binary search tree left tree values < root value < right tree values

array-based binary tree

BinaryHeap{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}: constructors
• push!(heap, elements...): push elements into the heap
• top(heap): get the top element (smaller in a MinHeap, greater in a MaxHeap)
• pop!(heap): get top element and remove it from the heap
• isempty(heap): wheter theres no elemets in the heap
• length(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

This can contain a maximum of length(par) parenting-relations par is an array of Int, which is the index of the parent node.

abs_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

abs_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

abs_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

area_circle(radius)

Finds area of the circle

Example

area_circle(20) # returns 1256.6370614359173
area_circle(-1) # returns DomainError

area_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

area_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

area_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

area_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

area_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

area_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

area_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

area_square(side)

Finds area of the area_square

Example

area_square(10) # returns 100
area_square(-1) # returns DomainError

area_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

area_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

encode(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

bab_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 for xn

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

binary_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

binary_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

caesar(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

ceil_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

celsiustofahrenheit(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

function 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

coin_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 available
• amount: 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:

• Gabriel Soares

This 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

This 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

count_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

Counting 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]

detect_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

determinant(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.

dijkstra(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 arcs
• source: 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

dna2rna(s::AbstractString)

Given: A DNA string t

having length at most 1000 nt.

Return: The transcribed RNA string of t

Sieve of Eratosthenes is an algorithm for finding all the primes upto a limit n.

Reference: -https://en.wikipedia.org/wiki/SieveofEratosthenes

euler_method(f, x0, span, h=1.0e-2)

Calculate the solution to a differential equation using forward euler 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

factorial_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

factorial_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

fahrenheittocelsius(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

fahrenheittokelvin(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

fcfs(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

Find the ancestor of node x.

floor_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

gauss_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

get_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 the dijkstra algorithm
• dest: path's destionation vertex

heap_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:

1. Building a (max) heap of the array
2. 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

idx_for(i::Int)

Simple helper function for converting 0-based indices to Julia's 1-based indices.

 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))

is_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 +....

isbefore(heap, x, y)

Whether x comes before y in the heap ordering.

ispangram(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

jump_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) )

function 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

function 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

krishnamurthy(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

line_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

linear_search(array, key)

A simple search of array, element per element until key is found.

lu_decompose(mat)

Decomposes a n x n non singular matrix into a lower triangular matrix (L) and an upper triangular matrix (U)

mean(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

median(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

mode(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

monte_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

• AugustoCL
• Ved Mahajan

partitions_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

• Vaishakh C R

perfect_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

perfect_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

perfect_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

prime_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

prime_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

rabin_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

riemann_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

A 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.

simpsons_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

sum_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

sum_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

surfarea_cube(side)

Finds surface area of a cube

Example

surfarea_cube(1)  # returns 6
surfarea_cube(3)  # returns 54
surfarea_cube(-1) # returns DomainError

surfarea_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

trapazoidal_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.

trapezoid_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

variance(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:

• Aru Bhardwaj

Verlet 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 equation
• x0 : 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 solution
• t is the array containing the time points

Reference:

• https://www.algorithm-archive.org/contents/verletintegration/verletintegration.html

Contributed by: Ved Mahajan

vol_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

vol_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

vol_cube()

Compute the volume of a cube.

Examples

julia> vol_cube(1)
1
julia> vol_cube(3)
27
julia> vol_cube(-1)
DomainError

vol_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

vol_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

vol_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

vol_right_circ_cone(radius, height)

Compute the Volume of a Right Circular Cone.

Examples

julia> vol_right_circ_cone(2, 3)
12.566370614359172

vol_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

wordcount(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

zero_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

For 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