Please show how you determined an answer(s) for credit. Thank You. Which of the

Question

Please show how you determined an answer(s) for credit. Thank You.

Which of the following can be said to be typical attributes of a backtracking algorithm?

Choose an ANSWER or ANSWERS below (there can be more than one correct answer)

divides large problems up into smaller sub-problems

exponential time complexity

uses a data structure to avoid recursion

works from smaller sub-problems towards a larger solution

guesses what the answer might be and then checks to see if the guess was correct.

can be implemented recursively or iteratively

Explanation / Answer

Guesses what the answer might be and then checks to see if the guess was correct: Backtracking algorithm tries different solutions until correct solution is arrived. Backtracking algorithms are mostly used in constraint satisfaction problem where it there are multiple possibilities of finding solutions and Naive's approach is to be used to find all the solutions.

Exponential time complexity: Since backtracking does not follow a deterministic path, it often ends up running exponentially in order to derive the correct solution.

Divides large problems up into smaller sub-problems: It generate possible candidate solutions(of sub-problems) and work upon them to build the final solution.

Can be implemented recursively or iteratively: Yes algorithm of this class can be implemented both recursively and iteratively. For example in constraint satisfaction problem, one starts with an empty item and keep on adding the items to the solution using reucsion or loop if the item being added does not violate the rules of the system.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.