AP CSP Pages 115-139

studied byStudied by 1 person
0.0(0)
Get a hint
Hint

Given a collection of numbers, find and remove all zeros

1 / 21

22 Terms

1

Given a collection of numbers, find and remove all zeros

Data cleanup algorithm

New cards
2

(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

New cards
3

best case for shuffle left algorithm

order of magnitude n

New cards
4

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

New cards
5

Is the copy-over algorithm time and space efficient

yes, no

New cards
6

What is the Copy-Over algorithm an example of

Time-space tradeoff

New cards
7

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

Converging Pointers Algorithm

New cards
8

Is the Converging Pointers Algorithm time and space efficient

yes, yes

New cards
9

What order of magnitude is the converging-pointers algorithm

Order of magnitude n

New cards
10

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

New cards
11

What is the unit of work for the binary search algorithm

The number of comparisons

New cards
12

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

Half as much

New cards
13

worst case for binary search algorithm

order of magnitude lg n

New cards
14

What is the fastest order of magnitude

order of magnitude lg n

New cards
15

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

Faster, but needs a sorted list

New cards
16

What is the unit of work for the pattern matching algorithm

comparing the text to the pattern

New cards
17

Best case for pattern matching

order of magnitude n

New cards
18

worst case for pattern matching

order of magnitude m * n

New cards
19

worst case for shuffle left algorithm

order of magnitude n^2

New cards
20

best case for binary search

order of magnitude 1

New cards
21

What algorithm is more work than any polynomial in n

exponential algorithm

New cards
22

run in polynomial time but do not give optimal solutions

approximation algorithms

New cards

Explore top notes

note Note
studied byStudied by 6 people
... ago
5.0(1)
note Note
studied byStudied by 48 people
... ago
5.0(1)
note Note
studied byStudied by 26 people
... ago
5.0(1)
note Note
studied byStudied by 138 people
... ago
5.0(1)
note Note
studied byStudied by 21 people
... ago
5.0(1)
note Note
studied byStudied by 14 people
... ago
5.0(1)
note Note
studied byStudied by 42 people
... ago
5.0(2)
note Note
studied byStudied by 815 people
... ago
5.0(1)

Explore top flashcards

flashcards Flashcard (63)
studied byStudied by 70 people
... ago
5.0(1)
flashcards Flashcard (48)
studied byStudied by 31 people
... ago
5.0(1)
flashcards Flashcard (57)
studied byStudied by 16 people
... ago
5.0(1)
flashcards Flashcard (68)
studied byStudied by 3 people
... ago
5.0(1)
flashcards Flashcard (79)
studied byStudied by 1 person
... ago
5.0(1)
flashcards Flashcard (61)
studied byStudied by 30 people
... ago
5.0(1)
flashcards Flashcard (20)
studied byStudied by 153 people
... ago
4.5(2)
flashcards Flashcard (302)
studied byStudied by 51 people
... ago
5.0(1)
robot