Summary

Requesting tasks relating to CS problems.

Discussion

There was a discussion in the IRC channel a while back where Short Circuit noted that a lot of RC traffic comes from corresponding wikipedia articles. He has asked me to come up with a list of algorithms for which we want tasks. We would want a solid explanation and a starting implementation for these tasks. I have collected a bunch of algorithms from this list that probably belong here (any item from that list is probably good to have though):

Sorting algorithms

Gnome sort

I've used Gnome sort in Huffman codes, to sort the heap! Nonetheless I'm little scared by words like "we would want a solid explanation" and "Anyone with a good (and/or recent) CS background..." to be able to start a new task with Gnome sort (my explanation would have been the one in Wikipedia!) --ShinTakezou 23:40, 26 April 2009 (UTC)

I wouldn't let that stop you; At worst, someone will correct the page, and it will come out better for it. --Short Circuit 06:23, 27 April 2009 (UTC)

Counting sort

Computational geometry

Closest pair problem: find the pair of points (from a set of points) with the smallest distance between them
Point in polygon algorithms: tests whether a given point lies within a given polygon

Point in polygon using the ray casting algorithm

Computer algebra

Polynomial long division

Number theoretic algorithms

Integer factorization: breaking an integer into its prime factors (I haven't checked into any of these algorithms. Make sure they're appropriate.)

— see Prime decomposition; which algo is in use there? --ShinTakezou 09:39, 26 June 2009 (UTC)

Congruence of squares
Dixon's algorithm
Fermat's factorization method
General number field sieve
Lenstra elliptic curve factorization
Pollard's p − 1 algorithm
Pollard's rho algorithm
prime factorization algorithm
Quadratic sieve
Special number field sieve

Numerical algorithms

Nth roots

Nth root algorithm
Shifitng nth root algorithm

Interpolation (linear and cubic are probably enough)
Eigen value calculation

Kinda cool

XOR swap algorithm

Anyone with a good (and/or recent) CS background is encouraged to jump on these tasks. Link to them as you create them. Try to give an initial implementation to help solidify the task description. --Mwn3d 21:09, 16 March 2009 (UTC)