AP CSP Unit 10 Algorithms

Which phrase best defines an algorithm?

• exact list of clear steps

• random guessing until success

• picture of computer wires

• secret password saved offline

Which problem is provably unsolvable for all inputs?

• sorting eight random numbers

• multiplying two whole numbers

• deciding if any program halts

• finding a name linearly

Emma is organizing a school event and needs to arrange chairs in a grid pattern. She repeats the process of placing chairs in a row n times, and for each row, she repeats placing chairs n times. What is the overall Big-O time complexity of this chair arrangement process?

• linear time in n

• quadratic time n squared

• constant time regardless size

• logarithmic time log n

Binary search only works when the list is

• sorted into correct order

• stored on flash drive

• full of duplicate entries

• limited to ten items

Michael is organizing his collection of books on a shelf. He picks up each book one by one and places it in its correct position among the already sorted books. What is the average complexity of this sorting method?

• constant time for all

• n log n steps

• about n squared steps

• roughly log n steps

Inside many loops, an accumulator is used to

• keep a running total

• index through each value

• randomize entire list order

• encrypt the data items

Why might a map app use a heuristic instead of the perfect Traveling-Salesman answer?

• guarantees absolute shortest path

• uses less battery power

• gets good route quickly

• avoids all traffic jams

What mainly limits parallel speed-ups?

• slow monitor refresh frequency

• sequential parts of problem

• huge screen resolution size

• long keyboard repeat delay

Amdahl’s Law says adding more CPU cores will

• double the speed automatically

• never change program speed

• help partly but not fully

• halve the energy use

What is the fundamental principle behind merge sort?

• swap neighboring items repeatedly

• count each value frequency

• check parity bits first

• divide and conquer by merging sorted halves