/ex_algo

Data Structures and Algorithms implemented with Elixir

Primary LanguageElixirMIT LicenseMIT

ExAlgo

ExAlgo is a collection of data structures and algorithms implemented in Elixir. This is the authors attempt to see algorithms through Elixir's lens.

The sole purpose of this is to use as a learning tool for algorithms in a functional language set-up. I am also thinking of using this to host some algorithms that could come in handy while solving Advent of Code. Almost all algorithms mentioned here have well tested and production ready libraries so I see little use that anyone would want to use this for anything serious.

Development

Download this repo and get the dependencies with mix deps.get. Go to iex -S mix to try out the algorithms in the REPL. mix test runs all the tests.

Detailed Documentation

TODO - Add ex_doc pages with detailed explanations of each categories.

Catalogue

Graph

Name Implementation Test Benchmark Link Note

Heap

Name Implementation Test Benchmark Link Note

List

Name Implementation Test Benchmark Link Note
Linked List linked_list.ex Yes No
Circular List circular_list.ex Yes No
BidirectionalList bidirectional_list.ex Yes No WIP
Maximum Subarray Sum algorithms.ex Yes No Kadane's Algorithm

Functional/Immutable

Name Implementation Test Benchmark Link Note

Queue

Name Implementation Test Benchmark Link Note
Queue queue.ex Yes No

Search

Name Implementation Test Benchmark Link Note
Binary Search binary_search.ex Yes No

Set

Name Implementation Test Benchmark Link Note
Disjoint Set disjoint_set.ex Yes No

Sort

Name Implementation Test Benchmark Link Note
Bubble Sort exchange.ex Yes No
Insertion Sort insertion.ex Yes No
Merge Sort merge.ex Yes No
Pigeonhole Sort distribution.ex Yes No
Quick Sort exchange.ex Yes No
Selection Sort selection.ex Yes No

Stack

Name Implementation Test Benchmark Link Note
Stack stack.ex Yes No
Min-Max Stack min_max_stack.ex Yes No

String

Name Implementation Test Benchmark Link Note

Tree

Name Implementation Test Benchmark Link Note
Binary Search Tree binary_search_tree.ex Yes No
Tree Traversals traversal.ex Yes No

Counting

Name Implementation Test Benchmark Link Note
Permutations combinatorics.ex::permutations Yes No Naive
Combinations combinatorics.ex::combinations Yes No Naive

Trie

Name Implementation Test Benchmark Link Note

Dynamic Programming

Name Implementation Test Benchmark Link Note
Subset Sum subset_sum.ex Yes No FIXME: Not all subsets are listed. Need to work on that.

Numbers

Name Implementation Test Benchmark Link Note
Chinese Remainder Theorem chinese_remainder.ex Yes No
Catalan Numbers (Recursive) catalan.ex::recursive Yes No
Catalan Numbers (Dynamic) catalan.ex::dp Yes No
Divisors arithmetics.ex::divisors Yes No