TheAlgorithms

Basic

Basic algorthims for TheAlgorithms/Julia

prefix_sum(arr::Vector{<:Number})

Brief

Given an input array of numbers, return an array of the sum of each "prefix" of the input array i.e. the 1st element, 1st + 2nd element, 1st + 2nd + 3rd, etc.

This functionality is available in base Julia as cumsum.

Arguments

• arr: an array of numbers

Examples

julia> prefix_sum([1, 2, 3])
3-element Vector{Int64}:
 1
 3
 6

julia> prefix_sum([0.0, 10.0, π])
3-element Vector{Float64}:
  0.0
 10.0
 13.141592653589793

Difference array

Brief:

For any array A with N numbers, we can create difference array D with N numbers also.
Every k-th element of D is equal to difference between A[k] and A[k-1]
    D[k] = A[k-1] - A[k]

Complexity of some operations

- add some value x to the m consecutive elements of array - O(1)
- print array after any numbers of changes                - O(N)

Functions

- create_diff_arr(original::Array{<:Number})
    * Create difference array for array 'original'
- calculate_arr(diff_arr::Array{<:Number})
    * Recreate the original array from the given difference array
- add_to_arr(diff_arr::Array{<:Number}, l::Int, r::Int, x::Number)
    * Add x to all elements with index from [l, r]

Contributed by: Nikola Mircic

Cipher

Cipher algorithms.

affine(text, alphabet, nMultiply, nAdd)

Program to implement affine cipher for the given input. A full description of it can be found on wikipedia.

Arguments:

• text : text to be encoded/decoded
• alphabet : the alphaebt the text uses
• nMultiply : the number to the multiply by (a)
• nAdd : the number to add (b)

Examples/Tests

julia> affine("abcdefghijklmnopqrstuvwxyz", "abcdefghijklmnopqrstuvwxyz", 3, 1)
"behknqtwzcfiloruxadgjmpsvy"

julia> affine("whyhellothere", "abcdefghijklmnopqrstuvwxyz", 17, 82)
"otwtujjiptuhu"

julia> affine("1234", "0123456789", 5, 2)
"9630"

Algorithm:

As usual, julia's 1 based indexing doesn't play nicely with the affine cipher, but all that is required is -1 from the initial index of the letter and +1 after the mod.

An affine cipher uses a simple function: f(x) = ax + b.

Notes:

• nMultiply and length(alphabet) must be coprime so that the two plaintext letters are not substituted for the same cipehrtext letter.
• This doesn't check that the all of the characters in text actually are in alphabet, but that does need to be the case!

join([
    alphabet[((findfirst(isequal(letter), alphabet) - 1) * nMultiply + nAdd) % length(alphabet) + 1]
    for letter in text
])

References:

https://www.dcode.fr/affine-cipher https://github.com/Squalm/Cipher-Tools

Contributed by: Chirp (Squalm)

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

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

decrypt_vigenere(text, key)

Decrypts a plaintext message using the Vigenere cipher.

Arguments

• text: the ciphertext message to decrypt
• key: the keyword used for decryption

Examples

julia> decrypt_vigenere("Rijvs, Uyvjn!", "key")
Hello, World!

encrypt_vigenere(text, key)

Encrypts a plaintext message using the Vigenere cipher.

Arguments

• text: the plaintext message to encrypt
• key: the keyword used for encryption

Examples

julia> encrypt_vigenere("Hello, World!", "key")
Rijvs, Uyvjn!

Conversions

Conversions are conversions of measurements in Julia

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

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

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

DataStructure

DataStructure algorithms.

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.

Find the ancestor of node x.

isbefore(heap, x, y)

Whether x comes before y in the heap ordering.

Linked List

Brief:

A linked list is a data structure where each element is connected to the next one.

Complexity of some operations

- insert            - O(N)
- insert to front   - O(1)
- delete            - O(N)
- delete first      - O(1)
- get element       - O(N)

Functions

