finals/katapusan sa DAA

the straight forward design technique applicable to variety of applications; suggests constructing a solution through a sequence of steps, each expanding a partially constructed solution obtained so far, until a complete solution to the problem is reached

• greedy method
• algorithm
• system

it has to satisfy the problem's constraints

• feasible
• locally optimal
• irrevocable

it has to be the best local choice among all feasible choices available on that step

• feasible
• locally optimal
• irrevocable

once made, it cannot be changed on subsequent stepsof the algorithm

• feasible
• locally optimal
• irrevocable

Solution for coin change problem using greedy algorithm is very intuitive and called as

• greedy method
• cashier's algorithm
• knapsack

If a set of items are given, each with a weight and a value, the goal is to select a subset of the items that maximises the value while keeping the total weight below or equal to a given limit.

• fractional knapsack
• job sequencing with deadlines
• 0/1 knapsack

the items are either completely or no items are filled in a knapsack.

• fractional knapsack
• job sequencing with deadlines
• 0/1 knapsack

A ___ of a connected graph is its connected acyclic subgraph (i.e., a tree) that contains all the vertices of the graph.

• fractional knapsack
• job sequencing with deadlines
• 0/3 knapsack

the straight forward design technique applicable to variety of applications

• spanning tree
• algorithm
• system

A ___ of a weighted connected graph is its spanning tree of the smallest weight

• maximum spanning tree
• weight
• minimum spanning tree