algorithm-archivists/algorithm-archive

A collaborative book on algorithms

The Arcane Algorithm Archive

The Arcane Algorithm Archive is a collaborative effort to create a guide for all important algorithms in all languages. This goal is obviously too ambitious for a book of any size, but it is a great project to learn from and work on and will hopefully become an incredible resource for programmers in the future.

To change the language, please use the UI at the top of the site:

Here are some essential links:

• Book / website: https://www.algorithm-archive.org/
• GitHub repository: https://github.com/algorithm-archivists/algorithm-archive
• YouTube channel (LeiosOS): https://www.youtube.com/user/LeiosOS
• Twitch livestream: https://www.twitch.tv/leioslabs
• Discord server: https://discord.gg/Pr2E9S6

Note that this project is essentially a book about algorithms collaboratively written by an online community. Fortunately, there are a lot of algorithms out there, which means that there is a lot of content material available. Unfortunately, this means that we will probably never cover every algorithm ever created and instead need to focus on what the community sees as useful and necessary. That said, we'll still cover a few algorithms for fun that have very little, if any practical purpose.

If you would like to contribute, feel free to go to any chapter with code associated with it and implement that algorithm in your favorite language, and then submit the code via pull request. You can find help and instructions regarding the contribution process in our How to Contribute wiki entry.

Hopefully, this project will grow and allow individuals to learn about and try their hand at implementing different algorithms for fun and (potentially) useful projects. If nothing else, it will be an enjoyable adventure for our community.

Thanks for reading and let me know if there's anything wrong or if you want to see something implemented in the future!

---

License

The code examples for this project are licensed under the MIT license (found in LICENSE.md). All text content is licensed under the Creative Commons Attribution-ShareAlike 4.0 International License with attribution specified at the end of every chapter. All graphics are licensed under the license stated at the end of every chapter. If no attribution is specified, please attribute James Schloss.

algorithm-archive's Issues

Chapter submissions and planned revision

Hey Guys,

