Test 2 Flashcards
For some problems, a top-down divide-and conquer decomposition results in smaller instances which are related , resulting in : .
Example : Fib Algorithm 1.6
Very inefficient solutions
In _____________, smaller instances solved first, the results are stored, and reused later if needed.
Dynamic Programming
Dynamic programming is a __________ approach that stores partial solutions , typically in an array .
“bottom-up”
Using the dynamic programming method:
- Establish a recursive property that gives the solution to an instance of the problem .
- Solve an instance of the problem in a bottom-up fashion by solving smaller instances first . In the process , store partial solutions.
To solve an optimization problem using dynamic programming, the principle of optimality must apply:
an optimal solution to an instance of a problem always contains optimal solutions to all subinstances.
When the principle of optimality applies , we can
- Establish a recursive property that gives the optimal solution to an instance of the problem ,
- Compute the value of an optimal solution in a bottom-up fashion ,
- Construct the optimal solution in a bottom-up fashion
The goal is to maximize the value that can hold at most a total weight W of goods from a set of items
Knapsack
To save a record of a knapsack problem you must:
To compute the actual subset, we add an auxiliary boolean array keep[i, w] which is true if the i ^ (th) item is kept in P[i, w] , false otherwise.
A greedy algorithm works in phases. At each phase :
You take the best you can get right now , without regard for future consequences (or past events )
You hope that by making a locally optimal choice at each step, you will end up with a globally optimal solution
algorithm starts with an empty “chosen” set and adds items to the set until a solution is obtained
greedy
Each iteration for greedy requires :
selection procedure: pick the next item that appears to be the “best “ according to a “ local “ criterion
feasibility check: determine if it is feasible to add the chosen item to the set within problem constraints
A solution check: do we have a solution to the problem ?
For optimization problems , greedy algorithms are often simpler and more efficient, but:
do not always produce optimal results
___________ programming produces optimal results provided that the principle of optimality applies.
Dynamic
Any problem that can be solved by a _______ algorithm can be solved by ________ programming , but not the other way around.
greedy
dynamic
If fractions of items are allowed , a greedy approach:
yields an optimal solution
If no fractions allowed , greedy approaches are ______________ to yield optimal solutions
not guaranteed
We can place objects or fractions of objects in the knapsack, as long as W:
is not exceeded
A minimum spanning tree is a spanning tree with _______ overall weight .
lowest
Numerous applications of this apllication: road construction, network cabling , etc.
Minimum spanning tree
Start by picking any vertex and adding it to the tree
Repeatedly: Pick any least- cost edge from a vertex in the tree to a vertex not in the tree, and add the edge and new vertex to the tree
Stop when all vertices have been added to the tree
Prim’s algorithm
uses the greedy approach to find the shortest paths from a given source to all other vertices in a graph.
Dijkstra’s algorithm
Dijkstra’s algorithm complexity is:
O(n ^ 2) complexity
