In regards to greedy algorithms, which of the following statements are true (select all that apply)? A greedy algorithm will backtrack when it finds a suboptimal solution. Agreedy algorithm constructs a solution by choosing the best option at the moment. A greedy algorithm tends to be very efficient. 2 points In order for a Greedy Strategy to be correct it must be guaranteed to produce an optimal solution for any inpu True False

In regards to greedy algorithms, which of the following statements are true (select all that apply)? A greedy algorithm will backtrack when it finds a suboptimal solution. Agreedy algorithm constructs a solution by choosing the best option at the moment. A greedy algorithm tends to be very efficient. 2 points In order for a Greedy Strategy to be correct it must be guaranteed to produce an optimal solution for any inpu True False

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Choose the correct answer for the question below: A greedy algorithm for a given problem: 1.Always makes the choice that results in the most efficient space complexity 2.Always makes a locally-optimal choice in the hope that this choice will lead to a globally optimal solution, and never goes back to reverse the decision. 3.Always makes a locally-optimal choice but goes back and re-selects the same element in case the choice was sub-optimal. 4.Always makes the choice that results in the most efficient time complexity
Question 1: A greedy algorithm is a simple, intuitive algorithm that is used in optimization problems. The algorithm makes the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem, means it does not intend to find the best solution, but it terminates in a reasonable number of steps finding an optimal solution to such a complex problem typically requires unreasonably many steps. Briefly explain why is Dijkstra's shortest path algorithm considered as greedy?
For an optimization problem which of the following is/are the property/properties that must hold for a greedy algorithm to work? select all that apply
Algorithm A search using the heuristic h(n) = α for some fixed constant α > 0 is guaranteed to find an optimal solution Select one: True False
The best sequence is list of actions, called solution problem Path search The Optimal solution is : * a path from the initial state to a state satisfying the goal test This process of looking for the best sequence is called the solution with lowest path cost among all solutions none
Does a greedy algorithm always find an optimal solution? Justify your answer.
Constructing an Optimal Solution:algorithm ParsingWithAdvice(G, Th, ai, ... , aj, birdAdvice) pre- & post-cond: Same as Parsing except with advice.
(a) Design a greedy algorithm to make change for n cents using the least number of coins among quarters(25), dimes (10), nickels (5), and pennies (1). Fully explain your algorithm.For example, if n = 91, your algorithm must return 6, since we can make change for 91 cents using6 coins: Take 3 quarters, 1 dime, 1 nickel, and 1 penny. Also, we can show that it is not possible tomake change for 91 cents using less than 6 coins. (b) Show that your algorithm in part (a) outputs a correct result for all positive integers n.
Is it true that a greedy algorithm always finds the best solution? Justify your response.
Consider the following computer game: you have found some items of distinct values. On each turn you take one of these items while the values of the remaining items are multiplied by a factor D where D>1. On the next turn, you take one of the remaining items and also the other items are multiplied by D, this continues until no items are remaining. Find an optimal greedy strategy that gets the maximum score you can get. Write a pseudecode for a greedy strategy that gets the maximum score. What is the complexity of your algorithm?? What is the output of your algorithm if the input values are {your birth day, your birth month, last two digits of your birth year}, and D = 2. For example if the values are {2, 5, 3}, D=2 and you choose to get them in the given order your score will be like this: • After the first iteration your score is 2 and the remaining values are {10, 6}. • After the second iteration your score is 12 and the remaining values are {12} • After the last iteration your score…
Consider the following computer game: you have found some items of distinct values. On each turn you take one of these items while the values of the remaining items are multiplied by a factor D where D>1. On the next turn, you take one of the remaining items and also the other items are multiplied by D, this continues until no items are remaining. Find an optimal greedy strategy that gets the maximum score you can get. Write a pseudecode for a greedy strategy that gets the maximum score. What is the complexity of your algorithm?? What is the output of your algorithm if the input values are {your birth day, your birth month, last two digits of your birth year}, and D = 2. For example if the values are {2, 5, 3}, D=2 and you choose to get them in the given order your score will be like this: • After the first iteration your score is 2 and the remaining values are {10, 6}.
Let A = {a1, a2, ..., an} and be a set of n positive integer and let T be another integer. Design a dynamic programming algorithm that determines whether there exists a subset of A whose total sum is exactly T. Analyze the time complexity of your solution. For instance, if A = 4, 5, 17, 23, 11, 2 and T = 35 the algorithm should return True because the subset 5, 17, 11, 2 sums to 35. For the same set of numbers if we choose T = 31 the problem has no solution, and the algorithm will return False. When designing the dynamic programming algorithm, please describe the size and dimensionality of the dynamic programming table, and explicitly formulate the recurrence relationship.