a. Compute the next level in the search tree.

b. If depth first search is applied in this problem, the solution found would have ______ nickels (5 cents each), ______ dimes (10 cents each), ______ quarters (25 cents each), if depth first search is applied (to the entire tree) in this problem.

c. If breadth first search is applied in this problem, the solution found would have ______ nickels (5 cents each), ______ dimes (10 cents each), ______ quarters (25 cents each).

d. How much memory would be used by depth first search?

e. How much memory would be used by breadth first search?

You are given an unlimited number of coins consisting of nickels (5 cents) dimes (10 cents) and quarters (25 cents). Your task is to get 30 cents with as few coins as possible. This problem can be described as search, where the decision in each level of the search tree is what coin to choose next. The first two levels of the search tree are shown below, where a left branch indicates a choice of a nickel (5 cents) a center branch indicates the choice of a dime, and a right branch indicates the choice of a quarter. The number written in each node is the total amount.

Transcribed image text