wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Usefulness of advanced algorithm design courses
        
(Message started by: amichail on Nov 28th, 2006, 7:55pm)
Title: Usefulness of advanced algorithm design courses
Post by amichail on Nov 28th, 2006, 7:55pm
How useful are advanced algorithm design courses for software engineers?

This seems like a complicated question to me.

If a software engineer encounters a common problem, then there is almost certainly a library with one of the best algorithms available for that problem.

If a software engineer encounters an obscure problem, then what is the probability that (a) the problem is tractable and (b)  the software engineer would find an efficient algorithm for that problem?

And even if the software engineer succeeds in that respect (and perhaps publishes a paper or two along the way), what happens if the problem evolves as the system evolves?

What is the probability that the efficient algorithm will continue to apply, at least in some variation?

Whether or not advanced algorithm design courses are useful for software engineers appears to be an empirical question that would be quite difficult to answer.
Title: Re: Usefulness of advanced algorithm design course
Post by Sameer on Nov 28th, 2006, 9:23pm
i am not from comp sci background but from my friends who are and the algorithm books they have been reading, I think the course is very important. It is just not the case of knowing algorithms and that libraries are available, but it is also important for software engineers to know the techniques employed in reducing the complexity of calculations. The approach is more useful than the content itself.
Title: Re: Usefulness of advanced algorithm design course
Post by Whiskey Tango Foxtrot on Nov 28th, 2006, 9:35pm
I agree as well.  I am not a comp sci major either, but I have taken more than my fair share and have used almost everything I've learned in those classes in EE courses and projects.  I actually talked this over with my uncle, who works at Goldman Sachs, and he said that finding a more efficient algorithm is the major selling point for most computation-based services.  If your company can pump out 40 calculations in the time it takes your competitor to do 25, you are providing a more valuable service.  Learning how to create advanced algorithms is invaluable in my opinion, but I'm interested to see what some of the more experienced computer wizards on the site have to say.
Title: Re: Usefulness of advanced algorithm design course
Post by towr on Nov 29th, 2006, 1:37am

on 11/28/06 at 19:55:33, amichail wrote:
If a software engineer encounters a common problem, then there is almost certainly a library with one of the best algorithms available for that problem.
It is actually rare to find that a general library function does exactly what you specifically want. Libraries do general things pretty well, but specific things not as well as possible. A good software engineer should be able to make up some of that difference, although hobby programmers probably won't.


Quote:
If a software engineer encounters an obscure problem, then what is the probability that (a) the problem is tractable and (b)  the software engineer would find an efficient algorithm for that problem?
If he followed an advanced algorithm design class, the chances are rather better than if he hasn't. Because in the design class he'll have learned how to think about reducing the problem to manageble proportions.
And of course efficiency is a relative term. If the only alternative is the application of a brute force library function, then chances are he can vastly improve the computation process. I know people working with image/handwriting processing, where processing the database in the standard way would take weeks, but with improved algorithms it takes mere hours. It can be very important to squeeze out those last few cycles.


Quote:
And even if the software engineer succeeds in that respect (and perhaps publishes a paper or two along the way), what happens if the problem evolves as the system evolves?
Typically the application/algorithms also evolves. It's just coevolution at work.


Quote:
What is the probability that the efficient algorithm will continue to apply, at least in some variation?
Pretty good, generally. As the key problems don't usually change that much. And even if they do, you want to get there as fast as possible. If nothing else an efficient algorithm is usefull to bring you to the next stage as fast as possible. A bit of thought can safe you months of work (especially in fields involving vast amounts of dataprocessing, as mentioned before).


Quote:
Whether or not advanced algorithm design courses are useful for software engineers appears to be an empirical question that would be quite difficult to answer.
If it's an empirical question, then experiment.
-Make two groups of students
-Make/compile a set of complicated problems
-Have one group start right away at solving them, and the other first follow a course in advanced algorithm design.
-At the end check who has made the most and best progress a year later.
It will probably be the second group, even though they started late due to "wasting" a quarter studying design.
Title: Re: Usefulness of advanced algorithm design course
Post by amichail on Nov 29th, 2006, 1:47am

