3.17/18_4.1_formative

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?

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

• 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 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, 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, no algorithm can be written 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.

Which of the following best explains how messages are typically transmitted over the Internet?

• The message is broken into packets that are transmitted in a specified order. Each packet must be

  received in the order it was sent for the message to be correctly reassembled by the recipient’s device.

• The message is broken into packets. The packets can be received in any order and still be reassembled

  by the recipient’s device.

• The message is broken into two packets. One packet contains the data to be transmitted and the other

  packet contains metadata for routing the data to the recipient’s device.

• The message is transmitted as a single file and received in whole by the recipient’s device.

Which of the following is a primary reason for the use of open protocols on the Internet?

• Open protocols ensure that all Internet users are provided connections with equal bandwidth.

• Open protocols ensure that all data transmission on the Internet is kept secure.

• Open protocols provide a way to standardize data transmission between different devices.

• Open protocols allow devices to specify how data packets are to be routed on the Internet in advance.

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.

• Appending a value to a list of N elements, which requires no list elements 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.

Which of the following is a benefit of using a simulation instead of an experiment to make a prediction?

• A simulation allows investigation of a phenomenon without the real-world limitations on time, safety,

  or budget.

• A simulation always produces the same output, so its results can be verified.

• A simulation produces results that are more accurate than experimental results.

• A simulation can be used to model real-world events that are impractical for experiments.

Which of the following best describes the relationship between the World Wide Web and the Internet?

• The World Wide Web is a protocol that is accessed using a data stream called the Internet.

• The World Wide Web is a system of linked pages, programs, and files that is accessed using a data

  stream called the Internet.

• The World Wide Web is a system of linked pages, programs, and files that is accessed via a network

  called the Internet.

• The World Wide Web is a Web site that is accessed using a protocol called the Internet.