Rosetta Code:Village Pump/CS Pages Wanted

CS Pages Wanted
This is a particular discussion thread among many which consider Rosetta Code.

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)