Types of Algorithms
Material adapted – courtesy of
Prof. Dave Matuszek at UPENN
Algorithm classification
Algorithms that use a similar problem-solving approach
can be grouped together
This classification scheme is neither exhaustive nor
disjoint
The purpose is not to be able to classify an algorithm as
one type or another, but to highlight the various ways in
which a problem can be attacked
1
A short list of categories
Algorithm types we will consider include:
Simple recursive algorithms
Divide and conquer algorithms
Dynamic programming algorithms
Greedy algorithms
Brute force algorithms
Randomized algorithms
Note: we may even classify algorithms based on the
type of problem they are trying to solve – example
sorting algorithms, searching algorithms etc.
Simple recursive algorithms I
A simple recursive algorithm:
Solves the base cases directly
Recurs with a simpler subproblem
Does some extra work to convert the solution to the simpler
subproblem into a solution to the given problem
We call these “simple” because several of the other
algorithm types are inherently recursive
2
Example recursive algorithms
To count the number of elements in a list:
If the list is empty, return zero; otherwise,
Step past the first element, and count the remaining elements
in the list
Add one to the result
To test if a value occurs in a list:
If the list is empty, return false; otherwise,
If the first thing in the list is the given value, return true;
otherwise
Step past the first element, and test whether the value occurs
in the remainder of the list
Backtracking algorithms
Backtracking algorithms are based on a depth-first*
recursive search
A backtracking algorithm:
Tests to see if a solution has been found, and if so, returns it;
otherwise
For each choice that can be made at this point,
Make that choice
Recur
If the recursion returns a solution, return it
If no choices remain, return failure
*We will cover depth-first search very soon (once we get to
tree-traversal and trees/graphs).
6
3
Divide and Conquer
A divide and conquer algorithm consists of two parts:
Divide the problem into smaller subproblems of the same
type, and solve these subproblems recursively
Combine the solutions to the subproblems into a solution to
the original problem
Traditionally, an algorithm is only called “divide and
conquer” if it contains at least two recursive calls
Examples
Quicksort:
Partition the array into two parts (smaller numbers in one
part, larger numbers in the other part)
Quicksort each of the parts
No additional work is required to combine the two sorted
parts
Another example is Mergesort
Not yet reviewed in class (we can do so if time permits)
Cut the array in half, and mergesort each half
Combine the two sorted arrays into a single sorted array by merging
them
4
Binary tree lookup
Here’s how to look up something in a sorted binary tree:
Compare the key to the value in the root
If the two values are equal, report success
If the key is less, search the left subtree
If the key is greater, search the right subtree
This is not a divide and conquer algorithm because,
although there are two recursive calls, only one is used
at each level of the recursion
Fibonacci numbers
To find the nth Fibonacci number:
If n is zero or one, return one; otherwise,
Compute fibonacci(n-1) and fibonacci(n-2)
Return the sum of these two numbers
10
5
Dynamic programming algorithms
A dynamic programming algorithm remembers past results
(“memoization”) and uses them to find new results
Dynamic programming is generally used for optimization
problems
Multiple solutions exist, need to find the “best” one
Requires “optimal substructure” and “overlapping subproblems”
Optimal substructure: Optimal solution contains optimal solutions to
subproblems
Overlapping subproblems: Solutions to subproblems can be stored and reused
in a bottom-up fashion
This differs from Divide and Conquer, where subproblems
generally need not overlap
11
Fibonacci numbers again
To find the nth Fibonacci number:
If n is zero or one, return one; otherwise,
Compute, or look up in a table, fibonacci(n-1) and
fibonacci(n-2)
Find the sum of these two numbers
Store the result in a table and return it
Since finding the nth Fibonacci number involves finding
all smaller Fibonacci numbers, the second recursive call
has little work to do (this is easiest observed by drawing
the tree out)
The table may be preserved and used again later
12
6
Greedy algorithms
An optimization problem is one in which you want to
find, not just a solution, but the best solution
A “greedy algorithm” sometimes works well for
optimization problems
A greedy algorithm works in phases: At each phase:
You take the best you can get right now, without regard for
future consequences
You hope that by choosing a local optimum at each step, you
will end up at a global optimum
13
Brute force algorithm
A brute force algorithm simply tries all possibilities
until a satisfactory solution is found
Such an algorithm can be:
Optimizing: Find the best solution. This may require finding all
solutions, or if a value for the best solution is known, it may stop
when any best solution is found
Example: Finding the best path for a traveling salesman
Satisficing: Stop as soon as a solution is found that is good enough
Example: Finding a traveling salesman path that is within 10%
of optimal
14
7
Improving brute force algorithms
Often, brute force algorithms require exponential time
Various heuristics and optimizations can be used
Heuristic: A “rule of thumb” that helps you decide which
possibilities to look at first
Optimization: In this case, a way to eliminate certain
possibilities without fully exploring them
15
Randomized algorithms
A randomized algorithm uses a random number at
least once during the computation to make a decision
Example: In Quicksort, using a random number to choose a
pivot
Example: Trying to factor a large number by choosing
random numbers as possible divisors
16
8
More on Dynamic Programming
Recall Recursion…
The function that does the work calls itself to solve a smaller
version of its input successively.
Need a base case to terminate!
Solutions look very terse and elegant
Common examples (especially for programming interviews)
include factorial/fibonacci
But think about it…every call falls on a Stack…this approach is
memory intensive
Furthermore, it doesn’t take into account the ability to avoid
repeated operations.
18
9
Counting coins
To find the minimum number of US coins to make any amount,
the greedy method always works
At each step, just choose the largest coin that does not overshoot the
desired amount: 31¢=25
The greedy method would not work if we did not have 5¢ coins
For 31 cents, the greedy method gives seven coins (25+1+1+1+1+1+1),
but we can do it with four (10+10+10+1)
The greedy method also would not work if we had a 21¢ coin
For 63 cents, the greedy method gives six coins (25+25+10+1+1+1), but
we can do it with three (21+21+21)
How can we find the minimum number of coins for any given
coin set?
19
A dynamic programming solution
Idea: Solve first for one cent, then two cents, then three cents,
etc., up to the desired amount
Save each answer in an array !
For each new amount N, compute all the possible pairs of
previous answers which sum to N
For example, to find the solution for 13¢,
First, solve for all of 1¢, 2¢, 3¢, ..., 12¢
Next, choose the best solution among:
Solution for 1¢ + solution for 12¢
Solution for 2¢ + solution for 11¢
Solution for 3¢ + solution for 10¢
Solution for 4¢ + solution for 9¢
Solution for 5¢ + solution for 8¢
Solution for 6¢ + solution for 7¢
20
10
Example
Suppose coins are 1¢, 3¢, and 4¢
There’s only one way to make 1¢ (one coin)
To make 2¢, try 1¢+1¢ (one coin + one coin = 2 coins)
To make 3¢, just use the 3¢ coin (one coin)
To make 4¢, just use the 4¢ coin (one coin)
To make 5¢, try
1¢ + 4¢ (1 coin + 1 coin = 2 coins)
2¢ + 3¢ (2 coins + 1 coin = 3 coins)
The first solution is better, so best solution is 2 coins
To make 6¢, try
1¢ + 5¢ (1 coin + 2 coins = 3 coins)
2¢ + 4¢ (2 coins + 1 coin = 3 coins)
3¢ + 3¢ (1 coin + 1 coin = 2 coins) – best solution
Etc.
21
Comparison with divide-and-conquer
Divide-and-conquer algorithms split a problem into separate
subproblems, solve the subproblems, and combine the results for
a solution to the original problem
Example: Quicksort, Mergesort, Binary Search
Divide-and-conquer algorithms can be thought of as top-down
algorithms
In contrast, a dynamic programming algorithm proceeds by
solving small problems, remembering the results, then combining
them to find the solution to larger problems
Dynamic programming can be thought of as bottom-up
22
11
Example 2: Binomial Coefficients
(x + y)2 = x2 + 2xy + y2, coefficients are 1,2,1
(x + y)3 = x3 + 3x2y + 3xy2 + y3, coefficients are 1,3,3,1
(x + y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4,
coefficients are 1,4,6,4,1
(x + y)5 = x5 + 5x4y + 10x3y2 + 10x2y3 + 5xy4 + y5,
coefficients are 1,5,10,10,5,1
The n+1 coefficients can be computed for (x + y)n according to
the formula c(n, i) = n! / (i! * (n – i)!)
for each of i = 0..n
The repeated computation of all the factorials gets to be expensive
We can use dynamic programming to save the factorials as we go
23
Solution by dynamic programming
n c(n,0) c(n,1) c(n,2) c(n,3) c(n,4) c(n,5) c(n,6)
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
Each row depends only on the preceding row
This algorithm is known as Pascal’s Triangle
24
12
The principle of optimality, I
Dynamic programming is a technique for finding an
optimal solution
The principle of optimality applies if the optimal
solution to a problem always contains optimal solutions
to all subproblems
Example: Consider the problem of making N¢ with the
fewest number of coins
Either there is an N¢ coin, or
The set of coins making up an optimal solution for N¢ can be
divided into two nonempty subsets, n1¢ and n2¢
If either subset, n1¢ or n2¢, can be made with fewer coins, then clearly
N¢ can be made with fewer coins, hence solution was not optimal
25
The principle of optimality, II
The principle of optimality holds if
Every optimal solution to a problem contains...
...optimal solutions to all subproblems
The principle of optimality does not say
If you have optimal solutions to all subproblems...
...then you can combine them to get an optimal solution
Example: In US coinage,
The optimal solution to 7¢ is 5¢ + 1¢ + 1¢, and
The optimal solution to 6¢ is 5¢ + 1¢, but
The optimal solution to 13¢ is not 5¢ + 1¢ + 1¢ + 5¢ + 1¢
But there is some way of dividing up 13¢ into subsets with
optimal solutions (say, 11¢ + 2¢) that will give an optimal
solution for 13¢
Hence, the principle of optimality holds for this problem
26
13
The 0-1 knapsack problem
A thief breaks into a house, carrying a knapsack...
He can carry up to 25 pounds of loot
He has to choose which of N items to steal
Each item has some weight and some value
“0-1” because each item is stolen (1) or not stolen (0)
He has to select the items to steal in order to maximize the value of his
loot, but cannot exceed 25 pounds
A greedy algorithm does not find an optimal solution
A dynamic programming algorithm works well
This is similar to, but not identical to, the coins problem
In the coins problem, we had to make an exact amount of change
In the 0-1 knapsack problem, we can’t exceed the weight limit, but the
optimal solution may be less than the weight limit
The dynamic programming solution is similar to that of the coins problem
27
Comments
Dynamic programming relies on working “from the bottom up”
and saving the results of solving simpler problems
These solutions to simpler problems are then used to compute the solution
to more complex problems
Dynamic programming is used for optimization problems,
especially ones that would otherwise take exponential time
Only problems that satisfy the principle of optimality are suitable for
dynamic programming solutions
Since exponential time is unacceptable for all but the smallest
problems, dynamic programming is sometimes essential
28
14
The End
29
15