on 11/29/06 at 01:37:42, towr wrote:
Pretty good, generally. As the key problems don't usually change that much. And even if they do, you want to get there as fast as possible. If nothing else an efficient algorithm is usefull to bring you to the next stage as fast as possible. A bit of thought can safe you months of work (especially in fields involving vast amounts of dataprocessing, as mentioned before).

It seems to me that efficient algorithms tend to be very brittle. Change the problem even slightly, and they may not apply at all. In fact, the problem may in fact become intractable. This is not a good sign for rapidly changing requirements.

By "efficient algorithms", I mean ones with good worst case/average case guarantees.

Heuristics, which provide no such guarantees, might be less brittle in the presence of changing requirements. But heuristics don't require an advanced algorithms class either.
Title: Re: Usefulness of advanced algorithm design course
Post by towr on Nov 29th, 2006, 2:15am

on 11/29/06 at 01:47:43, amichail wrote:
It seems to me that efficient algorithms tend to be very brittle. Change the problem even slightly, and they may not apply at all.
Not without adapting the algorithm slightly, no. Btu I don't see why that would be a problem.


Quote:
This is not a good sign for rapidly changing requirements.
Areas were efficiency is required aren't generally all that changeable in my experience. Notable because efficiency isn't needed unless you have "a lot of the same" going on repeatedly.


Quote:
But heuristics don't require an advanced algorithms class either.
They don't?!
Title: Re: Usefulness of advanced algorithm design course
Post by amichail on Nov 29th, 2006, 2:19am
By heuristics, I mean algorithms with no guarantees.

So I don't see that there is a lot to teach people about how to come up with heuristics.
Title: Re: Usefulness of advanced algorithm design course
Post by amichail on Nov 29th, 2006, 2:22am

on 11/29/06 at 02:15:00, towr wrote:
Not without adapting the algorithm slightly, no. Btu I don't see why that would be a problem.

Changing the problem slightly might make it intractable (e.g., NP-complete). It's not obvious that the original algorithm or a slight variation thereof would be of any use now.
Title: Re: Usefulness of advanced algorithm design course
Post by towr on Nov 29th, 2006, 3:05am

on 11/29/06 at 02:22:27, amichail wrote:
Changing the problem slightly might make it intractable (e.g., NP-complete). It's not obvious that the original algorithm or a slight variation thereof would be of any use now.
I disagree that that is generally the case. It's a matter of evolution, usually you don't stray very far from where you start. Radical changes of the problem at hand are rare.


on 11/29/06 at 02:19:13, amichail wrote:
By heuristics, I mean algorithms with no guarantees.

So I don't see that there is a lot to teach people about how to come up with heuristics.
Again, I disagree. It is a way of thinking that doesn't come naturally to everyone, and it needs to be develloped. A sort of philosophy of computation. There's really much more to it than a bit of handwaving.
Take computational chess for example, the heuristic strategies it employs are hardly trivial. And while it may not guarantee the best play, it is generally better under time constraints than an algorithms that would guarantee best play (for one, because that would be intractable except in endgames)
Title: Re: Usefulness of advanced algorithm design course
Post by kay on Dec 22nd, 2006, 1:45am

Some points which seem to be missing so far from the discussion:

1. One of the most important things you learn in an advanced algorithms class is the notion of reduction. A large fraction of problems programmers face in practice can be reduced to standard problems such as max flow or matching. Having taken an algorithms class makes you better positioned to realize that there is a reduction.

2. Of course there is the question of knowing that problems such as min cost flow and B-matching can be solved efficiently, and knowing how to solve them. In an algorithms class, you learn that these are well studied problems.

3. A math class teaches you how to add numbers, so that even though it doesn't explicitly teach you how to add 12442 and 1077543, you are usually in a position to add these two after learning to add. In a similar way, an algorithms class teaches you how to think algorithmically... so that you can solve the particular problem you face later.

4. Often I have found that programmers don't even recognize that there can be a non-brute force way to do something.  Often that is fine in that the problem is not really a bottleneck and may not be worth the time spent looking for a better solution. Sometimes though it can really make a difference.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board