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?
Computer Used
Phone Book length
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