Over the years I have worked with many algorithmic problems and there is definitely a pattern in the approach for solving them. I would like to note down my current approach of solving them and many books talk about similar stuff.
0. Solve by bruteforce(or backtracking)
If the problem size is small and bruteforce approach is ok, then do it and not worry too much about the efficient solution. Make sure you do some back of the envelop runtime cost calculations before you disregard bruteforce. In some problems, you might need an intelligent algorithm to solve a sub-problem and then a bruteforce approach to combine sub-problem solutions. This is especially true for some of the problems in code competitions.
now on to the ways of finding efficient solutions....
1. Solve by Example or solving problem instances of small sizes, n = 1,2,3..
Here we solve some example inputs to the problem, e.g. if the problem input is a number n, then I will try to solve it manually for n = 1,2,3,4... and see if a solution clicks in my mind. This same approach can sometimes lead to solution involving recursion(and dynamic programming) described later.
2. Solve by Simplification
Here We try to remove/add some constraints from/to the problem that simplify it, solve the simpler version or a different but similar problem and see if it can be used to solve/understand the original problem.
3. Solve by Recursion
"Thinking Recursively" is an art. Best way to "get" recursion is to practice and read the literature on functional programming where recursion is one of the key concepts. I highly recommend working through SICP and the "wishful thinking" concept described there. For example, to get factorial(n) you will think like, make a wish that someone gives you the factorial(n-1) then how will you get factorial(n) using that of (n-1). Be wishful !!
One of the things I "got" over time is that, for recursion to work It is not necessary that
f(n) = g(f(n-1))
but all of the following could work also
f(n) = g(f(n-1),f(n-2))
f(n) = g(f(n-1),f(n-2),f(n-3))
....
f(n) = g(f(n-1),f(n-2),...f(1),f(0))
3.1 Divide and Conquer(for example standard solution to merge-sort) is another powerful problem solving technique which uses recursion. Here, you solve the original problem by "merging" the solutions of two or more disjoint sub-problems(which are solved recursively).
3.2 Dynamic Programming is an optimization to improve running time after you have a recursive strategy. Draw the recursion tree and see if same sub-problem is being solved multiple times. That is, you will notice that total number of distinct sub-problems to be solved is much less than the total number of sub-problems being solved in straightforward recursive implementation. (In cormen et al, it is called the overlapping sub-problems property).
In such cases, a lot of, redundant computation is saved by caching the solution of various sub-problems and reusing them when required again.
Solution can be implemented either top down recursive with a table to cache the sub-problem solutions or a bottom-up iterative where you solve the smaller sub-problems first and then solve the bigger using solution of smaller sub-problems.
Some problems solved by dynamic programming are optimization problems and they exhibit optimal substructure property, that basically means that optimal solution to bigger problem "contains" optimal solution to the smaller sub-problems.
Most of the time, proof by induction is used here to prove the correctness of algorithm.
4. Solve using Greedy approach
It is a algorithm technique where making locally optimal/correct decisions, *sometimes*, leads to globally optimal/correct solutions. Usually, you can get idea of the solution by solving small size instances of the problem. However, this idea may or may not be correct so it is *essential* to prove that your locally optimal strategy gives you globally optimal results too.
In most of the cases following proof strategies work for greedy algorithms..
- proof by induction
- proof by contradiction: it is sometimes combined with, proof by exchange argument. Here you assume some optimal solution S* and a solution S produced by your greedy algorithm. Using, exchange of elements in S* so that exchange either preserves the optimality score or makes it better, you transform S* to S and that essentially proves that S is either better or equally good as S*. And hence, your greedy strategy works.
- Anything else :)
5. Solve by Reduction
Here we try to reduce the given problem to another problem whose solution is well-known and many of the code challenges problems are of this nature. Some of the algorithms, which come up very frequently, and you should know them by heart(including their proof, and if you have problem reading proofs then you need to work through How to Prove it!). Knowing them also means having their concise/optimal implementation in your [muscle] memory.
Sorting Algorithms - Index Sort, Merge Sort, Quick Sort, Bucket Sort, Radix Sort .
Binary Search Algorithm .
Graph Algorithms:
Breadth First Search(BFS) - Its most popular usage is to find single source shortest path in unweighted graph .
Depth First Search(DFS) .
Note that, Checking Bipartiteness of an undirected graph have standard BFS and DFS based solutions which you should know. Also, either of them can be used to find connected components in an undirected graph.
Topological Sorting [lets you find shortest/longest paths in a DAG in linear time, can be used to solve problems where there are some dependencies/prerequisites and you are required to find a valid ordering]
Strongly Connected Components of directed graph
Finding Euler Path
Dijkstra's Algorithm - for single source shortest path in weighted graph .
Bellman-Ford Algorithm - for single source shortest path in weighted graph with negative edges.
Floyd-Warshall algorithm - for all pair shortest path .
Kruskal and Prim's algorithms - for finding minimum spanning tree .
Max Network Flow (Ford-Fulkerson Algorithm)
Knapsack Problem
Zero-Sum and Alpha-Beta Search
5. Solve by using Data-Structures
You should know how to use Array, Hash table, (Single and Doubly) Linked List traversal, Pre/Post/In order traversal of Binary [Search] tree, Stack and Queue.
Many a times a problem can be solved by inserting the input into one of these data structures and traversing(or retrieving data from) it in certain way.
I found Stack interesting in another way. Most of the problems that are solved by simple recursion are also solvable using Stack and it is no surprise as in case of recursion the stack is hidden in the programming language implementation.
Let me conclude by saying that above list of algorithms and data structures is by no means exhaustive. They are just the most important and basic ones which you should know in great detail including their implementation and proofs.
In my opinion, Part-II(Problem Solving) of AIMA consists of very important algorithms and problem solving techniques. They are mostly related to Graph search but, you will see that there are a lot of problems that can be reduced to Graph search. One should work through at least that part of the book at some point in his life.
Another thing, you should be comfortable with, is basic calculations of computing (time/memory) complexity, the Big-O notation and methods of solving recurrence relations(which come up when computing complexity of any recursive algorithm).
Next level would be to understand theory of NP completeness(and awareness of known hard problems e.g. traveling-salesman-problem and their approximate solutions). You might want to know about advanced data structures such as BTree, KDTree, Trie etc and other graph algorithms. But these, I believe, you don't need to understand in great detail but just the usage. It is impossible to remember all the algorithms. However, you need to be "aware" of as many known data structures and algorithms as possible.
Lastly, This is a journey.. farther you go, better you get.
[Update: July 25' 2011] Sometimes writing precise statement of the problem also helps.
Basically it means to describe your problem under following headings...
Problem Description
Input
Output
Constraints
[Update: July 28' 2011] Sometimes problem is easier(or more efficient) to solve when the input is *Sorted*( or *preprocessed* in general) .
Also there can be problems where finding a *Signature* helps. For example problems related to anagrams of a string are usually solved by finding the signature that is the count of individual characters in the word or just the lexicographical sort of the word.
[Update: Feb 3' 2013] When solving an algorithmic problems. You should convince yourself, with [in]formal proofs, of 3 things (in worst cases)
1. Your algorithm will always terminate.
2. It will always produce the correct solution.
3. What is the worst case running time? (should be polynomial)
However, when solving some NP-complete problem, then 2 can be relaxed in the sense that algorithm is good enough as long as it either computes approximately good solution(if you're ok with it) or correct solution to specific instances of the general problem, that you are interested in. This relaxation is must because, with very high probability, there is no efficient(..polynomial time) solution to general problem you're solving.
0. Solve by bruteforce(or backtracking)
If the problem size is small and bruteforce approach is ok, then do it and not worry too much about the efficient solution. Make sure you do some back of the envelop runtime cost calculations before you disregard bruteforce. In some problems, you might need an intelligent algorithm to solve a sub-problem and then a bruteforce approach to combine sub-problem solutions. This is especially true for some of the problems in code competitions.
now on to the ways of finding efficient solutions....
1. Solve by Example or solving problem instances of small sizes, n = 1,2,3..
Here we solve some example inputs to the problem, e.g. if the problem input is a number n, then I will try to solve it manually for n = 1,2,3,4... and see if a solution clicks in my mind. This same approach can sometimes lead to solution involving recursion(and dynamic programming) described later.
2. Solve by Simplification
Here We try to remove/add some constraints from/to the problem that simplify it, solve the simpler version or a different but similar problem and see if it can be used to solve/understand the original problem.
3. Solve by Recursion
"Thinking Recursively" is an art. Best way to "get" recursion is to practice and read the literature on functional programming where recursion is one of the key concepts. I highly recommend working through SICP and the "wishful thinking" concept described there. For example, to get factorial(n) you will think like, make a wish that someone gives you the factorial(n-1) then how will you get factorial(n) using that of (n-1). Be wishful !!
One of the things I "got" over time is that, for recursion to work It is not necessary that
f(n) = g(f(n-1))
but all of the following could work also
f(n) = g(f(n-1),f(n-2))
f(n) = g(f(n-1),f(n-2),f(n-3))
....
f(n) = g(f(n-1),f(n-2),...f(1),f(0))
3.1 Divide and Conquer(for example standard solution to merge-sort) is another powerful problem solving technique which uses recursion. Here, you solve the original problem by "merging" the solutions of two or more disjoint sub-problems(which are solved recursively).
3.2 Dynamic Programming is an optimization to improve running time after you have a recursive strategy. Draw the recursion tree and see if same sub-problem is being solved multiple times. That is, you will notice that total number of distinct sub-problems to be solved is much less than the total number of sub-problems being solved in straightforward recursive implementation. (In cormen et al, it is called the overlapping sub-problems property).
In such cases, a lot of, redundant computation is saved by caching the solution of various sub-problems and reusing them when required again.
Solution can be implemented either top down recursive with a table to cache the sub-problem solutions or a bottom-up iterative where you solve the smaller sub-problems first and then solve the bigger using solution of smaller sub-problems.
Some problems solved by dynamic programming are optimization problems and they exhibit optimal substructure property, that basically means that optimal solution to bigger problem "contains" optimal solution to the smaller sub-problems.
Most of the time, proof by induction is used here to prove the correctness of algorithm.
4. Solve using Greedy approach
It is a algorithm technique where making locally optimal/correct decisions, *sometimes*, leads to globally optimal/correct solutions. Usually, you can get idea of the solution by solving small size instances of the problem. However, this idea may or may not be correct so it is *essential* to prove that your locally optimal strategy gives you globally optimal results too.
In most of the cases following proof strategies work for greedy algorithms..
- proof by induction
- proof by contradiction: it is sometimes combined with, proof by exchange argument. Here you assume some optimal solution S* and a solution S produced by your greedy algorithm. Using, exchange of elements in S* so that exchange either preserves the optimality score or makes it better, you transform S* to S and that essentially proves that S is either better or equally good as S*. And hence, your greedy strategy works.
- Anything else :)
5. Solve by Reduction
Here we try to reduce the given problem to another problem whose solution is well-known and many of the code challenges problems are of this nature. Some of the algorithms, which come up very frequently, and you should know them by heart(including their proof, and if you have problem reading proofs then you need to work through How to Prove it!). Knowing them also means having their concise/optimal implementation in your [muscle] memory.
Sorting Algorithms - Index Sort, Merge Sort, Quick Sort, Bucket Sort, Radix Sort .
Binary Search Algorithm .
Graph Algorithms:
Breadth First Search(BFS) - Its most popular usage is to find single source shortest path in unweighted graph .
Depth First Search(DFS) .
Note that, Checking Bipartiteness of an undirected graph have standard BFS and DFS based solutions which you should know. Also, either of them can be used to find connected components in an undirected graph.
Topological Sorting [lets you find shortest/longest paths in a DAG in linear time, can be used to solve problems where there are some dependencies/prerequisites and you are required to find a valid ordering]
Strongly Connected Components of directed graph
Finding Euler Path
Dijkstra's Algorithm - for single source shortest path in weighted graph .
Bellman-Ford Algorithm - for single source shortest path in weighted graph with negative edges.
Floyd-Warshall algorithm - for all pair shortest path .
Kruskal and Prim's algorithms - for finding minimum spanning tree .
Max Network Flow (Ford-Fulkerson Algorithm)
Knapsack Problem
Zero-Sum and Alpha-Beta Search
5. Solve by using Data-Structures
You should know how to use Array, Hash table, (Single and Doubly) Linked List traversal, Pre/Post/In order traversal of Binary [Search] tree, Stack and Queue.
Many a times a problem can be solved by inserting the input into one of these data structures and traversing(or retrieving data from) it in certain way.
I found Stack interesting in another way. Most of the problems that are solved by simple recursion are also solvable using Stack and it is no surprise as in case of recursion the stack is hidden in the programming language implementation.
Let me conclude by saying that above list of algorithms and data structures is by no means exhaustive. They are just the most important and basic ones which you should know in great detail including their implementation and proofs.
In my opinion, Part-II(Problem Solving) of AIMA consists of very important algorithms and problem solving techniques. They are mostly related to Graph search but, you will see that there are a lot of problems that can be reduced to Graph search. One should work through at least that part of the book at some point in his life.
Another thing, you should be comfortable with, is basic calculations of computing (time/memory) complexity, the Big-O notation and methods of solving recurrence relations(which come up when computing complexity of any recursive algorithm).
Next level would be to understand theory of NP completeness(and awareness of known hard problems e.g. traveling-salesman-problem and their approximate solutions). You might want to know about advanced data structures such as BTree, KDTree, Trie etc and other graph algorithms. But these, I believe, you don't need to understand in great detail but just the usage. It is impossible to remember all the algorithms. However, you need to be "aware" of as many known data structures and algorithms as possible.
Lastly, This is a journey.. farther you go, better you get.
[Update: July 25' 2011] Sometimes writing precise statement of the problem also helps.
Basically it means to describe your problem under following headings...
Problem Description
Input
Output
Constraints
[Update: July 28' 2011] Sometimes problem is easier(or more efficient) to solve when the input is *Sorted*( or *preprocessed* in general) .
Also there can be problems where finding a *Signature* helps. For example problems related to anagrams of a string are usually solved by finding the signature that is the count of individual characters in the word or just the lexicographical sort of the word.
[Update: Feb 3' 2013] When solving an algorithmic problems. You should convince yourself, with [in]formal proofs, of 3 things (in worst cases)
1. Your algorithm will always terminate.
2. It will always produce the correct solution.
3. What is the worst case running time? (should be polynomial)
However, when solving some NP-complete problem, then 2 can be relaxed in the sense that algorithm is good enough as long as it either computes approximately good solution(if you're ok with it) or correct solution to specific instances of the general problem, that you are interested in. This relaxation is must because, with very high probability, there is no efficient(..polynomial time) solution to general problem you're solving.
No comments:
Post a Comment