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.

Table of Contents

• Development
• Detailed Documentation
• Catalogue
  • Graph
  • Heap
  • List
  • Functional/Immutable
  • Queue
  • Search
  • Set
  • Sort
  • Stack
  • String
  • Tree
  • Counting
  • Trie
  • Dynamic Programming
  • Numbers

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.

Testing

• mix test - Run all tests
• mix coveralls - Run tests with coverage report
• mix coveralls.html - Generate HTML coverage report (opens in browser at cover/excoveralls.html)
• mix coveralls.detail - Show detailed coverage per file

Documentation

• mix docs - Generate documentation
• Documentation will be available at doc/index.html

Detailed Documentation

Comprehensive API documentation is available via ex_doc. After running mix docs, open doc/index.html in your browser to explore detailed documentation for all modules, including usage examples and type specifications.

Catalogue

Graph

Name	Implementation	Test	Benchmark	Link	Note

Heap

Name	Implementation	Test	Benchmark	Link	Note
Leftist Heap	leftist_heap.ex	Yes	No
Pairing Heap	pairing_heap.ex	Yes	No

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