Optimal Algorithms

dennismv · Post by **dennismv** » Tue Jul 03, 2007 3:04 pm

I'm creating a site for algorithms in wiki style -- Optimal Algorithms.

The goal for is to create a ready to use implementation library of algorithms that one can search and use to help out with problem solving.

My focus is on simple implementation of algorithms using STL when possible and using simple data structures when possible. Things like longest common/increasing subsequence, convex hull, graph algorithms, etc - anything clever I would like to have included. I've started with a few algorithms and will be adding more.

Comments/Contributions welcome.

Hadi · Post by **Hadi** » Wed Jul 04, 2007 1:10 am

Why is the name "Optimal Algorithms"?
If you define an "optimal algorithm" as an algorithm that has the optimal time / memory complexity; I should say some of algorithms you have described might not be optimal

dennismv · Post by **dennismv** » Thu Jul 05, 2007 11:29 pm

In general it's for algorithms that are fast enough time wise to get you accepted/AC in programming contests.

Often you can't get both optimal time and optimal memory complexity. If I have a choice, I'd prefer optimal time complexity.

I think that algorithms like All Pairs Shortest Path of O(n^3), and LIS of O(n log n) on the site are good enough examples. If you need to find all shortest paths or LIS of something, for all possible inputs, I'm not aware of faster algorithms.

misof · Post by **misof** » Mon Jul 09, 2007 8:05 am

Have you seen http://boost.org/ and possibly also http://algorithmist.com/? Maybe contributing to an existing project makes more sense than starting your own -- this is not a task for one man.

Oh, and there is an asymptotically more efficient algorithm for all-pairs shortest paths. I'm not sure about the LIS now, but at least for some special cases (e.g., input values are integers of size polynomial in N) it can be solved faster.