Test 2

Question 1

For some problems, a top-down divide-and conquer decomposition results in smaller instances which are related , resulting in : .

Example : Fib Algorithm 1.6

Answer 1

Very inefficient solutions

Question 2

In _____________, smaller instances solved first, the results are stored, and reused later if needed.

Answer 2

Dynamic Programming

Question 3

Dynamic programming is a __________ approach that stores partial solutions , typically in an array .

Answer 3

“bottom-up”

Question 4

Using the dynamic programming method:

Answer 4

1. Establish a recursive property that gives the solution to an instance of the problem .
2. Solve an instance of the problem in a bottom-up fashion by solving smaller instances first . In the process , store partial solutions.

Question 5

To solve an optimization problem using dynamic programming, the principle of optimality must apply:

Answer 5

an optimal solution to an instance of a problem always contains optimal solutions to all subinstances.

Question 6

When the principle of optimality applies , we can

Answer 6

1. Establish a recursive property that gives the optimal solution to an instance of the problem ,
2. Compute the value of an optimal solution in a bottom-up fashion ,
3. Construct the optimal solution in a bottom-up fashion

Question 7

The goal is to maximize the value that can hold at most a total weight W of goods from a set of items

Answer 7

Knapsack

Question 8

To save a record of a knapsack problem you must:

Answer 8

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.

Question 9

A greedy algorithm works in phases. At each phase :

Answer 9

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

Question 10

algorithm starts with an empty “chosen” set and adds items to the set until a solution is obtained

Answer 10

greedy

Question 11

Each iteration for greedy requires :

Answer 11

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 ?

Question 12

For optimization problems , greedy algorithms are often simpler and more efficient, but:

Answer 12

do not always produce optimal results

Question 13

___________ programming produces optimal results provided that the principle of optimality applies.

Answer 13

Dynamic

Question 14

Any problem that can be solved by a _______ algorithm can be solved by ________ programming , but not the other way around.

Answer 14

greedy

dynamic

Question 15

If fractions of items are allowed , a greedy approach:

Answer 15

yields an optimal solution

Question 16

If no fractions allowed , greedy approaches are ______________ to yield optimal solutions

Answer 16

not guaranteed

Question 17

We can place objects or fractions of objects in the knapsack, as long as W:

Answer 17

is not exceeded

Question 18

A minimum spanning tree is a spanning tree with _______ overall weight .

Answer 18

lowest

Question 19

Numerous applications of this apllication: road construction, network cabling , etc.

Answer 19

Minimum spanning tree

Question 20

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

Answer 20

Prim’s algorithm

Question 21

uses the greedy approach to find the shortest paths from a given source to all other vertices in a graph.

Answer 21

Dijkstra’s algorithm

Question 22

Dijkstra’s algorithm complexity is:

Answer 22

O(n ^ 2) complexity