Some pointers on implementing algorithms in code

tags:

algorithm

views:

151

answers:

+1 Q:

Some pointers on implementing algorithms in code

Hi,

The other day I thought I'd attempt creating the Fibonacci algorithm in my code, but I've never been good at maths.

I ended up writing my own method with a loop but it seemed inefficient or not 'the proper way'.

Does anyone have any recommendations/reading material on implementing algorithms in code?

+4 A:

I find Project Euler useful for this kind of thing. It forces you to think about an algorithm and then implement it. Many of the questions then have extensive discussions on how to solve the problem (from the naive solutions to some pretty ingenious ones) that you can use to see what you did right and wrong.

In the discussion threads you'll find various implementations from other people in many different languages too. Coming up with a solution yourself and then comparing it to that from other people is (imho) a good way to learn.

cletus 2009-04-28 23:31:39

+1 A:

Both of these introductory books have good information about this sort of thing: How To Design Programs and moreso Structure and Interpretation of Computer Programs

Both are somewhat funcitonal (and scheme) oriented, but that's a natural fit for these sorts of problems.

On top of that, you might get quite a bit out of Project Euler

simon 2009-04-28 23:32:45

+1 A:

Go on youtube and look at some of the lectures on Introduction to Algorithms. There are some really, really good lectures that break down some of the most common algorithms such as the Fibonacci series and how to optimize them.

Start reading about O notation so you can understand how your algorithm grows with variable size input and how to classifiy the run-time of the algorithm you have.

Start with this video series which I found excellent material on the subject:

Algorithms Lecture

Ralph 2009-04-28 23:33:56

+1 A:

Derive your algorithm test-driven. I've been able to write much more complex algorithms correctly by using TDD than I was before.

Stephan Eggermont 2009-04-28 23:38:49

Kent Beck has an example of using TDD to implement the Fibonacci sequence, and ends up with the recursive solution. The right solution should be "with a loop" because it has better performance and helps understand infinite streams, vs. helping to understand recursion for a sub-par solution.

Andrew Dalke 2010-01-19 17:07:01

Convert recursion to iteration is a standard refactoring for non-optimizing compilers.

Stephan Eggermont 2010-01-19 18:09:27

Refactoring for tail recursion is mechanical, as is refactoring using a heap-based stack. Neither change the run-time behavior. But Fib(n) is one case where some analysis shows that building up to the solution iteratively is faster than recursively going down. That's new algorithm development, not a standard refactoring. How does TDD help? Eg, I add "fib(50)" as a test case to the recursive solution found through TDD (see Beck or Bernhardt) and after 10 minutes kill the process. Fowler calls this refactoring "Substitute Algorithm", which is the step the OP wants help understanding.

Andrew Dalke 2010-01-20 04:12:33

Ok. Also "introduce a cache" I can see doing TDD, even the one with just the two last values. Too bad AssertRunsFast() is missing. The matrix multiplication one I cannot see from a TDD perspective, there I agree you'd need analysis. http://www.ics.uci.edu/~eppstein/161/960109.html

Stephan Eggermont 2010-01-20 07:10:59

If you can't translate pseudo code for a fibonacci function to your language, then you should go and find a basic tutorial for your language, since it seems that you have not yet grasped its basic idioms.

If you have a working solution, but feel insecure about it, show it to others for review.

Svante 2009-04-29 00:55:08

ansaurus

tags:

views:

answers:

Some pointers on implementing algorithms in code

related questions