1) We mentioned in class that dynamic programming and greedy algorithms can only be used to solve problems that exhibit
Posted: Tue Jul 12, 2022 8:09 am
1) We mentioned in class that dynamic programming and greedyalgorithms can only be used to solve problems that exhibitrecursive substructure. Do Divide and Conquer algorithms requirethe problem to exhibit recursive substructure as well, or could weuse Divide and Conquer to solve problems that do not exhibitrecursive substructure?
2) Let’s say that for some problem you have come up with adynamic programming algorithm to solve that problem, and a greedyalgorithm to solve that same problem. You know both algorithms arecorrect, and as is nearly always the case, your greedy algorithm isasymptotically faster than the Dynamic Programming solution. Nameone reason why you might prefer to use the Dynamic Programmingalgorithm over the greedy algorithm
3) The Greedy Choice Function is the rule used to make eachselection in a greedy algorithm. When we prove the correctness ofour greedy algorithm we seek to show that the choice designated bythe greedy choice function is a component of some correct solution.Why do we not instead show that optimal solutions must use thegreedy choice?
2) Let’s say that for some problem you have come up with adynamic programming algorithm to solve that problem, and a greedyalgorithm to solve that same problem. You know both algorithms arecorrect, and as is nearly always the case, your greedy algorithm isasymptotically faster than the Dynamic Programming solution. Nameone reason why you might prefer to use the Dynamic Programmingalgorithm over the greedy algorithm
3) The Greedy Choice Function is the rule used to make eachselection in a greedy algorithm. When we prove the correctness ofour greedy algorithm we seek to show that the choice designated bythe greedy choice function is a component of some correct solution.Why do we not instead show that optimal solutions must use thegreedy choice?