Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
34 Cards in this Set
- Front
- Back
|
Quick Sort Big Oh's |
best: n log n average: n log n worst: n ^ 2 |
|
|
Merge Sort Big Oh's |
best: n log n average: n log n worst: n log n |
|
|
Insertion Sort Big Oh's |
best: n average: n ^ 2 worst: n ^ 2 |
|
|
Selection Sort Big Oh's |
best: n ^ 2 average n ^ 2 worst n ^ 2 |
|
|
Linear Search Big Oh's |
best: 1 average: n worst: n |
|
|
Binary Search Big Oh's |
best: 1 average: log n worst: log n |
|
|
Best data structure
An inventory application that records the quantity of each item stored in the inventory. |
map
Choose map when you have an item and its quantity |
|
|
Best data structure
A hard drive that receives a number of block read requests and optimizes head movement by selecting the next request to process based on which block address is closest to the current head position. |
priority queue
Choose priority queue when you need actions in the order received (like a server). Use priority when "closest", "first", "last" is specified |
|
|
Best data structure
A classroom scheduling application that allows the user to find the course number, name, section number, and instructor for a given classroom and time of day. |
map
Choose when you have multiple associations between the data |
|
|
Best data structure
An application that stores a number of tasks that need to be done and allows the user to insert, delete, and edit tasks while keeping the tasks stored in the order given by the user. |
list
Use a list when it is storage, and when the order is controlled by the user, otherwise use a set for automatic ordering |
|
|
Best data structure
Application to balance matching parenthesis |
stack
Use a stack when when there's nesting, or the return in reverse order ({[ -> normal ]}) -> reverse |
|
|
Find the Big Oh
int doit(int n) { int sum = 0; for (int i = 1; i < n; i *= 10) sum += i; return sum; } |
big oh: log n
reason: because the for loop multiplies by ten, anything with a variable different than n and that is multiplied by at least 2, is log n |
|
|
Find the Big Oh
int again(int n) { int sum = 0; for (int i = 10; i > 0; i /= 4) sum++; return sum; } |
big oh: 1 (constant time)
reason: i is not related to n
|
|
|
Find the Big Oh
int more(int n) { int sum = 0; for (int i = n; i > 0; i -= 2) if (i % 4 == 2) for (int i = 0; i < n; i++) sum++; else sum++; return sum; } |
big oh: n^2
reason: when n is an even number, big oh is n^2, when n is odd, big oh is n, so give the worst case |
|
|
Find the Big Oh
(assume print(int) is O(1)) void print(int m[][], int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { print(m[i][j]); } } } |
big oh: n^2
reason: two for loops based on n |
|
|
Find the Big Oh
int less(int n) { for (int i = 0; i*i < n; i++) sum++; } |
big oh: √n
reason: repeats until i * i = n, or until square root of n |
|
|
Given Big Oh log n
An algorithm completes a problem of size 1024 in 2 seconds. How long will this algorithm take to complete a problem of size 4096? How large a problem can be solved in 4 seconds using this algorithm? |
a) 2 / log(2) 1024 = t / log(2) 4096 2 / 10 = t / 12 t = 12 * 2 / 10 t = 2.4 seconds
b) log(2) n / 4 = log(2) 1024 / 2 log(2) n = 4 * 10 / 2 log(2) n = 20 n = 2 ^ 20
|
|
|
Given Big Oh 2 ^ n
An algorithm completes a problem of size 1024 in 2 seconds. How long will this algorithm take to complete a problem of size 4096? How large a problem can be solved in 4 seconds using this algorithm? |
a) 2 / 2^1024 = t / 2^4096 t = 2^1 * 2^4096 / 2^1024 t = 2 ^ 4097 - 1024 t = 2 ^ 3073 seconds
b) 2^1024 / 2 = 2^n / 4 2^n = 4 * 2^1024 / 2 2^n = 2^1 * 2*1024 2^n = 2 ^ 1025 n = 1025 |
|
|
Given Big Oh 1
An algorithm completes a problem of size 1024 in 2 seconds. How long will this algorithm take to complete a problem of size 4096? How large a problem can be solved in 4 seconds using this algorithm? |
a) t / 1 = 2 / 1 t = 2 seconds
b) 1 / 4 = 1 / 2 (?) no answer |
|
|
Given Big Oh n ^ 2
An algorithm completes a problem of size 1024 in 2 seconds. How long will this algorithm take to complete a problem of size 4096? How large a problem can be solved in 4 seconds using this algorithm? |
a) 2 / 1024^2 = t / 4096^2 t = 4096^2 * 2 / 1024^2 t = 4096 * 4096 * 2 / 1024 * 1024 t = 4 * 4 * 2 t = 32 seconds
b) 1024^2 / 2 = n^2 / 4 n^2 = 4 * 1024^2 / 2 n = √2 * 1024 |
|
|
Given Big Oh n ^ 3
An algorithm completes a problem of size 1024 in 2 seconds. How long will this algorithm take to complete a problem of size 4096? How large a problem can be solved in 4 seconds using this algorithm? |
a) 2 / 1024^3 = t / 4096^3 t = 4096^3 * 2 / 1024^3 t = 4096 * 4096 * 4096 * 2 / 1024 * 1024 * 1024 t = 4 * 4 * 4 * 2 t = 128 seconds
b) 1024^3 / 2 = n^3 / 4 n^3 = 4 * 1024^3 / 2 n = cubic√2 * 1024 |
|
|
Given Big Oh n
An algorithm completes a problem of size 1024 in 2 seconds. How long will this algorithm take to complete a problem of size 4096? How large a problem can be solved in 4 seconds using this algorithm? |
a) 2 / 1024 = t / 4096 t = 4096 * 2 / 1024 t = 4096 * 2 / 1024 t = 8 seconds
b) 1024 / 2 = n / 4 n = 4 * 1024 / 2 n = 2048 |
|
|
Find Big Oh
size time 100 10 200 10 400 10 800 10 1600 10 |
big oh: 1 |
|
|
Find Big Oh
size time 128 7 256 8 512 9 1024 10 2048 11 |
big oh: log n |
|
|
Find Big Oh
size time 1 10 2 100 3 1000 4 10000 5 100000 |
big oh: 2^n or 10^n |
|
|
Find Big Oh
size time 10 1110 20 8420 30 27930 40 65640 50 127550 |
big oh: n^3 |
|
|
Binary Search
11 15 16 22 33 44 48 55 58 62 66 72 77 88 99 |
11 15 16 22 33 44 48 55(1) 58 62 66 72(2) 77(4) 88(3) 99
low 0 - 8 - 12 - 12 high 14 - 14 - 14 - 12 mid 7 - 11 - 13 - 12 |
|
|
Show the contents
Stack S List L s.push 4 s push 2 s push 1 s push 8 while s is not empty L append ( s. pop()) |
S : 4 2 1 8 L : 8 1 2 4 |
|
|
Show the contents
Queue Q List L Q.add(4) Q.add(2) Q.add(1) Q.add(8) while q is not empty L append ( Q.remove()) |
Q: 4 2 1 8 L: 4 2 1 8 |
|
|
Show the contents
Priority Queue List L Q.add(4) Q.add(2) Q.add(1) Q.add(8) while q is not empty L append ( Q.remove()) |
Q : 4 2 1 8 L : 1 2 4 8 ( assume 1 ) |
|
|
Insertion sort
8 7 2 9 4 8 5 4 3 |
8 | 7 2 9 4 8 5 4 3
7 8 | 2 9 4 8 5 4 3
2 7 8 | 9 4 8 5 4 3
2 7 8 9 | 4 8 5 4 3
2 4 7 8 9 | 8 5 4 3
2 4 7 8 8 9 | 5 4 3
2 4 5 7 8 8 9 | 4 3
2 4 4 5 6 8 8 9 | 3
2 3 4 4 5 6 8 8 9 | -> stops |
|
|
Selection sort
8 7 2 9 4 8 5 4 3 |
| 8 7 2 9 4 8 5 4 3
2 | 7 8 9 4 8 5 4 3
2 3 | 8 9 4 8 5 4 7
2 3 4 | 9 8 8 5 4 7
2 3 4 4 | 8 8 5 9 7
2 3 4 4 5 | 8 8 9 7
2 3 4 4 5 7 | 8 9 8
2 3 4 4 5 7 8 | 9 8
2 3 4 4 5 7 8 8 | 9 - > stops |
|
|
Merge sort
8 2 7 4 4 8 5 1 |
8 2 7 4 4 8 5 1
8 2 7 4 4 8 5 1
8 2 7 4 4 8 5 1
8 2 7 4 4 8 5 1
2 8 4 7 4 8 1 5
2 4 7 8 1 4 5 8
1 2 4 4 5 7 8 8 |
|
|
Quick sort
1 9 8 3 3 2 5 4 7 |
1 9 8 3 3(1) 2 5 4 7
1(2) 2 3 3 9 8 5(2) 4 7 4 5 9 8(3) 7
- 1 2 7 8 9
1 2 4 5 7 8 9
1 2 3 3 4 5 7 8 9 |
