Test 3 Flashcards
1
Q
A __________ ___________ is a restricted form of a list. Items have priorities (or _____)
A
priority queuekeys
2
Q
A priority queue removes items based on _________
A
priority
3
Q
Unsorted list implementation store the items of the priority queue in a ____-_____, in arbitrary order
A
list-based
4
Q
Unsorted list implementation example
A
4 - 5 - 2 - 3 - 1
5
Q
Unsorted list implementation Performance: ____________ takes _____ time since we can insert the item at the beginning of the sequence
A
insertItemO(1)
6
Q
Unsorted list implementation Performance: ___________, __________, and ___________ take ______ time since we have to traverse the entire sequence to find the smallest key
A
removeItem, min/maxKey, min/maxElementO(n)
7
Q
Sorted list implementation store the items of the priority queue in a sequence, sorted by _____
A
key
8
Q
Sorted list implementation example
A
1 - 2 - 3 - 4 - 5
9
Q
Sorted list implementation Performance: __________ takes ______ time since we have to find the place where to insert the item
A
insertItemO(n)
10
Q
Sorted list implementation Performance: ___________, __________, and ___________ take ______ time since the smallest key is at the beginning of the sequence
A
removeItem, min/maxKey, min/maxElementO(1)
11
Q
Sorting Using a Priority Queue -given a ___________ of N items: a PQ can be used to sort the ___________:
A
sequencesequence
12
Q
Sorting Using a Priority Queue -given a sequence of N items: a PQ can be used to sort the sequence: -Step 1: ___________…
A
Insert N items into the PQ via insertItem(key, data)
13
Q
Sorting Using a Priority Queue -given a sequence of N items: a PQ can be used to sort the sequence: -Step 1: Insert N items into the PQ via insertItem(key, data) -Step 2: ___________…
A
Remove the items by calling removeItem() N times-the first remove removes the largest item, the second call the second largest, … the last removes the smallest item
14
Q
Binary Search -uses a _________ and ___________ methodology
A
divideconquer
15
Q
Binary Search -requires data to be ________
A
sorted
16
Q
Binary Search -Runs in _______ time
A
O(lg n)
17
Q
Binary Search -example of divide and conquer
A
looking up a word in a dictionary
18
Q
Bubble Sort 1st run (5), (7), 2, 6, 9, 3 can’t switch 5 and 7 because 7 is larger 5, (7), (2), 6, 9, 3 then 7 and 2 5, 2, (7), (6), 9, 3 switch 7 and 2 because 7 is larger 5, 2, 6, (7), (9), 3 switch 7 and 6 5, 2, 6, 7, (3), (9) switch 9 and 3
A
the largest value has now bubbled to the end
19
Q
Bubble Sort 2nd run (5), (2), 6, 7, 3, 9 2, (5), (6), 7, 3, 9 2, 5, (6), (7), 3, 9 2, 5, 6, (7), (3), 9 2, 5, 6, 3, (7), 9
A
the second largest value has now bubbled to the end
20
Q
Complexity of bubble sort
A
n^2
21
Q
Quicksort Algorithm 1. While data[___________] <= data[______] {++BiggerIndex; }
A
BiggerIndexpivot
22
Q
Quicksort Algorithm 2. While data[___________] > data[_____] {–SmallerIndex; }
A
SmallerIndexpivot
23
Q
Quicksort Algorithm 3. If ___________ < ____________ { swap data[BiggerIndex] and data[SmallerIndex] }
A
BiggerIndexSmallerIndex
24
Q
Quicksort Algorithm 4. While SmallerIndex > BiggerIndex, go to 1
A
SmallerIndexBiggerIndex
25
Quicksort Algorithm 5. Swap data[____________] and data[____________]
SmallerIndexpivotIndex
26
Quicksort Algorithm given an array of n ________ (integers) -if array only contains one element, return -else --pick one element to use as ______ --partition elements into two ___-______: ---elements less than or equal to pivot ---elements greater than pivot
elementspivotsub-arrays
27
Quicksort example pivot index = 0 bigger index = 1 smaller index = 8 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 80 | 60 | 50 | 7 | 30 | 100 so is 20 <= 40?
yes
28
Quicksort example pivot index = 0 bigger index = 2 smaller index = 8 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 80 | 60 | 50 | 7 | 30 | 100 so is 10 <= 40?
yes
29
Quicksort example pivot index = 0 bigger index = 3 smaller index = 8 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 80 | 60 | 50 | 7 | 30 | 100 so is 80 <= 40?
no
30
Quicksort example pivot index = 0 bigger index = 3 smaller index = 8 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 80 | 60 | 50 | 7 | 30 | 100 so is 100 > 40?
yes
31
Quicksort example pivot index = 0 bigger index = 3 smaller index = 7 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 80 | 60 | 50 | 7 | 30 | 100 so is 30 > 40?
no
32
Quicksort example pivot index = 0 bigger index = 3 smaller index = 7 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 30 | 60 | 50 | 7 | 80 | 100 swap 80 and 30 so is 30 <= 40?
yes
33
Quicksort example pivot index = 0 bigger index = 4 smaller index = 7 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 30 | 60 | 50 | 7 | 80 | 100 swap 80 and 30 so is 60 <= 40?
no
34
Quicksort example pivot index = 0 bigger index = 4 smaller index = 7 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 30 | 60 | 50 | 7 | 80 | 100 so is 80 > 40?
yes
35
Quicksort example pivot index = 0 bigger index = 4 smaller index = 6 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 30 | 60 | 50 | 7 | 80 | 100 so is 7 > 40? so swap 7 and 60
no
36
Quicksort example pivot index = 0 bigger index = 4 smaller index = 6 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 30 | 7 | 50 | 60 | 80 | 100 so is 7 <= 40?
yes
37
Quicksort example pivot index = 0 bigger index = 5 smaller index = 6 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 30 | 7 | 50 | 60 | 80 | 100 so is 50 <= 40?
no
38
Quicksort example pivot index = 0 bigger index = 5 smaller index = 6 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 30 | 7 | 50 | 60 | 80 | 100 so is 60 > 40? then the bigger index = smaller index
yes
39
Quicksort example pivot index = 0 bigger index = 5 smaller index = 4 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 7 | 20 | 10 | 30 | 40 | 50 | 60 | 80 | 100 swap 40 and 7 so what's the new pivot index?
pivotIndex = 4
40
Quicksort Analysis with the assumption the keys are random uniformly distributed, the runtime of QuickSort is usually taken to be ____________
O(n lg n)
41
Quicksort to avoid such bad scenarios a better choice of pivot is typically used: use the Median of 3 Rule:
pick the median value of 3 elements from the data array as the pivot specifically: data[0], data[n/2], and data[n-1]
42
Quicksort median of 3 rule example: data[0] = 10, data[n/2] = 70, data[n-1] = 50 median of {10, 50, 70} = ?
50
43
Quicksort: small arrays for very small arrays (circa n <= 20), quicksort in physical time does not perform as well as __________ ______.
insertion sort
44
Quicksort: small arrays And because quicksort is ___________, these cases occur frequently
recursive
45
"Quicksort: small arrays common solution: when the array size becomes ""sufficiently"" small _____ ______ ______ quicksort recursively. instead, use a sorting algorithm that is more efficient for small arrays (such as ___________ _____)"
do not useinsertion sort
46
worst case time for Selection Sort
O(n^2)
47
worst case time for Insertion Sort
O(n^2)
48
worst case time for Bubble Sort
O(n^2)
49
worst case time for Heap Sort
O(n log(n) )
50
worst case time for Merge Sort
O(n log(n) )
51
worst case time for Quick Sort
O(n^2)
52
________ sort is based on divide and conquer paradigm
merge
53
Merge sort consists of three steps. What is the first step?
Divide: partition input sequence S into two sequences S1 and S2 of about n/2 elements each
54
Merge sort consists of three steps. What is the second step?
Recur: recursively sort S1 and S2
55
Merge sort consists of three steps. What is the third step?
Conquer: merge S1 and S2 into a unique sorted sequence
56
MergeSort you may also see MergeSort Trees that: -instead of reversing direction back up the tree -continue down -- ______________...
merging the branches as they go
57
MergeSort the execution results of a MergeSort can be represented as a _________ _______
binary tree
58
MergeSort uses a ________ and ________ method
divide conquer
59
MergeSort The height of the tree is _________, where N is the number of items being sorted
lg N
60
MergeSort The height of the tree is lg N, where N is the number of items being sorted How do we know that? because lg N is _________________....
the number of times N can be divided by 2 (integer wise)
61
Runtime of MergeSort knowing the height of the representative tree is lg N is important because:
"it is the ""key concept"" in showing/proving the runtime of MergeSort is O(N lg N)"
62
"Merge sort consists of three steps. The first step ""divide"" has what runtime?"
O(1)
63
"Merge sort consists of three steps. The third step ""conquer"" has what runtime?"
O(n)
64
"Merge sort consists of three steps. The second step ""recur"" has what runtime?"
O(lg n)
65
MergeSort The Tree Proof The height h of the mergesort tree is _______
O(lg n)
66
MergeSort The Tree Proof at each recursive call we ______________
divide the sequence in half
67
MergeSort The Tree Proof The work done at each level is _______
O(n)
68
MergeSort The Tree Proof -at level i, we partition and merge ______ sequences of size _______ (# boxes) * (# things in each box)
2^in / 2^i
69
MergeSort The Tree Proof Thus, the total running time of merge-sort is __________
O(n lg n)
70
MergeSort Telescoping Proof given T(N) = 2T(N/2) + N prove T(N) = N lg N for N > 1, and also given T(1) = 0 (do algebra) T(N) = 2 * T(N/2) + N T(N) / N = 2 * (N/2) / N + 1 = T(N/2) / (N/2) + 1 = T(N/4) / (N/4) + 1 + 1 = T(N/8) / (N/8) + 1 + 1 + ... + 1 = lg N that is T(N) / N = lg N so...
T(N) = N lg Nrecall that lg N denotes log base 2 of N
71
Average time for Selection Sort
O(n^2)
72
Notes for Selection Sort
slow, in placefor small data sets
73
Worst case time for Selection Sort
O(n^2)
74
Average time for Insertion Sort
O(n^2)
75
Notes for Insertion Sort
slow, in placefor small data sets
76
Worst case time for Insertion Sort
O(n^2)
77
Average time for Bubble Sort
O(n^2)
78
Notes for Bubble Sort
slow, in placefor small data sets
79
Worst case time for Bubble Sort
O(n^2)
80
Average time for Merge Sort
O(n log(n) )
81
Notes for Merge Sort
fast, sequential data accessfor huge data sets
82
Worst case time for Merge Sort
O(n log(n))
83
Average time for Quick Sort
O(n log(n))
84
Notes for Quick Sort
assumes key values are random and uniformly distributed
85
Worst case time for Quick Sort
O(n^2)
86
What is a tree? in computer science, a tree is...
an abstract model of a hierarchical structure
87
A tree consists of...
nodes with a parent-child relation
88
Tree applications:
organization chartsfile systemsmany others
89
General tree terminology -Root:
node without parent
90
General tree terminology -Internal node:
node with at least one child
91
General tree terminology -Leaf (aka external node):
node without children
92
General tree terminology -Ancestors of a node:
parent, grandparent, great-grandparent, etc
93
General tree terminology -Depth of a node:
number of ancestors (root has a depth of 0)
94
General tree terminology -Height of a tree:
maximum depth of any node
95
General tree terminology -Descendant of a node:
child, grandchild, great-grandchild, etc
96
General tree terminology -Size:
number of nodes in a tree
97
General tree terminology -Subtree:
tree consisting of a node and its descendants
98
Tree terminology -depth of a node p: most often we speak of the depth of nodes and the height of the tree
number of ancestors of p
99
Tree terminology -height of a node p: most often we speak of the depth of nodes and the height of the tree
the length of the longest path to a leaf from p
100
Tree ADT Nodes will hold _______ and ________ to other nodes
data links
101
Tree ADT Generic methods:
integer size()boolean isEmpty()objectIterator elements()positionIterator positions()
102
Tree ADT Accessor methods:
position root()position parent(p)positionIterator children(p)
103
Tree ADT Query methods:
boolean isInternal(p)boolean isLeaf(p)boolean isRoot(p)
104
Tree ADT Update methods: additional update methods may be defined by data structures implementing the Tree ADT
swapElements(p, q)object replaceElement(p, o)
105
A Linked Structure for General Trees -a node is represented by an object storing:
elementparent nodesequence of children nodes
106
Binary Tree A binary tree is a tree with the following properties: -Each node has ______ children -The children of a node are an _________ ________
twoordered pair
107
Binary Tree We call the children of an internal node _________ ________ and ________ ________.
left child right child
108
BinaryTree ADT The BinaryTree ADT extends the ________ ADT. (it inherits all the methods of this ADT)
Tree
109
A Linked Structure for Binary Trees -a node is represented by an object storing
elementparent nodeleft child noderight child node
110
"Balanced Tree A binary tree is balanced if every level above the lowest is ""full"" (contains 2^level nodes) a / \ b c /\ / \ d e f g / \ h i is this tree balanced?"
yes
111
A Complete Binary Tree with height h, is a tree such that -_________________________, for ____________________ -nodes at level h fill up ____ to _____
level i has 2^i nodes0 <= i <= h-1leftright
112
Sorted Binary Tree a binary tree is sorted if every node in the tree is larger than (or equal to) its _____________________, and smaller than (or equal to) its _____________________ equal nodes can go either left or the right but it has to be ___________
left descendantsright descendantsconsistent
113
A full (or proper) binary tree is a tree such that every non-leaf node has ____ children
2
114
Generalizing Traversals the 3 tree traversals methods: 1. ___________ 2. ___________ 3. ___________ they are all very similar in nature
preorderinorderpostorder
115
Claim about sorting possible to create a _________ __________ -pq sort where the ____ ___________ used to implement it __________ ____ ___________ of the algorithm
generic algorithmdata structureaffects the runtime
116
Priority Queue ADT a priority queue (PQ) is a restricted form of a list items are arranged to their priorities (or keys) --keys may or may not be unique a priority queue removes items based on __________
priority
117
Queue ADT what does FIFO stand for?
first in, first out
118
PQ - Total Order Relation a priority queue must hold a ______ ______ ___________ (example <= )
total order relation
119
PQ - Total Order Relation a total order relation has the following properties:
-reflexive-antisymmetric-transitive
120
PQ - Total Order Relation -reflexive
k <= k
121
PQ - Total Order Relation -antisymmetric
if x <= y and y <= x then x = y
122
PQ - Total Order Relation -transitive
if a <= band b <= cthen a <= c
123
2 types of PQ
min PQmax PQ
124
Min PQ
minimum key value is the highest priority
125
Max PQ
maximum key value is the highest priority
126
Priority Queue ADT Operations Main Methods of PQs
1. insertItem(key, data)--aka enqueue(key, data)--inserts data into the PQ according to key2. removeItem()--removes the item with the smallest (largest) key---depending if using min PQ or max PQremoveItem() may also be named removeMin() or removeMax() or dequeue()
127
Priority Queue ADT Operations Additional Methods of PQs
1. size()--returns number of elements in PQ2. empty()--returns true if zero elements in PQ3. minItem() / maxItem()--returns item with smallest/largest key4. minKey() / maxKey()--returns smallest/largest key
128
Sorting Using a PQ given a sequence of N items a PQ can be used to sort the sequence Step 1: insert N items into the PQ via ____________
insertItem(key, data)
129
Sorting Using a PQ given a sequence of N items a PQ can be used to sort the sequence Step 2: remove the items by calling _________________ N times the first remove removes the largest item, the second call the second largest,...the last removes the smallest item
removeItem()
130
Recall doubly linked list
prevnext | key data
131
for priority queue, we split elem into two things:
key (of type int)data (of type T)
132
so if we have a list of (un)ordered stuff to make it a PQ we need the functions:
insertItem(key, data)removeItem()--assume a Min PQ so this removes the item with the smallest key
133
PQ as Unordered List PQ::_____________________ this is just an insertFront() call for the list --like m_list.insertFront(...) recall this is an ____ operation
insertItem(key, data)O(1)
134
so if we have a list of unordered stuff to make it a PQ we need the functions: insertItem(key, data) --can be done in ____ removeItem() --requires ____
O(1)O(n)
135
let's say we have a list of ordered stuff to make it a PQ we need the functions: insertItem(key, data) --requires _______ removeItem() --can be done in _______
O(n)O(1)
136
Selection and Insertion Sort are:
two different implementations of PQ sort
137
Selection sort uses a data structure of
unsorted list
138
Insertion sort uses a data structure of
sorted list
139
Priority Queues can be implemented using a _______ _______
binary heap
140
A heap is a binary tree with two properties:
structure propertyheap order property--max heap--min heap
141
Structure Property A heap is a complete binary tree. When a complete binary tree is built, its first node must be the ____
root
142
Structure Property The second node is always the ____ ______ of the root.
left child
143
Structure Property The third node is always the ____ ______ of the root.
right child
144
Structure Property The next nodes always fill the next level from _____-__-______
left-to-right
145
Structure Property Each node in a heap contains a ____ that can be compared to other nodes' ______.
keykeys
146
"Heap Order Property For a ""MaxHeap"" The key value of each node is at least as ______ as the key value of its children"
large
147
"Heap Order Property For a ""MaxHeap"" The root of the heap is the _______ value in the tree"
largest
148
"Heap Order Property For a ""MaxHeap"" The ""max heap property"" requires that each node's key is _______(operator) the keys of its children"
>=
149
"Heap Order Property For a ""MinHeap"" The key value of each node is the ____ __ _______ than the key value of its children"
same or smaller
150
"Heap Order Property For a ""MinHeap"" The root of the heap is the ___________ value in the tree"
smallest
151
"Heap Order Property For a ""MinHeap"" The ""min heap property"" requires that each node's key is _______(operator) the keys of its children"
<=
152
Heap Implementation A heap could be implemented using a regular binary tree (left and right child pointers) however, a heap is a _________ binary tree so we can use an array or vector instead
complete
153
Big Oh int sum = 0; cout << value if (count < 20) { area = (1.0 / 2.0) * base * height; total = total + current;
O(1)
154
"Big Oh for (int j = 1; j <= n; j++) { cout << ""this prints n times"" << endl; }"
O(n)
155
"Big Oh for (int j = 1; j<= n; j++) { for (int k=1; k <= n; k++) { cout << ""this prints n^2 times"" << endl; } }"
O(n^2)
156
"Big Oh for (int j = 1; j <= sqrt(n); j++) { cout << ""this prints n^1/2 times"" << endl; }"
O(n^1/2)
157
"Big Oh for (int j = n; j > 0; j /= 2 ) { cout << ""this prints lg n times"" endl; }"
O(lg n)