- create_node(val, next=missing) - Create node with value 'val' and the pointer to the next node ( missing by default ) 
- create_list(n::Int=0, val=missing) - Create root node of the list with n elements with value set to 'val'
- insert(list::Node, new_node::Node, index::Int=1) - Add a new node to the list at the specified index
- insert(list::Node, val, index::Int=1) - Create a new node with value 'val' in the list at the specified index
- push_back(list::Node, node::Node) - Add a new node to the end of the list
- push_back(list::Node, val) - Add a new node with value 'val' to the end of the list
- return_as_array(list::Node) - Return the array representation of the list
- clear(list::Node) - Remove all elements from the list
- remove(list::Node, index::Int) - Remove an element at the specified index
- remove_all(list::Node, val) Remove all elements with the value 'val'
- remove_first(list::Node, val) - Remove the first element in the list with value 'val'
- get_node(list::Node, index::Int) - Get a node at the specified index
- get(list::Node, index::Int) - Get a value from the node at the specified index
- indexOf(list::Node, val) - Return the index of the first element with a value 'val'
- is_empty(list) - Return true if list is empty, false if it has elements

Contributed by: Nikola Mircic

This function changes the tree to correspond to an array after adding k to the element at index x

Arguments

- tree::Array{T} - A Fenwick tree for an array
- x::Integer - Index of the changed element
- k::Integer - An integer added to the element arr[x]

This is a function for generating the tree from the given array of numbers.

Arguments

- arr::Array{T} : An array of numbers.

Returns

- A Fenwick tree for the given array

This is a function that returns the sum of the first x elements

Arguments

- tree::Array{T} - A Fenwick tree for an array
- x::Integer - The number of the elements

Create a original array from the given tree

Arguments

- tree::Array{T} - an binary index tree which is used for calculating the original array

DynamicProgramming

DynamicProgramming algorithms in Julia.

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

Graph

Graph related algorithms in Julia.

bellman_ford(graph::Vector{Tuple{Int, Int, Int}}, source::Int)

The Bellman-Ford algorithm is an algorithm which computes the shortest paths from a single source vertex to all other vertices in a weighted graph. It is slower than Dijkstra's algorithm, which solves the same problem, but it is capable of handling graphs with negative edge weights. Instead of greedily performing the relaxation on the vertices, Bellman-Ford simply relaxes all edges, and does this |V|-1 times.

Arguments:

• graph: a directed, weighted graph
• source: the source vertex from which to begin the traversal

Example

graph = [
    (1, 2, 4), (1, 3, 2),
    (2, 3, 3), (2, 4, 2), (2, 5, 3),
    (3, 2, 1), (3, 4, 4), (3, 5, 5),
    (5, 4, -5)
]
bellman_ford(graph, 1)

# output

5-element Vector{Int64}:
 0
 3
 2
 1
 6

Contributed by: Yannick Brenning

bfs(graph:Vector{Vector{Int}}, source::Int = 1)

Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at a given vertex and explores all vertices at the present depth before moving to the next "level". This implementation is for educational purposes only, so it simply prints out the vertices in the order that they were traversed.

Arguments:

• graph: a directed, unweighted graph
• source: the source vertex from which to begin the traversal

Example

graph = [
    [2, 3, 6], 
    [3, 4],
    [4],
    [1, 2, 5],
    [2],
    [1, 5]
]
TheAlgorithms.Graph.bfs(graph, 4)

# output

6-element Vector{Int64}:
 4
 1
 2
 5
 3
 6

Contributed by: Yannick Brenning

dfs(graph::Vector{Vector{Int}}, source::Int)

Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at a given vertex and explores as far as possible along each branch before backtracking. This implementation is for educational purposes only, so it simply prints out the vertices in the order that they were traversed.

Arguments:

• graph: a directed, unweighted graph
• source: the source vertex from which to begin the traversal

Example

graph = [
    [2, 3, 6], 
    [3, 4],
    [4],
    [1, 2, 5],
    [2],
    [1, 5]
]
dfs(graph, 6)

# output

6-element Vector{Int64}:
 6
 5
 2
 4
 3
 1

Contributed by: Yannick Brenning

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

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

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

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

LongSubSeq

LongSubSeq for longest increasing subsequence algorithms.

Math

Math algorithms.

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

aliquot_sum(n::Int)

The aliquot sum of a positive integer n is the sum of all the proper divisors of n, i.e, all divisors of n other than n itself.

Input parameters:

• n : The number to find the aliquot sum of.

Examples/Tests:

