Problem-solving is not a science, but part art and part skill. I read this phrase and list of common practices for algorithm design in S.S. Skiena, The Algorithm Design Manual book. Skiena explains that this is one of the skills most worth developing. I've read other data-structures and algorithms books, and I've never found one like this one. Algorithm Design Manual - is a very deep book and it is easy to understand
For example, Skiena says: "Its unconventional approach is refreshing and keeps you interested. I find myself coming back to it frequently, and always learning something new. The key to algorithm design (or any other problem-solving task) is to proceed by asking yourself questions to guide your thought process. What if we do this? What if we do that? Should you get stuck on the problem, the best thing to do is move onto the next question. In any group brainstorming session, the most useful person in the room is the one who keeps asking, “Why can’t we do it this way?” not the person who later tells them why, because she will eventually stumble on an approach that can’t be shot down."
Written by a well-known, IEEE Computer Science teaching-award winner, this new edition is an essential learning tool for students needing a solid grounding in algorithms, as well as a uniquely comprehensive text/reference for professionals. The book is an algorithm-implementation treasure trove, and putting all of these implementations in one place was no small feat. The list of implementations and extensive bibliography make the book an invaluable resource for everyone.
This newly expanded and updated second edition continues to take the "mystery" out of designing algorithms and analyzing their efficacy and efficiency. Expanding on the first edition, the book now serves as the primary textbook of choice for algorithm design courses while maintaining its status as the premier practical reference guide to algorithms for programmers, researchers, and students.
The reader-friendly Algorithm Design Manual provides straightforward access to combinatorial algorithms technology, stressing design over analysis. The first part, Techniques, provides accessible instruction on methods for designing and analyzing computer algorithms. The second part, Resources, is intended for browsing and reference and comprises the catalog of algorithmic resources, implementations, and an extensive bibliography.
- Do I really understand the problem?
(a) What exactly does the input consist of?
(b) What exactly are the desired results or output?
(c) Can I construct an input example small enough to solve by hand? What happens when I try to solve it?
(d) How important is it to my application that I always find the optimal answer? Can I settle for something close to the optimal answer?
(e) How large is a typical instance of my problem? Will I be working on 10 items? 1,000 items? 1,000,000 items?
(f) How important is speed in my application? Must the problem be solved within one second? One minute? One hour? One day?
(g) How much time and effort can I invest in implementation? Will I be limited to simple algorithms that can be coded up in a day, or do I have the freedom to experiment with a couple of approaches and see which is best?
(h) Am I trying to solve a numerical problem? A graph algorithm problem? A geometric problem? A string problem? A set problem? Which formulation seems easiest?
What is known about the problem? Is there an implementation available that I can use?
- Can I find a simple algorithm or heuristic for my problem?
(a) Will brute force solve my problem correctly by searching through all subsets or arrangements and picking the best one?
i. If so, why am I sure that this algorithm always gives the correct answer?
ii. How do I measure the quality of a solution once I construct it?
iii. Does this simple, slow solution run in polynomial or exponential time? Is my problem small enough that this brute-force solution will suffice?
iv. Am I certain that my problem is sufficiently well defined to actually have a correct solution?
(b) Can I solve my problem by repeatedly trying some simple rule, like picking the biggest item first? The smallest item first? A random item first?
i. If so, on what types of inputs does this heuristic work well? Do these correspond to the data that might arise in my application?
ii. On what types of inputs does this heuristic work badly? If no such examples can be found, can I show that it always works well?
iii. How fast does my heuristic come up with an answer? Does it have a simple implementation?
- Are there special cases of the problem that I know how to solve?
(a) Can I solve the problem efficiently when I ignore some of the input parameters?
(b) Does the problem become easier to solve when I set some of the input parameters to trivial values, such as 0 or 1?
(c) Can I simplify the problem to the point where I can solve it efficiently?
(d) Why can’t this special-case algorithm be generalized to a wider class of inputs?
(e) Is my problem a special case of a more general problem in the catalog?
- Which of the standard algorithm design paradigms are most relevant to my problem?
(a) Is there a set of items that can be sorted by size or some key? Does this
sorted order make it easier to find the answer?
(b) Is there a way to split the problem into two smaller problems, perhaps by doing a binary search? How about partitioning the elements into big and small, or left and right? Does this suggest a divide-and-conquer algorithm?
(c) Do the input objects or the desired solution have a natural left-to-right order, such as characters in a string, elements of a permutation, or leaves of a tree? Can I use dynamic programming to exploit this order?
(d) Are there certain operations being done repeatedly, such as searching, or finding the largest/smallest element? Can I use a data structure to speed up these queries? What about a dictionary/hash table or a heap/priority queue?
(e) Can I use random sampling to select which object to pick next? What about constructing many random configurations and picking the best one? Can I use some kind of directed randomness like simulated annealing to zoom in on the best solution?
(f) Can I formulate my problem as a linear program? How about an integer program?
(g) Does my problem seem something like satisfiability, the traveling salesman problem, or some other NP-complete problem? Might the problem be NP-complete and thus not have an efficient algorithm? Is it in the problem list in the back of Garey and Johnson? Am I still stumped?
References
Skiena Press
http://www.algorist.com/
The source code of the book solutions
Buy Algorithm Manual book on Amazon
Algorithm lecture presentations: Skiena TheAlgorithmDesignManual.zip (4.70 MB)
Video lectures
Summary
Though less academic than "Introduction To Algorithms" (by Charles E. Leiserson (Author), Ronald L. Rivest (Author), Clifford Stein), this ain't the book to pick up to learn about coding algorithms for a quick study on problem-solving practices.
