AP CSP - Unit Algorithms (2)

A mathematician comes up with an algorithm to search a matrix for a value.

This table shows how many steps the algorithm requires for different matrix sizes:

Which function best describes how the number of steps changes as the matrix size (nnn) increases?

• 2/n

• n/2

• n

• n²

• 2ⁿ

Kora implements an algorithm for determining whether a list has duplicate values.

She counts the number of steps required by the algorithm for increasing list lengths and comes up with this table:

Based on the table, which of the following statements describe the run time for this algorithm?

• The algorithm does not run in reasonable time.

• The algorithm runs in polynomial time.

• The algorithm runs in superpolynomial time.

• The algorithm runs in reasonable time.

One way to measure the efficiency of an algorithm is to count how many steps it requires for different input sizes and then use a function to describe how the number of steps increases in proportion to the input size.

The table below lists various efficiencies, where n represents the input size.

Categorize each efficiency as superpolynomial:

• n²+6n

• 6ⁿ

• 6n⁶

• 6^{2n^2}

• n/6

Reese develops an algorithm to determine all the possible pizza topping combinations.

For a list of 3 possible toppings ("pepper", "pineapple", "mushroom"), their algorithm generates these combinations:

- pepper

- pineapple

- mushroom

- pepper, pineapple

- pepper, mushroom

- pineapple, mushroom

- pepper, pineapple, mushroom

They try out the algorithm on increasing numbers of toppings and record the number of steps it takes.

Their findings are summarized in this table:

Based on the table, which of the following statements describe the run time for this algorithm?

• The algorithm runs in reasonable time.

• The algorithm runs in superpolynomial time.

• The algorithm runs in polynomial time.

• The algorithm does not run in reasonable time.

A mathematician comes up with an algorithm for multiplying two matrices together.

This table shows how many steps the algorithm requires for different matrix sizes:

Which function best describes how the number of steps changes as the matrix size (n) increases?

• 1/n

• n

• n²

• n³

• 2ⁿ

Meredith implements a "graph coloring" algorithm, which comes up with colors for graph vertices such that no neighboring vertices share the same color.

The algorithm outputs graph colorings like this one:

Based on the table, which of the following statements describe the run time for this algorithm?

• The algorithm runs in reasonable time.

• The algorithm does not run in reasonable time.

• The algorithm runs in superpolynomial time.

• The algorithm runs in polynomial time.

Which of the following is the best description of parallel computing?

• A computational model in which a program is broken into smaller subproblems, some of which are executed simultaneously.

• The use of multiple computing devices to work on different parts of a problem.

• The technology which powers online experiences with multiple simultaneous users, such as multi-player computer games.

• The mechanism by which a computer can run multiple applications at once, by switching between them so quickly the user cannot tell.

Ophelia is working on a program that uses machine learning to analyze hospital CT scans for signs of cancer.

With her first version of the program, the computer took an average of 24 minutes to analyze 1000 images. To improve the performance, she parallelized the image analysis operation. When running the parallelized program on a hospital computer, the computer took an average of 6 minutes to analyze 1000 images.

What is the speedup of the parallel solution?

• 4

• 6

• 18

• 1/4

A mapping company is creating a program that can predict the traffic on routes and estimate the delay from the traffic. The program takes an input of 5 routes and outputs the delay for each route.

The program has two phases:

Setup: Loads historical traffic data for the geographic region.

Simulation: Predicts the traffic and estimates the delay of 5 routes.

The initial setup phase takes 10 minutes. The simulation phase takes 5 minutes per route, which amounts to 25 minutes total for the 5 routes. The program takes 35 minutes total.

The company would like to improve the program's efficiency by parallelizing the simulation operations.

What is true about the potential efficiency gains?

• Once the simulation operations are parallelized, the entire simulation phase will never take longer than 5 minutes.

• A version with parallelized simulation operations could take a total time of less than 10 minutes (including setup and simulation).

• The version with parallelized simulation operations will always take less time than the sequential version, even if the company runs the software on a computer that cannot do parallel computing.

• Even if it's run on a powerful computer, a version with parallelized simulation operations would still take at least 15 minutes.

Answer explanation

Nếu mỗi tuyền đường được mô phỏng ss trên một máy tính chạy 5 tác vụ đồng thời, thì toàn bộ giai đoạn mô phỏng có thể mất ít nhất là 5p. Giai đoạn thiết lập mất 10p, Tổng là 15p

Which of these situations is most analogous to parallel computing?

• In a relay race, a team of multiple people each run one segment of the race. Cumulatively, they complete the race, but each person can run for a shorter period of time and focus their energy on that segment.

• People can be pen pals with other people all over the globe. Each person sends letters to however many pen pals they would like, and it's up to the recipient if they would like to send a letter back.

• When multiple people work on a jigsaw puzzle, they can each work on a different part of the puzzle. Once each person has put together a significant area of the puzzle, they can merge the areas and see the completed puzzle.

• On a football team, each player position focuses on different parts of the field (e.g. quarterback, halfback). Each player picks the position that caters to their strengths, so that their team can most effectively move the ball down the field.

Answer explanation

Trong tình huống này, nhiều ng đang làm việc song song trên các bài toán con của 1 bài toán lớn hơn, để họ có thể hoàn thành bài toàn lớn 1 cách nhanh chóng hơn.