Algs4-C#

The book Algorithms 4th Edition contains Java implementations for many fundamental algorithms "the 50 algorithms that every programmer should know". The authors created a website, http://algs4.cs.princeton.edu/code/ where all the code for the book is published as a class library algs4 (including additional code that was omitted from the book itself for brevity reasons).

Personally I prefer using C# so I have decided to re-implement algs4 in C# (some reasons I like C# is because it has been evolving from an original "very Java-like" object oriented language into a very flexible multi-paradigm language, and also because I like the tools in Visual Studio better than the equivalent tools for Java)

I am trying to preserve the original APIs with minimal changes, extending them in some cases. If there is java code that uses the original algs4 I want it to be easy to port to C# using my re-implementation. On the other hand I use static code and style checking extensively (fxcop, stylecop and similar tools) and my code follows C# style rules (e.g., in terms of capitalization). An additional porting effort will be required, it will not be a drop-in replacement.

The original algs4 mixes executable clients with the libraries themselves. I have separated the client code into test projects. Initially I'm expecting this to provide some degree of Unit testing. Eventually (after I get to implement the entire algs4 library) I may re-visit the Unit Tests to make them more exhaustive (and "real unit tests")

Sedgewick & Wayne also wrote the book Introduction to Programming in Java and an associated class library stdlib that they use in the algs4 code. I will re-implement some portions of stdlib as I need but I do not expect it to be complete, and my target quality level for stdlib is that it is "good enough" (e.g., for I/O functions I will not try to make it solid to deal with the many types of failure that can happen)

Implemented functionality

Algs4

• Binary search
• Quick find Union-Find
• Quick union Union-Find
• Weighted quick union Union-Find
• Weighted quick-union by rank with path compression Union-Find
• Insertion sort
• Optimized insertion sort with half exchanges and a sentinel
• Selection sort
• Shellsort
• Top-down mergesort
• Bottom-up mergesort
• Optimized mergesort with cutoff to insertion sort
• Quicksort
• Quicksort with 3-way partitioning
• Optimized quicksort using Bentley-McIlroy 3-way partitioning, Tukey's ninther, and cutoff to insertion sort
• Max and Min Priority Queues (Heap based, generic keys, ICollection<T>)
• Max and Min Index Priority Queues (Heap based, generic priorities, IDictionary<int, T>)
• Heapsort

Stdlib:

• Input from files and urls
• Random distributions: Bernoulli, Uniform, Gaussian, Discrete, and Exponential
• Shuffling

Licensing

The original algs4 is released as GPLv3. In the Q&A section of the original code it says:

Our libraries stdlib.jar and algs4.jar are released under the GNU General Public License, version 3 (GPLv3). If you wish to license the code under different terms, please contact our publisher to discuss.

My re-implementation is also released under the same terms. Personally I would have chosen a less restrictive licensing (e.g. GPLv2 with "or later" clause, or MIT License). If you can get the original owners of algs4 to agree to different terms, please let me know and I'll release my re-implementation with a less restrictive license

Contact Information

If you'd like to contact me regarding this code, please email algs4 (hyphen) csharp (dot) nospam (at) rufian (dot) zilbermann (dot) org