csp unit 6 collegeboard

A student wants to determine whether a certain problem is undecidable. Which of the following will demonstrate that the problem is undecidable?

**A**

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.

**B**

Show that for one instance of the problem, no algorithm can be written that is capable of providing a correct yes-or-no answer.

**C**

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.

**D**

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.

Show that for one instance of the problem, no algorithm can be written that is capable of providing a correct yes-or-no answer

For which of the following lists can a binary search be used to search for an item in the list?

1. ["blue", "green", "jade", "mauve", "pink"]

2. [5, 5, 5, 5, 6, 7, 8, 8, 8]

3. [10, 5, 3, 2, -4, -8, -9, -12]

I, II, and III

The position of a runner in a race is a type of analog data. The runner’s position is tracked using sensors. Which of the following best describes how the position of the runner is represented digitally?

The position of the runner is sampled at regular intervals to approximate the real-word position, and a sequence of bits is used to represent each sample.

The owner of a clothing store records the following information for each transaction made at the store during a 7-day period.

• The date of the transaction

• The method of payment used in the transaction

• The number of items purchased in the transaction

• The total amount of the transaction, in dollars

Customers can pay for purchases using cash, check, a debit card, or a credit card.

Using only the data collected during the 7-day period, which of the following statements is true?

The total number of items purchased on a given date can be determined by searching the data for all transactions that occurred on the given date and then adding the number of items purchased for each matching transaction.

The list listOne is a sorted list of numbers that contains 700 elements. The list listTwo is a sorted list of numbers that contains 900 elements. Let *x* represent the maximum number of list elements that will need to be examined when performing a binary search for a value in listOne, and let *y* represent the maximum number of list elements that will need to be examined when performing a binary search for a value in listTwo. Which of the following statements about *x* and *y* is true?

The value of *x* is approximately equal to the value of *y*.

A certain programming language uses 4-bit binary sequences to represent nonnegative integers. For example, the binary sequence 0101 represents the corresponding decimal value 5. Using this programming language, a programmer attempts to add the decimal values 14 and 15 and assign the sum to the variable total. Which of the following best describes the result of this operation?

An overflow error will occur because 4 bits is not large enough to represent 29, the sum of 14 and 15.

A video game character can face toward one of four directions: north, south, east, and west. Each direction is stored in memory as a sequence of four bits. A new version of the game is created in which the character can face toward one of eight directions, adding northwest, northeast, southwest, and southeast to the original four possibilities. Which of the following statements is true about how the eight directions must be stored in memory?

Four bits are enough to store the eight directions.

A certain programming language uses 4-bit binary sequences to represent nonnegative integers. For example, the binary sequence 0101 represents the corresponding decimal value 5. Using this programming language, a programmer attempts to add the decimal values 14 and 15 and assign the sum to the variable total. Which of the following best describes the result of this operation?

An overflow error will occur because 4 bits is not large enough to represent 29, the sum of 14 and 15.

A video game character can face toward one of four directions: north, south, east, and west. Each direction is stored in memory as a sequence of four bits. A new version of the game is created in which the character can face toward one of eight directions, adding northwest, northeast, southwest, and southeast to the original four possibilities. Which of the following statements is true about how the eight directions must be stored in memory?

Four bits are enough to store the eight directions

In which of the following scenarios would a simulation be the LEAST beneficial?

**A**

An engineering company wants to test whether a change to a car design will negatively affect fuel efficiency.

**B**

An insurance company wants to study the effect of cold weather patterns on health-care costs.

**C**

A manufacturing company wants to determine whether using robots in its facility will increase productivity.

**D**

A retail company wants to determine the most popular item that was sold on the company’s Web site last month.

A retail company wants to determine the most popular item that was sold on the company’s Web site last month.

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?

**A**

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

**B**

Finding the fastest route that visits every location among nn locations, which requires n!n! possible routes be examined.

**C**

Performing a binary search for a score in a sorted list of nn scores, which requires that fewer than nn scores be examined.

**D**

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

Finding the fastest route that visits every location among nn locations, which requires n!n! possible routes be examined.

A user wants to save a data file on an online storage site. The user wants to reduce the size of the file, if possible, and wants to be able to completely restore the file to its original version. Which of the following actions best supports the user’s needs?

Compressing the file using a lossless compression algorithm before uploading it

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

Select two answers.

**A**

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

**B**

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

**C**

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

**D**

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

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

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

Which of the following is an advantage of a lossless compression algorithm over a lossy compression algorithm?

**A**

A lossless compression algorithm can guarantee that compressed information is kept secure, while a lossy compression algorithm cannot.

**B**

A lossless compression algorithm can guarantee reconstruction of original data, while a lossy compression algorithm cannot.

**C**

A lossless compression algorithm typically allows for faster transmission speeds than does a lossy compression algorithm.

**D**

A lossless compression algorithm typically provides a greater reduction in the number of bits stored or transmitted than does a lossy compression algorithm.

A lossless compression algorithm can guarantee reconstruction of original data, while a lossy compression algorithm cannot.

Consider the following numeric values.

• Binary 1011

• Binary 1101

• Decimal 5

• Decimal 12

Which of the following lists the values in order from least to greatest?

\n Decimal 5, binary 1011, decimal 12, binary 1101

A time stamp indicates the date and time that a measurement was taken. A data scientist has a list containing 10,000 time stamps, sorted in chronological order. Which of the following is closest to the maximum number of values that will need to be examined when performing a binary search for a value in the list?

15

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.

A sorted list of numbers contains 200 elements. Which of the following is closest to the maximum number of list elements that will need to be examined when performing a binary search for a particular value in the list?

8

Which of the following best explains how algorithms that run on a computer can be used to solve problems?

**A**

All problems can be solved with an algorithm that runs in a reasonable amount of time.

**B**

All problems can be solved with an algorithm, but some algorithms might need a heuristic to run in a reasonable amount of time.

**C**

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

**D**

Some problems cannot be solved by an algorithm.

Some problems cannot be solved by an algorithm

A city planner is using simulation software to study crowd flow out of a large arena after an event has ended. The arena is located in an urban city. Which of the following best describes a limitation of using a simulation for this purpose?

**A**

The model used by the simulation software cannot be modified once the simulation has been used.

**B**

The model used by the simulation software often omits details so that it is easier to implement.

**C**

Running a simulation requires more time to generate data from trials than observing the crowd exiting the arena at various events.

**D**

Running a simulation requires a large number of observations to be collected before it can be used to explore a problem.

The model used by the simulation software often omits details so that it is easier to implement.

Which of the following are true statements about the data that can be represented using binary sequences?

1. Binary sequences can be used to represent strings of characters.

2. Binary sequences can be used to represent colors.

3. Binary sequences can be used to represent audio recordings.

I, II, and III

Consider the 4-bit binary numbers 0011, 0110, and 1111. Which of the following decimal values is NOT equal to one of these binary numbers?

**A**3

**B**6

**C**9

**D**15

9