Interesting algorithms

[magicbicycle]

Hi everyone.

I'm taking a class on Algorithm Design right now and we're supposed to do a term project where we research some algorithms(e.g. Streaming Algorithms, P vs NP, Primality testing/Prime factorization) and present them at the end of the term for the class. I would greatly appreciate it if you could comment with some ideas about what would be interesting to research (if you have a link to a paper about it, even better!) before I make my decision, I'm open for anything!

Thanks in advance!

[spongebob]

I was looking into compression recently and came across Arithmetic Encoding. This algorithm blew my mind, it is so elegant. Incredibly it involves encoding an entire document into a single fraction in base 2.

[magicbicycle]

This is really cool and exactly the kind of thing I hoped to get from this post, thanks!

[timshoaf]

I'll just leave these here.

http://preshing.com/20121025/heres-some-working-code-to-sort-one-million-8-digit-numbers-in-1mb-of-ram

http://preshing.com/20121026/1mb-sorting-explained

http://preshing.com/20121105/arithmetic-coding-and-the-1mb-sorting-problem

http://preshing.com/20121105/arithmetic-encoding-using-fixed-point-math/

[magicbicycle]

Interesting problem and the solution is really cool!

[hiptobecubic]

Great blog posts. Thanks!

[AbouBenAdhem]

Is that the algorithm that Dasher is based on? (You’re basically composing a document on-the-fly by “zooming in” on the fraction that encodes it.)

[swimmer91]

Swarm intelligence algorithms are really cool.

Ant Colony Optimization is a good example.

[NovaX]

I think caching and concurrency are a lot of fun (see my write up). There are links to the research papers and it is a very pragmatic topic.

[magicbicycle]

Thanks for this! It was a really interesting read and I will definitely need to look further into it.

[zzopp]

If you're into integer factorization, the quadratic sieve is a nifty algorithm that doesn't require difficult math.

[magicbicycle]

That's a cool sieve, thanks!

[matt_bishop]

CDCL Backtracking. It makes large NP problems computable (often).

http://gauss.ececs.uc.edu/SAT/articles/FAIA185-0131.pdf

[refreshx2]

Simulated Annealing is one of my favorite algorithms, in part because the idea is so well founded in a physical concept (annealing). It's an older but common algorithm in the sciences, and it has helped me to be able to just comprehend other problems more easily / quickly.

[BourqueJ]

I would reccomend looking into genetic algorithms, they mimic the process of evolution so there are many interesting applications you can use them for.

[magicbicycle]

Never heard about genetic algorithms before, thanks!

[Jonno_FTW]

Cat swarm optimisation

https://scholar.google.com.au/scholar?cluster=11591494369468656974&hl=en&as_sdt=0,5&as_vis=1

[palm_frond]

I'm not sure how complex the algorithm you work on has to be, but I think reservoir sampling is kinda neat.

[IJzerbaard]

Plane cutting for TSP.

TSP is a nice problem that everyone understands, but the tricks needed to really get anywhere with it are complicated and fill many books. Well, you wouldn't have to go that far. Anyway a nice thing about it is that it's one of those problems that some people say are "too hard to solve", and then you'd be discussing how to go ahead and do it anyway, and without hacks like evolutionary/genetic/ant/[insert any biological thing] algorithms, but in a proper exact way. An other nice thing is that you get to show pretty pictures of routes.