Optimal Algorithms

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

Post Reply
dennismv
New poster
Posts: 3
Joined: Tue Jul 03, 2007 2:48 pm

Optimal Algorithms

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.

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

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
New poster
Posts: 3
Joined: Tue Jul 03, 2007 2:48 pm

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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

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.

Post Reply

Return to “Other words”