AP CSP Pages 115-139

Given a collection of numbers, find and remove all zeros

Data cleanup algorithm

(Data Cleanup Algorithm) Scans a list from left to right, when a zero is found, shift all values to its right one slot to the left

Shuffle Left Algortihm

best case for shuffle left algorithm

order of magnitude n

Create a second, initially empty, list Look at each value in the original If it is non-zero, copy it to the second list

Copy-Over Algorithm

Is the copy-over algorithm time and space efficient

yes, no

What is the Copy-Over algorithm an example of

Time-space tradeoff

A data cleanup that squeezes out zeros and finishes when both data pointers converge at a nonzero value.

Converging Pointers Algorithm

Is the Converging Pointers Algorithm time and space efficient

yes, yes

What order of magnitude is the converging-pointers algorithm

Order of magnitude n

Given a target value and an ordered list of values, find the location of the target in the list, if it occurs, by starting in the middle and splitting the range in two with each comparison

Binary Search Algorithm

What is the unit of work for the binary search algorithm

The number of comparisons

How much work does the binary search algorithm do compared to the sequential search algorithm

Half as much

worst case for binary search algorithm

order of magnitude lg n

What is the fastest order of magnitude

order of magnitude lg n

How does the binary search's efficiency compare to the sequential search

Faster, but needs a sorted list

What is the unit of work for the pattern matching algorithm

comparing the text to the pattern

Best case for pattern matching

order of magnitude n

worst case for pattern matching

order of magnitude m * n

worst case for shuffle left algorithm

order of magnitude n^2

best case for binary search

order of magnitude 1

What algorithm is more work than any polynomial in n

exponential algorithm

run in polynomial time but do not give optimal solutions

approximation algorithms