aliquot_sum(6)      # returns 6
aliquot_sum(10)     # returns 8
aliquot_sum(1345)   # returns 275
aliquot_sum(-1)     # throws DomainError

Reference

• https://en.wikipedia.org/wiki/Aliquot_sum

Contributed by: Praneeth Jain

amicable_pairs(n::Int)

Two unique natural numbers are said to form an amicable pair when them sum of proper divisors of each is equal to the other number.

Input parameters:

• n : Finds amicable pairs below n.

Examples/Tests:

amicable_pairs(10)      # returns []
amicable_pairs(400)     # returns [220 => 284]
amicable_pairs(2000)    # returns [220 => 284, 1184 => 1210]
amicable_pairs(-1)      # throws DomainError

Reference

• https://mathworld.wolfram.com/AmicablePair.html

Contributed by Praneeth Jain

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

average_absolute_deviation(numbers)

The average absolute deviation of a data set is the average of the absolute deviations from the mean. It is a measure of statistical dispersion or variability.

Input parameters:

• numbers : The numbers to find the average absolute deviation of.

Examples/Tests:

average_absolute_deviation([1, 2, 3, 4, 5])     # returns 1.2
average_absolute_deviation([0])                 # returns 0.0
average_absolute_deviation([5.5, 64.3, 100.4])  # returns 34.16

Reference

• https://mathworld.wolfram.com/AverageAbsoluteDeviation.html

Contributed by Praneeth Jain

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

bin_length(binNum)

Returns the length of binNum's binary representation.

Input parameters:

• binNum : The number to find the binary length of.

Examples/Tests:

bin_length(1)       # returns 1
bin_length(2)       # returns 2
bin_length(3)       # returns 2
bin_length(4)       # returns 3
bin_length(5)       # returns 3
bin_length(12)      # returns 4
bin_length(256)     # returns 9
bin_length(1024)    # returns 11
bin_length(-1)      # throws DomainError

Contributed by: Praneeth Jain

This algorithm features use of the OEIS entry A070939 - length of Binary Representation of n. It finds the length of any binary number and returns said length.

https://oeis.org/A070939

This function, as believed, is O(n)

The idea follows that the sequence is dependent on a repeating pattern of 2. Short for sequence, seq is the number of digits required before an increase in finNum or final number as seen here with the first few iterations - i on the left, final number on the right:

1 : 1 2 : 2 3 : 2 4 : 3 5 : 3 6 : 3 7 : 3 8 : 4 cont.

As you can see, for every version of i, there is an appropriate modified number that only repeats for the sequence of the last doubled amount.

#Contributions: Contributed by F35H: https://github.com/F35H

This algorithm features use of the OEIS entry A070939 - length of Binary Representation of n. It finds the length of any binary number and returns said length.

https://oeis.org/A070939

This function, as believed, is O(log(n))

The idea follows that the sequence is dependent on a repeating pattern of 2. The final number being finNum increases on every doubling of i.

1 : 1 2 : 2 3 : 2 4 : 3 5 : 3 6 : 3 7 : 3 8 : 4 cont.

As you can see, for every version of i, there is an appropriate final number that iterates on every doubling of i.

Contributors:

• F45H

catalan(n::Int)

In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects.

Input parameters:

• n : index of the catalan number.

Examples/Tests:

catalan(0)  # returns 1
catalan(3)  # returns 5
catalan(8)  # returns 1430
catalan(-1) # throws DomainError

Reference

• https://mathworld.wolfram.com/CatalanNumber.html

Contributed by: Praneeth Jain

ceil(x)

Finds the ceiling of x as an functionInteger

Example

ceil(1.3)   # 2.0
ceil(2.0)   # returns 2.0
ceil(-1.5)  #returns -1.0

Reference

• https://en.wikipedia.org/wiki/Floorandceiling_functions

Contributed By:- Ashwani Rathee

divisors(n::Int)

Returns the divisors of n as a vector.

Input parameters:

• n : The number to find the factors of.

Examples/Tests:

divisors(6)     # returns [1, 2, 3, 6]
divisors(10)    # returns [1, 2, 5, 10]
divisors(1345)  # returns [1, 5, 269, 1345]
divisors(-1)    # throws DomainError

Reference

• https://mathworld.wolfram.com/Divisor.html

Contributed by: Praneeth Jain

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.

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

