CmSc 250 Intro to Algorithms
Algorithm Design Paradigms
Algorithm Design Paradigms: General approaches to the construction of efficient solutions to problems.
Such methods are of interest because:
Although more than one technique may be applicable to a specific problem, it is often the case that an algorithm constructed by one approach is clearly superior to equivalent solutions built using alternative techniques.
Paul E. Dunne,
Brute force is a straightforward approach to solve a problem based on the problem’s statement and definitions of the concepts involved. It is considered as one of the easiest approach to apply and is useful for solving small – size instances of a problem.
Some examples of brute force
Exhaustive search: Traveling Salesman Problem, Knapsack problem.
The solution is constructed through a sequence of steps, each expanding a partially constructed solution obtained so far. At each step the choice must be locally optimal – this is the central point of this technique.
Shortest distance in graphs
Greedy algorithm for the Knapsack problem
The coin exchange problem
Huffman trees for optimal encoding
Greedy techniques are mainly used to solve optimization problems. They do not always give the best solution.
Consider the knapsack problem with a knapsack of capacity 10 and 4 items given by the < weight :value> pairs: <5:6>, <4:3>, <3: 5>, <3: 4>. The greedy algorithm will choose item1 <5:6> and then item3 <3:5> resulting in total value 11, while the optimal solution is to choose items 2, 3, and 4 thus obtaining total value 12.
It has been proven that greedy algorithms for the minimal spanning tree, the shortest paths, and Huffman codes always give the optimal solution.
These are methods of designing algorithms that (informally) proceed as follows:
Given an instance of the problem to be solved, split this into several smaller sub-instances (of the same problem), independently solve each of the sub-instances and then combine the sub-instance solutions so as to yield a solution for the original instance.
With the divide-and-conquer method the size of the problem instance is reduced by a factor (e.g. half the input size), while with the decrease-and-conquer method the size is reduced by a constant.
Examples of divide-and-conquer algorithms:
Binary search in a sorted array (recursion)
Mergesort algorithm, Quicksort algorithm (recursion)
The algorithm for solving the fake coin problem (recursion)
Examples of decrease-and-conquer algorithms:
Binary Tree traversals: inorder, preorder and postorder (recursion)
Computing the length of the longest path in a binary tree (recursion)
Computing Fibonacci numbers (recursion)
Reversing a queue (recursion)
Warshall’s algorithm (recursion)
The issues here are two:
The answer to the second question depends on the nature of the problem.
In most cases the answer to the first question is: using the same method. Here another very important issue arises: when to stop decreasing the problem instance, i.e. what is the minimal instance of the given problem and how to solve it.
When we use recursion, the solution of the minimal instance is called “terminating condition”
One disadvantage of using Divide-and-Conquer is that the process of recursively solving separate sub-instances can result in the same computations being performed repeatedly since identical sub-instances may arise.
The idea behind dynamic programming is to avoid this pathology by obviating the requirement to calculate the same quantity twice.
The method usually accomplishes this by maintaining a table of sub-instance results.
Dynamic Programming is a Bottom-Up Technique in which the smallest sub-instances are explicitly solved first and the results of these used to construct solutions to progressively larger sub-instances.
In contrast, Divide-and-Conquer is a Top-Down Technique which logically progresses from the initial instance down to the smallest sub-instance via intermediate sub-instances.
Warshall’s algorithm implemented by iterations
These methods work as two-stage procedures. First, the problem is modified to be more amenable to solution. In the second stage the problem is solved.
Types of problem modifications
The method is used for state-space search problems. State-space search problems are problems, where the problem representation consists of:
The solving process solution is based on the construction of a
state-space tree, whose nodes represent
states, the root represents the initial state, and one or more leaves are goal
states. Each edge is labeled with some operator.
Backtracking uses depth-first search usually without cost function. The main algorithm is as follows:
The utility function is used to tell how close is a given state to the goal state and whether a given state may be considered a goal state.
If no children can be generated from a given node, then we backtrack – read the next node from the stack.
Example: The following problems can be solved using state-space search techniques:
We have to decide:
For the example:
More on backtracking.
Branch and bound is used when we can evaluate each node using the cost and utility functions. At each step we choose the best node to proceed further. Branch-and bound algorithms are implemented using a priority queue. The state-space tree is built in a breadth-first manner.
Example: the 8-puzzle problem. The cost function is the number of moves. The utility function evaluates how close is a given state of the puzzle to the goal state, e.g. counting how many tiles are not in place.
Genetic algorithms (GAs) are used mainly for optimization problems for which the exact algorithms are of very low efficiency.
GAs search for good solutions to a problem from among a (large) number of possible solutions. The current set of possible solutions is used to generate a new set of possible solution.
They start with an initial set of possible solutions, and at each step they do the following:
The loop runs until a specified condition becomes true, e.g. a solution is found that satisfies the criteria for a “good” solution, or the number of iterations exceeds a given value, or no improvement ahs been recorded when evaluation the solutions.
Key issues here are:
Using the terminology above, we can outline the algorithms to obtain one generation:
The traveling salesman problem
Usually a given problem can be solved using various approaches however it is not wise to settle for the first that comes to mind. More often than not, some approaches result in much more efficient solutions than others. Consider again the Fibonacci numbers computed recursively using the decrease-and-conquer approach, and computed by iterations using dynamic programming. In the first case the complexity is O(2n), while in the second case the complexity is O(n). On the other hand, consider sorting based on decrease-and-conquer (insertion sort) and brute force sorting. For almost sorted files insertion sort will give almost linear complexity, while brute force sorting algorithms have quadratic complexity.
The basic question here is: How to choose the approach? First, by understanding the problem, and second, by knowing various problems and how they are solved using different approaches. Strongly recommended reading to learn more about how to design algorithms:The Algorithm Design Manual
Steven S. Skiena
Department of Computer Science
State University of New York
Back to Contents page
Created by Lydia Sinapova