I plan a large overhaul of the AAA in November, meaning that almost all chapters will be majorly changed and hopefully upgraded in terms of quality. During this process, the code should not change too much; however, I will need to update any chapter that is merged into the AAA before then. This includes chapters that I have not actually written (#163, #216, #278, #346, #358). By this, I mean that if these chapters are merged before the revision, they will need to be updated in the revision process.

I'm honestly not sure the best way to proceed here, but I believe the best option is to put chapter PR's on hold until the quality of the AAA improves and we have a set standard to work from.

Right now, I strongly feel that the AAA is lacking in quality in most cases. This is not okay and it is my fault. I need to fix it before the AAA gets too big. That said, I apologize for all the unnecessary work put into those PR's so far. They will be merged eventually, but I feel we should wait until after a new standard of quality has been created for the AAA.

I am definitely up for discussion here.

Here is a link to a list that will be updated soon: https://docs.google.com/spreadsheets/d/1TAHkVG5FyvXKyBQVPRO54ZpVcM5kUm9KhKH9LhTVP9I/edit?usp=sharing

Book Corrections - Complexity Notation & Euclidean Algorithm

While reading through the leading chapters of the book on https://www.algorithm-archive.org/ (august 10'th, 2018) I found some sections/descriptions which felt incomplete, and thought I might give my feedback.

Complexity Notation:

• It is unclear what is seen as an operation. It assumed that the operation initially is seen as the array-lookup, and not the print statement.

• In example two the operations are conditional to the length of the array which is unnecessary for the point of the example.

• In the second example of 'Linear Time', the explicit runtime is said to be Theta(3n/2+2) but again it is ambiguous as to what counts as an operation. If it is focused on array-lookup as well as the addition operation, the time would instead be Theta(5n/2+2), assuming we ignore the println statement of the independent string. To further state this argument, the multiplication and addition of the array index would also be calculated separately before the array-lookup, as well as printing the independent string, making the explicit runtime Theta(10n/2+3).

• The chapter nicely grasps the concept of complexity notation, but does not describe how O and Omega are the upper and lower bound of Theta very well. This could be clear with an example also.

• The exponential example has no terminating condition, causing stackoverflow independent of parameters.

• The logarithmic example is not logarithmic, as both branches are explored.

Euclidean Algorithm:

• the euclid_mod and euclid_sub examples are swapped in the text.

Code selection overlaps with chapter text on mobile

The code selection overlaps with the text of the current chapter on mobile.

iOS - Safari - iPhone SE:

Firefox - Samsung Galaxy S7 - Mac:

Non-rigorous style [text]

I need to get better with mathematical rigor. If you see anything that you think should be more rigorous, let me know.

In addition, I think the colloquial style I have been using is a little too colloquial.

I will address both of these in the next revision cycle.

Improving implementations for Verlet Integration

1. Printing inside the individual functions vs. printing in main

Some of the code examples print the results directly inside the verlet function. Others have the functions return the results and print them in main.

With #243, we're already steering in the direction of printing in main instead of the individual functions. To keep everything in line, we should do this in every example.

2. Using the velocity variable in Stormer-Verlet

Currently, the chapter about Verlet Integration includes code examples for the Stormer-Verlet and Velocity-Verlet methods. Both of them have a velocity term, but it's completely unused in Stormer-Verlet. The variable is assigned a value which is never actually used. In #256, @leios and I already agreed that it would be an improvement to also print the velocity. I want to leave this up for discussion before we decide on it.

I think that if we print the velocity for Stormer-Verlet, we should also print it for Velocity-Verlet.

Progress

If we were to change these 2 things, these are the languages examples that would need adjustment:

• C (#298)
• C++ (both)
• Java (#290)
• JavaScript (print velocity)
• Julia (both)
• Python (#256)
• Rust (#297)

Feel free to post your opinion on the second topic and to submit PRs for the listed languages. I will keep this list updated as the code comes in.

Let's decide on how to indent JSON files

During the latest pull request adventures, we had to add a few new languages to book.json. I noticed that the file is indented with tabs and we don't have an EditorConfig rule to reflect that. Some editors seem to indent JSON with spaces and that's why people could submit book.json edits with inconsistent indentation.

We have 3 options:

1. Keep tab indentation for book.json and make it a project-wide rule
2. Keep tab indentation for book.json as an exception and make space indentation the norm
3. Convert book.json to space indentation and make it a project-wide rule

What do you think? I personally lean towards 3.

Implementing translations

Do you think that it's possible and useful to translate the book or some chapters ?
If so, how could we do that ?

Journal of Open Source Education publication?

Hey, I have recently been made aware of a new journal, the Journal of Open Source Education (JOSE). It is similar to the Journal of Open Source Software (JOSS) in that the code, itself, is the publication. We simply need to provide a one-page intro to the project (which I should have no trouble writing on my own). I am considering publishing the Algorithm Archive in JOSE because it provides a citable reference so people can use the Algorithm Archive in their own projects.

To be clear: publishing the Algorithm Archive in JOSE does not restrict us from printing a version and publishing in that way later on.

I am curious to hear what you guys think:

1. Is publishing in JOSE a good idea? Why or why not?
2. If we do publish in JOSE, how do we determine who is on the author list?
3. Are there better places to publish the AAA? Should we just wait for a physical copy?

The way I see it, the most up-to-date version of the AAA will always be online, so it makes sense to have a citable online reference. If we do decide to submit to JOSE, there is a lot I would like to do before-hand... so there is time to discuss.

Ordering of languages is inconsistant

It's a bit confusing currently to read which languages each example is in. For example C# is the first language on the Jarvis march page while C is the fourth. It'd probably be good to come up with a consistent ordering of languages, probably ordering the tabs alphabetically?

Monte Carlo Percent Error

The percent error can be displayed in two different ways:

• Way 1: Having a positive or negative percent error depending on the estimate we have.
• Way 2: Always having a positive value by just taking the absolute.

The two ways would be calculated like the following:

• Way 1: percent error = [experimental value - theoretical value] / theoretical value x 100%
• Way 2: percent error = (AbsoluteOf([experimental value - theoretical value])) / theoretical value x 100%

We now have the following state for the Monte Carlo implementations of the AAA:

• Some implementations are using Way 2 of the percent error and just provide an always positive number. The following languages are using way 2: Clojure, D, Go, Haskell, Python, R
• And some other languages are using Way 1, but making a mistake by doing so, they aer using the following calculation: [theoretical value - experimental value] / theoretical value x 100% instead of [experimental value - theoretical value] / theoretical value x 100% The following languages are using way 1 incorrectly: C, Java, JavaScript, Julia, Rust, Swift

So the question is now: Should we use way 1 or way 2 in the AAA?

I vote for way 1 because it provides some nice additional information, i.e.:
Having a theoretical value of 3 would result in a negative percentage and having a theoretical value of 3.5 would result in a positive percentage. With way 2 it would be a positive percentage in both cases.

Progress Tracker - Way 2

Since we decided for way 2, the following to do list, shows which implementations need to be updated:

• Julia // Done: #325
• Swift // Done: #328
• Java // Done: #371
• JavaScript // Done: #372
• C // Done: #374
• Rust // #381

Julia code in FFT chapter

In the butterfly diagram were written
b0=a0+ω02a1
b1=a0−ω02a1

and from what I understand b_k=a(even)+w*a(odd)
but at the end of julia code in cooley_tukey function it says:

vcat(x_odd + x_even .* factor[1:half],
x_odd - x_even .* factor[1:half])

I checked with wikipedia and other languages in this book that I understand and it is even indices plus omega*odd indices

Convolution edge cases

Convolution is presented as an infinte sum over all indices, but for a finite input list this needs to be bounded. The question becomes what the function is assumed to be outside its definition range. The hand-written (Julia) code assumes the function to be zero outside its definition, while the FFT assumes it to be periodic. I'm pretty confident that the provided conv-function and conv_fft will give different output results, even if it is presented as they should produce the same. I say "pretty sure" because I had a hard time getting it to run and I am not a native Julia speaker.

Problem with Git

Hey guys,

I'm a beginner with Git and I red this tutorial : https://github.com/johhnry/algorithm-archive/blob/master/chapters/principles_of_code/version_control.md

I succeeded installing git and cloning the algorithm-archive repository localy.

But it seems really confusing to me, I have an error with the command :

git push remote master

fatal: remote does not appear to be a git repository
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

I would like to submit algorithms in C / Python and Processing to help the community.

Thanks in advance

Joseph

Unifying algorithms and examples (code)

Hey,

when I was looking through code examples, I noticed, each implementation is different from each other. Which is expected in some way. But we should try to unify things like:

• input values
• printed output
• naming of functions - where possible

When you change from one language to another, it's sometimes hard to understand what that algorithm does.

Example: Monte Carlo
Java implemented everything as static functions with sample size 1000.
JS is functions, which is fine (JS versioning is different topic) with sample size 100000000.
Swift is mix of objects/functions (can't say if good/bad, I don't know Swift) with sample size 10000.
@julianschacher is making C# implentation which uses OOP and looks good. So it could be example for OOP languages implementation.

You may agree with me or not, I can be wrong in this, but it's worth discussion.

extra term in FFT

hello @leios , I have been reading FFT and the step where using e2πiθ=cos(2πθ)+isin(2πθ) (line 41)
to change f(x)=∫∞−∞F(ξ)e2πiξxdξ (line 19)
to f(x)=∫∞−∞F(ξ)(cos(2πξx)+isin(2πξx))e2πiξxdξ (line 49)

seems off, especially the extra e2πiξx at the end (line 49)

Example Code at Forward Euler

Hey all!

The book states that the Example Code should estimate the abstract equation y' = 5y for y. But the implemented code is, as far as I saw it, the estimation of the previous named function y' = -3t with y(0) = 1.

However we should remove the text of the Code Example then.

All the best,

depate

Should we be able to "link" other code?

For example, in convolutions, the FFT code is out of date. Should we be able to link in other code? Preferably with checks for when the API breaks?

Unintuitive Directory Scheme

Currently, the Algorithm Archive is divided into large algorithmic "domains" of computational_physics, computational_mathematics and so on. I wrote it this way so that readers could easily learn about that topic of interest when it was sufficiently filled with algorithms. For example, if someone wanted to learn about computational physics, they just go to that section.

The problem here is that many of the algorithms in computational_physics could easily belong in computational_mathematics or other areas, so instead of providing large overarching directories, it might be better to divide those sections up into individual components (like ODE_solvers or something), and then provide an "algorithmic guide to computational physics" at the start, which provides commentary through all the different algorithms and methods in computational physics (kinda like a large outline for those who want to learn the topic).

These guides would be written after we have a sufficient number of algorithms in the Archive, so it will be a while, but I wanted to create an issue to keep this in mind and see if anyone has a better idea on how to organize this project. As always, I am open to suggestions!

missing imaginary protion in FFT

I was reading FFT chapter and looking at

Xk=∑N−1n=0xn⋅e−2πkn/N
and
xn=1N∑N−1k=0Xk⋅e2πkn/N

where did the imaginary numbers go?
it was in the integral before and in the code after the discrete fourier transform

Style Guide for Haskell

Style Guide for Haskell
There are some style considerations to make in regret to writing Haskell code.

Paradigm Preference
Normally Haskell programmers prefer to write declarative code instead of imperative code, but as imperative code is used on the mainstream and most non-haskell coders are more familiar with it, it could be viewed as an alternative.

Code Readability
As said in the "how_to_contribute.md" file we should use the style preferences of the language we are writing, but we should also consider readability as a must, because our code is going to be public and accessible on the internet.
I would recommend writing code as readable as possible even if you would rewrite it in a not so familiar style of coding.

An example:

euclidSub :: Integer -> Integer -> Integer
euclidSub a b = inner (abs a) (abs b) where
  inner a b =
    if a == b then
      a
    else if a < b then
      euclidSub a (b - a)
    else
      euclidSub (a - b) b

Could Be wiritten as:

euclidSub :: Integer -> Integer -> Integer
euclidSub a b = inner (abs a) (abs b)
  where
    inner a b
      | a == b = a
      | a < b = euclidSub a (b - a)
      | otherwise = euclidSub (a - b) b

(Example currently in use in the Euclidean Algorithm)

Complexity notation page inconsistent with array indexing

Some parts of the complexity notation page (chapters/principles_of_code/notation/notation.md) list arrays with base 0 indexing, others use things like a[1] to refer to the first element.

Although it's possible they could be from different languages, the examples are less likely to be misleading if all arrays are 0 based.

The linear time example also lists i = 0 : length, which would probably lead to an out of bounds error in languages providing them (not sure if this includes Julia) or runtime exception/similar.

Would you be willing to let me rewrite the C++ section in `euclidean`?

I'd like to change the style a bit to make it more similar to standard C++.

Also, the giant banner is unnecessary, and poor for accessibility.

Wiki - Code style guide

In this thread you can write coding standards, which are accepted in this project.
If you add new one, ping me to add it to wiki page.

This is because there are no PR's to wiki possible.

Wiki link

Pseudo-code

Since this is primarily a book, would it make since to provide pseudo code for each of the algorithms, something like CLRS's style. I think this would make implementing algorithms, and checking for errors in submitting implementations, a bit easier. It may also be useful if we ever intend to add complexity proofs to the chapters.

How to tell people how to compile?

Notably, for languages like C++, there are a few flags we might want to pass. Discussion here on how we'd like to format this.

Code box is too small

I think the way code is displayed should be changed a bit. Right now it's only about 45 characters wide. Ideally it should be 80.

DFS_recursive_inorder_btree in Julia would crash for singe-branch tree

In the code below, I think the case of single branch binary trees was not considered. It is checking >2 and >0 but not ==1 yet it uses [1]. We should add a case for single branch (which I realize is not well defined for here since we don't know if it's a left or right branch).

algorithm-archive/chapters/tree_traversal/code/julia/Tree.jl

Lines 28 to 43 in d9d8405

	# This assumes only 2 children
	function DFS_recursive_inorder_btree(n::Node)
	if (length(n.children) > 2)
	println("Not a binary tree!")
	exit(1)
	end
	if (length(n.children) > 0)
	DFS_recursive_inorder_btree(n.children[0])
	println(n.ID)
	DFS_recursive_inorder_btree(n.children[1])
	else
	println(n.ID)
	end
	end

Whitepace code not present in Euclidean chapter

I know this sounds like a joke because of how we implemented whitespace in the Euclidean algorithm chapter; however, if you highlight the code snippet, there is no actual whitespace there. It is available in the code/whitespace directory, though.

Run JS examples

Shouldn't we create a HTML file called index.html in the same directory as each JS file which just runs the JS code ?

Like this one :

<!DOCTYPE html>
<html>
	<head>
		<title>JS Example</title>
		<script type="text/javascript" src="_JS-FILE_.js"></script>
	</head>

	<body></body>
</html>

Adding people to the Algorithm Archivists organization

There are a few outstanding contributors I have been thinking about adding to the Algorithm Archivist organization. The organization, itself, has no special privileges, so I don't mind having quite a few people in the organization, but I am still hesitant to add people to the development team (with rights over the AAA).

My question here is how we should go about assigning new people to the organization. Should I just add people I trust or should we vote on each person individually? If we decide to vote, what is the best platform for the voting to occur?

The same goes for the development team. What do you guys think is the best way to become a member of the development team?

Should we restructure the organization?

Useless chapters.

The AAA has a couple of useless chapters like Mathematical Background and Principle of Code. The Chapter A Personal Note is weird but I think it should be renamed preface and should be less personal.

Missing algorithm implementations

Hacktoberfest is during the month of october and we wanted to open up submissions for any algorithm in any language that is currently missing. This should follow the How to Contribute wiki, and missing implementations can be found with @julianschacher's Language Implementation Progress Monitor (LIPM). If you are having trouble with git and version control, please also check out the video guide by @Butt4cak3

There are also quite a few languages that need to be updated, namely most C++ implementations and any implementations missing both example code and code that fits into the in-text code snippets. For example, there are certain algorithms that have julia code instead of the language chosen simply because the language does not have that code snippet implemented yet.

Algorithms that require plotting

Hey guys,

There are a few algorithms in the archive that require plotting and a few more are on the way. Obviously, not all languages come with a plotter, so I have been outputting the data into a file format that can be plotted with gnuplot. I don't know if this is good practice or not. On the one hand, it provides a stable output format that allows all code from the AAA to look the same in the end and everything can be plotted with a simple gnuplot plot.gp - command.

On the other hand, some languages already have in-built plotters.

I feel that the languages that do not have plotters, should have a consistent output format. Gnuplot is good for this because it's cross-platform and kinda the standard for HPC plotting.

Should we require everyone to output to gnuplot or should we allow them to use their in-built plotters?

As a note: I think it is best to put the gnuplot script in a separate directory in the code/ directory for each algorithm

Anyway, I wanted to hear your thoughts on this.

FYI: rosetta code

Maybe I'm stating the obvious, but just to be sure: Rosetta Code currently hosts 879 "programming tasks" in 697 languages.

Cheers,
Hans

MathJax stuff at the top of the chapters causes bad search result previews

The MathJax stuff at the top of the individual chapters causes bad result previews when searching the AAA.

Personal Issue List

• tree_traversal: c++ - renamed to tree.cpp, fixed identifier style

• tree_traveral: ocaml - added back

• euclidean_algorithms: c++ - make sure it's good

• euclidean_algorithms: all - rename the "euclidean_example" files to "euclidean"

• convolutions: c++ - copy the fft from fft

• convolutions: c++ - rewrite to make it compile

• verlet: c++ - make sure it's good

• sorting_searching: add C++

(gonna start fixing these once something similar to #61 is merged)

Chapter Contributors

As discussed on discord, how many writers should there be?

Strawpol: https://strawpoll.com/53bxcwpf

Implementation of Language specific guidelines

Related closed issues: #152 #18 #12 #25.
In my opinion, we should consider adding good practices, links to linter and prettifiers and general styling rules, like using spaces instead of tabs for indentation and how many spaces to each language.
But this could be a good place to define a way to contribute in relation to writing the chapter's text, like in #25, as, for now, we have to wait for @leios working on it and there is not a defined way of writing and submitting PR in respect of this.

• Start writing a How to Contribute section
• Make language-specific subsections as we think about them
• Make a general section for defining common styles and list "Prettifiers" and "linters"
• Add PR and Issues templates

C code in Graham Scan chapter is not highlighted

https://www.algorithm-archive.org/chapters/algorithms/graham_scan/graham_scan.html

code function ccw() is highlighted, following snippet and whole code is not :(

Search doesn't provide related results, maybe use tags?

I discovered that the search we're currently using for the AAA doesn't provide results related to the search term.

If I'm searching for geometry for example, I get the expected chapter Computational Geometry.

I don't get the sub-chapters of Computational Geometry however.

I thought that we can maybe add a tag system to the AAA. I.e. adding tags to each chapter, so that the search functionality also catches chapters related to the search term.
I know that it's not ideal however, since the AAA might get restructured and we can only guess, what terms people will use to search the AAA.

So what are your opinions on that? Do you like the tag system, do you have better ideas like another system, search engine, etc.?

Gauss elimination code (Julia) is wrong

Basically

• Don't check for singularity as Gauss Elimination can be done on singular matrices
• Pivots are not neccessarily on the diagonal
• Cover the general case and don't assume triangular matrices

This issue affects PR #200 (contains more details on the bugs) and PR #195

Standardize on style

mult-lang explanation / how to contribute

We should have a comprehensive how-to-contribute file, which includes documentation on how to use the theme-api with the book.json.

Broken syntax highlighting for some C/C++ code examples

Note: This issue exists primarily for documentation. I don't expect anyone else to step in. If you still want to help me investigate the issue, feel free to join me!

---

This is not a new one, but I found what causes the issue in some cases. I looked through the stable marriage code and found out that the second of these two lines breaks it. The first one is fine, but I left it in for comparison:

static thread_local std::random_device global_random_device;
static thread_local std::mt19937 global_rng(global_random_device());

The issue is with highlight.js, which we have already forked because I fixed another issue in it. The next step is to figure out what exactly causes it.

Make use of code-run-websites

For many languages websites exist, where people can run code snippets.
We currently don't really do that in the AAA, but I think it's a cool thing to add for languages supporting it.
People wouldn't have to download and install everything needed just to run some code and people could also run code on mobile.

This topic came to my attention again, because of this #164 which included a convenient way to run the code.

So I open this issue for discussion about this topic. What do you guys think?

Should we have seperate python2 and python3 codes?

The current state of python code:

• Tree Traversal (python2 and unfinished python3)
• Euclidean Algorithm (python2)
• Bubble Sort (python3, but unlisted)
• FFT (python2)

My question is if we really need to split the code into separate implementations for python2 and python3. It would probably be a much better design to just have a python implementation, and write it so it runs on both versions. For practical purposes this means that it is the print-statement that is going to be the most obvious problem to combine, but this very neatly fixed by including the following code at the start

from __future__ import print_function

which allows python2 to write print('Hello World'). The second most obvious difference is that the division operator / is interpreted as integer-division in python2 while always floating point division in python3. Again: we can write compatible code by including the __future__ library

from __future__ import division

Error in Tree Traversal code c#

The function DFSStack() for the Tree Traversal's example is missing a parameter of type "Node" called "root".

Relicense under MIT

ping:

• @ubsan

• @leios

• @Gathros

• @kingfredrickvi

• @julianschacherpp

Please write the following in a comment

I agree to have all of my previous and future commits to this repository licensed under the MIT license, as found in LICENSE.md.

and put your name in the CONTRIBUTING.md file.

me first:

I agree to have all of my previous and future commits to this repository licensed under the MIT license, as found in LICENSE.md.

Leaving gitbook

Hey Guys,

We found out recently that gitbook is planning to stop supporting its current version and will be moving to a proprietary system without plugins. We need plugins and strongly prefer open source. In addition, they are turning off the legacy gitbook servers soon.

After talking to support about this, we came to the conclusion that we should move the Algorithm Archive off of the gitbook site. The easiest solution to this is to create a new algorithm archive organization (and corresponding github pages site), which has a few benefits:

1. We can fork the legacy gitbook repos and plugins for when / if they go down (est. 6 months)
2. We can give people more permissions so they can more quickly handle PR's and can modify their own projects
3. We can use a github pages page for the algorithm archive for now on (algorithm-archive.github.io)

There was a lot of talk about this on discord, but I failed to discuss this on gitbhub. The plan is to create this organization soon and shift everything to the github url then too.

Please feel free to discuss alternative solutions here.

Language list should switch to dropdown when it overflows.

Here's an example of how it looks like without collapsing it. With so many languages, one of them is bound to overflow eventually (even on large screens). It would be nice to have either a "more" dropdown or just switch the entire thing to a dropdown.