fib_iterative(n::Int)

Finds the first n fibonacci number using iterative method.

Arguments:

• n : Number of fibonacci numbers required

Examples/Tests

fib_iterative(1)    # returns [0]
fib_iterative(2)    # returns [0, 1]
fib_iterative(6)    # returns [0, 1, 1, 2, 3, 5]
fib_iterative(10)   # returns [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
fib_iterative(-1)   # throws DomainError

Reference

• https://mathworld.wolfram.com/FibonacciNumber.html

Contributed by Praneeth Jain

fib_recursive(n::Int)

Finds the first n fibonacci number using recursive method.

Arguments:

• n : Number of fibonacci numbers required

Examples/Tests

fib_recursive(1)    # returns [0]
fib_recursive(2)    # returns [0, 1]
fib_recursive(6)    # returns [0, 1, 1, 2, 3, 5]
fib_recursive(10)   # returns [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
fib_recursive(-1)   # throws DomainError

Reference

• https://mathworld.wolfram.com/FibonacciNumber.html

Contributed by Praneeth Jain

fib_recursive_memo(n::Int)

Finds the first n fibonacci number using recursive method and memoization.

Arguments:

• n : Number of fibonacci numbers required

Examples/Tests

fib_recursive_memo(1)    # returns [0]
fib_recursive_memo(2)    # returns [0, 1]
fib_recursive_memo(6)    # returns [0, 1, 1, 2, 3, 5]
fib_recursive_memo(10)   # returns [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
fib_recursive_memo(-1)   # throws DomainError

Reference

• https://mathworld.wolfram.com/FibonacciNumber.html

Contributed by Praneeth Jain

floor(x)

Finds the floor of x as an Integer

Example

floor(1.3)  # 1
floor(2.0)  # returns 2.0
floor(-1.7) # returns -2.0

Reference

• https://en.wikipedia.org/wiki/Floorandceiling_functions

Contributed By:- Ashwani Rathee

get_mersenne_primes(n::Int)

A mersenne prime is a prime number that is one less than a power of 2. Returns a list of mersenne primes upto n.

Input parameters:

• n : The limit upto which mersenne primes are to be generated.

Examples/Tests:

get_mersenne_primes(100)    # returns [3, 7, 31]
get_mersenne_primes(1000)   # returns [3, 7, 31, 127]
get_mersenne_primes(10000)  # returns [3, 7, 31, 127, 8191]

Reference

• https://mathworld.wolfram.com/MersennePrime.html

Contributed by Praneeth Jain

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

is_mersenne_prime(n::Int)

A mersenne prime is a prime number that is one less than a power of 2. Checks whether the given integer is a mersenne prime.

Input parameters:

• n : The number to be checked.

Examples/Tests:

is_mersenne_prime(3)     # returns true
is_mersenne_prime(15)    # returns false
is_mersenne_prime(8191)  # returns true

Reference

• https://mathworld.wolfram.com/MersennePrime.html

Contributed by Praneeth Jain

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

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

num_divisors(n::Int)

Efficiently finds the number of divisors of n.

Input parameters:

• n : The number to find the number of divisors of.

Examples/Tests:

num_divisors(1)       # returns 1
num_divisors(13)      # returns 2
num_divisors(420)     # returns 24
num_divisors(1345)    # returns 4
num_divisors(-1)      # throws DomainError

Reference

• https://cp-algorithms.com/algebra/divisors.html#number-of-divisors

Contributed by: Praneeth Jain

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

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

runge_kutta_integration(f::Function, x0::Real, y0::Real, h::Real, x_stop::Real)

Numerically solve initial value problems of the form $y' = f(x, y)$ to find $y(x)$ using the Runge-Kutta 4th order integration scheme.

Starting with the differential equation $\frac{\mathrm{d}y}{\mathrm{d}x} = y' = f(x, y)$ and the initial condition $y(x_0) = y_0$, each step calculates 4 approximations of the gradient

\[\begin{align*} k_1 &= f(x_n, y_n),\\ k_2 &= f(x_n + \frac{h}{2}, y_n + k_1\frac{h}{2}),\\ k_3 &= f(x_n + \frac{h}{2}, y_n + k_2\frac{h}{2}),\\ k_4 &= f(x_n + h, y_n + k_3h), \end{align*}\]

