CSCE 411 Lecture 12

Lecture Slides

« previous | Friday, September 21, 2012 | next »

Design Paradigms

• Dynamic Programming
• Greedy
• Divide-and-Conquer

When can one successfully use one of these algoritm design paradigms to solve a problem?

Read Chapters 2–4, 15, 16

Dynamic Programming

Developing an algorithm can be subdivided into the following steps:

1. Characterize structure of optimal solution
2. Recursively define value of optimal solution (find base/stop case)
3. Compute value of optimal solution in a bottom-up fashion (start with what we know from stop cases)
4. Construct optimal solution from computed information

Look at optimal substructure (optimal solution to problem must have something to do with optimal solutions to subproblems)

Overlapping subproblems: recursive algorithm revisits the same problem several times.

Note: If recursive algorithm to solve the problem creates new subproblems, try using #Divide-and-Conquer

(Chapter 15)

Greedy Algorithms

Development can be subdivided into following steps:

1. Cast optimization problem as one in which we make a choice and are left with one subproblem to solve
2. Prove that there is always an optimal solution to the original problem that makes the greedy choice, so the greedy chaice is always safe.
3. Prove that, having made the greedy choice, what remains is a subproblem that can also be solved greedily

Optimal substructure and greedy property.

(Chapter 16)

Divide-and-Conquer

Recursive algorithm to solve the problem creates new subproblems of the same type.

1. break up problem into subproblems
2. recursively break subproblems to a stop case
3. combine solutions of subproblems bottom-up

(Chapter 2)