AP CSP Pages 92-115 Quiz

elegance

the algorithmic equivalent of style

efficiency

An algorithm’s careful use of resources

benchmarking

Running a program on many data sets to be sure its performance falls within required limits; timing the same algorithm on two different machines

comparing machines’ sensitivities

what are benchmarks useful for

analysis of algorithms

study of the efficiency of algorithms

order of magnitude n

anything that varies as a constant times n (and whose graph follows the basic shape of n)

Searching and Sorting

2 problems that a sequential search algorithm does

Selection Sort Algorithm

an algorithm that sorts a list of values into a particular order

order of magnitude n²

an algorithm that does cn² work for any constant c

flops

a unit of measure of processor speed: floating-point operations per second

Correctness, Usability, Efficiency, Elegance, Ease of Understanding

What features should an algorithm have

program maintenance

the process of adapting and improving an existing software product

Space efficiency

judged by the amount of information the algorithm must store in the computer’s memory to do its job, in addition to the initial data on which the algorithm is operating.

cross purposes

What do elegance and ease of understanding work at?

1. Computer Used

2. Phone Book length

3. Number searched for

What 3 things could affect the timing of a sequential search algorithm?

machine speed or variations in input data than the efficiency (or lack thereof) of the algorithm itself.

What would timing the running of an algorithm more likely to reflect?

The number of times a unit of work in an algorithm is executed is calculated

How is time efficiency measured

Comparison of the NUMBER being searched for against a single phone number in the list

What is the unit of work in the sequential search algorithm

small tasks that take a single instruction to execute

what are peripheral tasks

the same

How much work does the selection sort algorithm do for each arrangement of numbers

Exchange and compare numbers

what two things does the selection sort algorithm do

3

how many storage locations are needed for exchanging two numbers

(1, 1)

at what point do order of magnitude n and n² cross