and uses the weighted average of them,

\[\bar{k} = \frac{k_1 + 2k_2 + 2k_3 + k_4}{6},\]

to find the approximate value of $y(x_{n+1})$ and update $x$ and $y$ accordingly

\[\begin{align*} x &\rightarrow x_{n+1} = x_n + h\\ y &\rightarrow y_{n+1} = y_n + h\bar{k}. \end{align*}\]

Arguments:

• f: The function $y' = f(x, y)$ to solve for $y(x)$.
• x0: The starting value of x.
• y0: The starting value of y.
• h: The step size, should be >0.
• x_stop: The final value of x to solve to, i.e. integrate over the range [x0, x_stop]

Examples

julia> # If you have a constant slope of y' = 1, the analytic solution is y = x
julia> runge_kutta_integration((x, y)->1, 0, 0, 1, 3)
([0.0, 1.0, 2.0, 3.0], [0.0, 1.0, 2.0, 3.0])

julia> # Consider solving y' = exp(x), which has the analytic solution y = exp(x).
julia> runge_kutta_integration((x, y)->exp(x), 0, 1., 0.1, 0.1)
([0.0, 0.1], [1.0, 1.105170921726329])

julia> exp.([0.0, 0.1])
2-element Vector{Float64}:
 1.0
 1.1051709180756477

References

• https://en.wikipedia.org/wiki/Initialvalueproblem
• https://en.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods

Contributors:

• E-W-Jones

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_divisors(n::Int)

Returns the sum of the divisors of n.

Input parameters:

• n : The number to find the sum of divisors of.

Examples/Tests:

sum_divisors(6)     # returns 12
sum_divisors(10)    # returns 18
sum_divisors(1345)  # returns 1620
sum_divisors(-1)    # throws DomainError

Reference

• https://mathworld.wolfram.com/Divisor.html

Contributed by: Praneeth Jain

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_cuboid(length, width, height)

Finds surface area of a cuboid

Example

surfarea_cuboid(5, 5, 5)  # returns 150
surfarea_cuboid(-5, -5, -5)  # 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

totient(n::Int)

The totient function phi(n) is defined as the number of positive integers <=n that are relatively prime to n. Since a number less than or equal to and relatively prime to a given number is called a totative, the totient function phi(n) can be simply defined as the number of totatives of n.

Input parameters:

• n : The number to find the totient of.

Examples/Tests:

totient(1) # returns 1
totient(2) # returns 1
totient(3) # returns 2
totient(10) # returns 4
totient(24) # returns 8
totient(50) # returns 20
totient(-1) # throws DomainError

Reference

• https://mathworld.wolfram.com/TotientFunction.html

Contributed by Praneeth Jain

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

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

MatrixAlgo

MatrixAlgo for matrix algorithms.

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.

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

lu_decompose(mat)

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

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.

ProjectEuler

ProjectEuler naive solutions in Julia.

aliquot_sum(n::Int)

The aliquot sum of a positive integer n is the sum of all the proper divisors of n, i.e, all divisors of n other than n itself.

Input parameters:

• n : The number to find the aliquot sum of.

Examples/Tests:

aliquot_sum(6)      # returns 6
aliquot_sum(10)     # returns 8
aliquot_sum(1345)   # returns 275
aliquot_sum(-1)     # throws DomainError

Reference

• https://en.wikipedia.org/wiki/Aliquot_sum

Contributed by: Praneeth Jain

divisors(n::Int)

Returns the divisors of n as a vector.

Input parameters:

• n : The number to find the factors of.

Examples/Tests:

divisors(6)     # returns [1, 2, 3, 6]
divisors(10)    # returns [1, 2, 5, 10]
divisors(1345)  # returns [1, 5, 269, 1345]
divisors(-1)    # throws DomainError

Reference

• https://mathworld.wolfram.com/Divisor.html

Contributed by: Praneeth Jain

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

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

num_divisors(n::Int)

Efficiently finds the number of divisors of n.

Input parameters:

• n : The number to find the number of divisors of.

Examples/Tests:

num_divisors(1)       # returns 1
num_divisors(13)      # returns 2
num_divisors(420)     # returns 24
num_divisors(1345)    # returns 4
num_divisors(-1)      # throws DomainError

