Algorithms

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?

• Appending a value to a list of n elements, which requires no list elements be examined.

• Finding the fastest route that visits every location among n

  locations, which requires n! possible routes be examined.

• Performing a binary search for a score in a sorted list of n

  scores, which requires that fewer than n

  scores be examined.

• Performing a linear search for a name in an unsorted database of n people, which requires that up to n entries be examined.

A graphic artist uses a program to draw geometric shapes in a given pattern. The program uses an algorithm that draws the shapes based on input from the artist. The table shows the approximate number of steps the algorithm takes to draw different numbers of shapes.

Based on the values in the table, which of the following best characterizes the algorithm for drawing n shapes, where n is a very large number?

• The algorithm runs in a reasonable amount of time because it will use approximately n steps to draw n shapes.

• The algorithm runs in a reasonable amount of time because it will use approximately n^2 steps to draw n shapes.

• The algorithm runs in an unreasonable amount of time because it will use approximately n steps to draw n shapes.

• The algorithm runs in an unreasonable amount of time because it will use approximately n^2 steps to draw n shapes.

A computer scientist is analyzing four different algorithms used to sort a list. The table below shows the number of steps each algorithm took to sort lists of different sizes.

Based on the values in the table, which of the algorithms appear to run in reasonable time?

Select two answers.

• Algorithm A

• Algorithm B

• Algorithm C

• Algorithm D

A team of programmers is designing software. One portion of the project presents a problem for which there is not an obvious solution. After some research, the team determines that the problem is undecidable. Which of the following best explains the consequence of the problem being undecidable?

• The problem can be solved algorithmically, but it will require an unreasonably long amount of time.

• The problem can be solved algorithmically, but it will require an unreasonably large amount of data storage.

• There is no possible algorithm that can be used to solve all instances of the problem.

• There are several different possible algorithms that can solve the problem, but there is controversy about which is the most efficient.

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, 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.

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.

• All problems can be solved with an algorithm, but some algorithms might run in an unreasonable amount of time.

• Some problems cannot be solved by an algorithm.