Studied by 1 person
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
Note 
Flashcard (22)