Reference

• https://cp-algorithms.com/algebra/divisors.html#number-of-divisors

Contributed by: Praneeth Jain

Multiples of 3 or 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Input parameters:

• limit : Upper limit for the numbers.

Examples/Tests:

problem_001(10)     # returns 23
problem_001(1000)   # returns 233168
problem_001(-1)     # throws DomainError

Reference

• https://projecteuler.net/problem=1

Contributed by: Praneeth Jain

Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Input parameters:

• limit : Upper limit for the numbers.

Examples/Tests:

problem_002(10)         # returns 10
problem_002(4_000_000)  # returns 4613732
problem_002(-1)         # throws DomainError

Reference

• https://projecteuler.net/problem=2

Contributed by: Praneeth Jain

Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Input parameters:

• number : Number to find the largest prime factor of.

Examples/Tests:

problem_003(17)             # returns 17
problem_003(13195)          # returns 29
problem_003(600851475143)   # returns 6857
problem_003(-1)             # throws DomainError

Reference

• https://projecteuler.net/problem=3

Contributed by: Praneeth Jain

Largest palindrome product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Examples/Tests:

problem_004()   # returns 906609

Reference

• https://projecteuler.net/problem=4

Contributed by: Praneeth Jain

Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Input parameters:

• limit: Limit upto which to find the smallest multiple.

Examples/Tests:

problem_005(10) # returns 2520
problem_005(20) # returns 232792560
problem_005(-1) # throws DomainError

Reference

• https://projecteuler.net/problem=5

Contributed by: Praneeth Jain

Sum square difference

The sum of the squares of the first ten natural numbers is, 1^2 + 2^2 + ... + 10^2 = 385

The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)^2 = 55^2 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640. Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Input parameters:

• n : limit upto which to find the sum square difference.

Examples/Tests:

problem_006(10)     # returns 2640
problem_006(100)    # returns 25164150
problem_006(-1)     # throws DomainError

Reference

• https://projecteuler.net/problem=6

Contributed by: Praneeth Jain

10001st prime

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

Input parameters:

• n : Will find the nth prime.

Examples/Tests:

problem_007(1)      # returns 2
problem_007(6)      # returns 13
problem_007(10001)  # returns 104743
problem_007(-1)     # throws DomainError

Reference

• https://projecteuler.net/problem=7

Contributed by: Praneeth Jain

Largest product in a series

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Input parameters:

• num_str : The number to find the greatest product in, in string form.
• n : Number of consecutive numbers to find the product of.

Examples/Tests:

num_str = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
problem_008("1234", 2)      # returns 12
problem_008(num_str, 4)     # returns 5832    
problem_008(num_str, 13)    # returns 23514624000
problem_008("12345", 6)     # throws DomainError

Reference

• https://projecteuler.net/problem=8

Contributed by: Praneeth Jain

Special Pythagorean triplet

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

Examples/Tests:

problem_009()   # returns 31875000

Reference

• https://projecteuler.net/problem=9
• https://en.wikipedia.org/wiki/Pythagoreantriple#Generatinga_triple

Contributed by: Praneeth Jain

Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Input parameters:

• n : Upper limit of primes.

Examples/Tests:

problem_010(1)          # returns 0
problem_010(10)         # returns 17
problem_010(2000000)    # returns 142913828922
problem_010(-1)         # throws DomainError

Reference

• https://projecteuler.net/problem=10

Contributed by: Praneeth Jain

Highly Divisible Triangular Number

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1+2+3+4+5+6+7 = 28. The first ten terms would be 1,3,6,10,15,21,28,36,45,55,... What is the value of the first triangle number to have over 500 divisors?

Input parameters:

• n : the triangle number must have over n divisors.

Examples/Tests:

problem_012(5)          # returns 28
problem_012(333)        # returns 17907120
problem_012(500)        # returns 76576500
problem_012(-1)         # throws DomainError

Reference

• https://projecteuler.net/problem=12

Contributed by: Praneeth Jain

Large Sum

Work out the first ten digits of the sum of the given one-hundred 50-digit numbers.

Examples/Tests:

problem_013()   # returns "5537376230"

Reference

• https://projecteuler.net/problem=13

Contributed by: Praneeth Jain

