COMPUTER SCIENCE AND ENGINEERING
ALGORITHMS
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Show that for one instance of the problem, an algorithm can be written that is always capable of providing a correct yes-or-no answer.
|
|
|
Show that for one instance of the problem, no algorithm can be written that is capable of providing a correct yes-or-no answer.
|
|
|
Show that for one instance of the problem, a heuristic is needed to write an algorithm that is capable of providing a correct yes-or-no answer.
|
|
|
Show that for one instance of the problem, an algorithm that runs in unreasonable time can be written that is capable of providing a correct yes-or-no answer.
|
Detailed explanation-1: -A student wants to determine whether a certain problem is undecidable. Which of the following will demonstrate that the problem is undecidable? Show that for one instance of the problem, no algorithm can be written that is capable of providing a correct yes-or-no answer.
Detailed explanation-2: -Which of the following best explains the consequence of the problem being undecidable? There is no possible algorithm that can be used to solve all instances of the problem.
Detailed explanation-3: -Which of the following best describes the ability of parallel computing solutions to improve efficiency? Any problem that can be solved sequentially can be solved using a parallel solution in approximately half the time.
Detailed explanation-4: -Which of the following best explains how algorithms that run on a computer can be used to solve problems? All problems can be solved with an algorithm that runs in a reasonable amount of time. All problems can be solved with an algorithm, but some algorithms might need a heuristic to run in a reasonable amount of time.
Detailed explanation-5: -For which of the following situations would it be best to use a heuristic in order to find a solution that runs in a reasonable amount of time? Finding the fastest route that visits every location among n locations, which requires n! possible routes be examined.