Longest Collatz Sequence

The following iterative sequence is defined for the set of positive integers: n -> n/2 (n is even) n -> 3n+1 (n is odd) Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain?

Input parameters:

• n : upper bound on the starting number

Examples/Tests:

problem_014(10)         # returns 9
problem_014(250)        # returns 231
problem_014(1000000)    # returns 837799
problem_014(-1)         # throws DomainError

Reference

• https://projecteuler.net/problem=14

Contributed by: Praneeth Jain

Lattice Paths

Starting in the top left corner of a grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a 20 x 20 grid? grid?

Input parameters:

• n : number of rows in the grid
• m : number of columns in the grid

Examples/Tests:

problem_015(2, 2)       # returns 6
problem_015(5, 3)       # returns 56
problem_015(20, 20)     # returns 137846528820
problem_015(0, 5)       # throws DomainError
problem_015(-3, 0)      # throws DomainError

Reference

• https://projecteuler.net/problem=15

Contributed by: Praneeth Jain

Power Digit Sum

2^15 = 32768 and the sum of its digits is 3+2+7+6+8=26. What is the sum of the digits of the number 2^1000? grid?

Input parameters:

• a : base
• n : exponent

Examples/Tests:

problem_016(1, 1)       # returns 1
problem_016(2, 15)      # returns 26
problem_016(2, 1000)    # returns 1366
problem_016(2, -4)      # throws DomainError

Reference

• https://projecteuler.net/problem=16

Contributed by: Praneeth Jain

Number Letter Counts

If the numbers 1 to 5 are written out in words, then there are 3+3+5+4+4=19 letters used in total. If all the numbers from 1 to 1000 inclusive were written out in words, how many letters would be used?

Examples/Tests:

problem_017()       # returns 21124

Reference

• https://projecteuler.net/problem=17

Contributed by: Praneeth Jain

Maximum Path Sum I

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

    3
   7 4
  2 4 6
 8 5 9 3

Find the maximum total from top to bottom of the triangle below.

Examples/Tests:

problem_018()       # returns 1074

Reference

• https://projecteuler.net/problem=18

Contributed by: Praneeth Jain

Counting Sundays

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Input parameters:

• start_year : start from 1st January of start_year
• end_year : check till 31st December of end_year

Examples/Tests:

problem_019(1901, 2000)     # returns 171
problem_019(1901, 2200)     # returns 515
problem_019(2020, 2023)     # returns 6
problem_019(-1, 2023)       # throws DomainError

Reference

• https://projecteuler.net/problem=19

Contributed by: Praneeth Jain

Factorial Digit Sum

Find the sum of the digits in the number 100!.

Input parameters:

• n : number to find sum of digits of factorial of

Examples/Tests:

problem_020(10)     # returns 27
problem_020(37)     # returns 153
problem_020(100)    # returns 648
problem_020(-1)     # throws DomainError

Reference

• https://projecteuler.net/problem=20

Contributed by: Praneeth Jain

sum_divisors(n::Int)

Returns the sum of the divisors of n.

Input parameters:

• n : The number to find the sum of divisors of.

Examples/Tests:

sum_divisors(6)     # returns 12
sum_divisors(10)    # returns 18
sum_divisors(1345)  # returns 1620
sum_divisors(-1)    # throws DomainError

Reference

• https://mathworld.wolfram.com/Divisor.html

Contributed by: Praneeth Jain

Zeller's Congruence

Given a date, returns the day of the week

0 => Sunday 1 => Monday, 2 => Tuesday, ... , 6 => Saturday

Input parameters:

• day : day of the month
• month : month of the year (1 indexed)
• year : year

Reference

• https://en.wikipedia.org/wiki/Zeller%27s_congruence

ProjectRosalind

ProjectRosalind naive solutions and algorithms.

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

dna2rna(s::AbstractString)

Given: A DNA string t

having length at most 1000 nt.

Return: The transcribed RNA string of t

Scheduling

Scheduling algorithms in Julia.

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

Searches

Searches - search algorithms.

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

 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

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

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

linear_search(array, key)

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

Sorts

Sorts are sorting algorithms in Julia.

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]

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.

StatAlgo

StatAlgo in Julia

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

StringAlgo

StringAlgo in Julia.

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

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

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

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