Test 3 Flashcards
A __________ ___________ is a restricted form of a list. Items have priorities (or _____)
priority queuekeys
A priority queue removes items based on _________
priority
Unsorted list implementation store the items of the priority queue in a ____-_____, in arbitrary order
list-based
Unsorted list implementation example
4 - 5 - 2 - 3 - 1
Unsorted list implementation Performance: ____________ takes _____ time since we can insert the item at the beginning of the sequence
insertItemO(1)
Unsorted list implementation Performance: ___________, __________, and ___________ take ______ time since we have to traverse the entire sequence to find the smallest key
removeItem, min/maxKey, min/maxElementO(n)
Sorted list implementation store the items of the priority queue in a sequence, sorted by _____
key
Sorted list implementation example
1 - 2 - 3 - 4 - 5
Sorted list implementation Performance: __________ takes ______ time since we have to find the place where to insert the item
insertItemO(n)
Sorted list implementation Performance: ___________, __________, and ___________ take ______ time since the smallest key is at the beginning of the sequence
removeItem, min/maxKey, min/maxElementO(1)
Sorting Using a Priority Queue -given a ___________ of N items: a PQ can be used to sort the ___________:
sequencesequence
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)
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: ___________…
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
Binary Search -uses a _________ and ___________ methodology
divideconquer
Binary Search -requires data to be ________
sorted
Binary Search -Runs in _______ time
O(lg n)
Binary Search -example of divide and conquer
looking up a word in a dictionary
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
the largest value has now bubbled to the end
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
the second largest value has now bubbled to the end
Complexity of bubble sort
n^2
Quicksort Algorithm 1. While data[___________] <= data[______] {++BiggerIndex; }
BiggerIndexpivot
Quicksort Algorithm 2. While data[___________] > data[_____] {–SmallerIndex; }
SmallerIndexpivot
Quicksort Algorithm 3. If ___________ < ____________ { swap data[BiggerIndex] and data[SmallerIndex] }
BiggerIndexSmallerIndex
Quicksort Algorithm 4. While SmallerIndex > BiggerIndex, go to 1
SmallerIndexBiggerIndex
Quicksort Algorithm 5. Swap data[____________] and data[____________]
SmallerIndexpivotIndex
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Quicksort Analysis with the assumption the keys are random uniformly distributed, the runtime of QuickSort is usually taken to be ____________
O(n lg n)
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]
Quicksort median of 3 rule example: data[0] = 10, data[n/2] = 70, data[n-1] = 50 median of {10, 50, 70} = ?
50
Quicksort: small arrays for very small arrays (circa n <= 20), quicksort in physical time does not perform as well as __________ ______.
insertion sort
Quicksort: small arrays And because quicksort is ___________, these cases occur frequently
recursive
“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
worst case time for Selection Sort
O(n^2)
worst case time for Insertion Sort
O(n^2)
worst case time for Bubble Sort
O(n^2)
worst case time for Heap Sort
O(n log(n) )
worst case time for Merge Sort
O(n log(n) )
worst case time for Quick Sort
O(n^2)
________ sort is based on divide and conquer paradigm
merge
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
Merge sort consists of three steps. What is the second step?
Recur: recursively sort S1 and S2
Merge sort consists of three steps. What is the third step?
Conquer: merge S1 and S2 into a unique sorted sequence
MergeSort you may also see MergeSort Trees that: -instead of reversing direction back up the tree -continue down – ______________…
merging the branches as they go
MergeSort the execution results of a MergeSort can be represented as a _________ _______
binary tree
MergeSort uses a ________ and ________ method
divide conquer
MergeSort The height of the tree is _________, where N is the number of items being sorted
lg N
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)
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)”
“Merge sort consists of three steps. The first step ““divide”” has what runtime?”
O(1)
“Merge sort consists of three steps. The third step ““conquer”” has what runtime?”
O(n)
“Merge sort consists of three steps. The second step ““recur”” has what runtime?”
O(lg n)
MergeSort The Tree Proof The height h of the mergesort tree is _______
O(lg n)
MergeSort The Tree Proof at each recursive call we ______________
divide the sequence in half
MergeSort The Tree Proof The work done at each level is _______
O(n)
MergeSort The Tree Proof -at level i, we partition and merge ______ sequences of size _______ (# boxes) * (# things in each box)
2^in / 2^i
MergeSort The Tree Proof Thus, the total running time of merge-sort is __________
O(n lg n)
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
Average time for Selection Sort
O(n^2)
Notes for Selection Sort
slow, in placefor small data sets
Worst case time for Selection Sort
O(n^2)
Average time for Insertion Sort
O(n^2)
Notes for Insertion Sort
slow, in placefor small data sets
Worst case time for Insertion Sort
O(n^2)
Average time for Bubble Sort
O(n^2)
Notes for Bubble Sort
slow, in placefor small data sets
Worst case time for Bubble Sort
O(n^2)
Average time for Merge Sort
O(n log(n) )
Notes for Merge Sort
fast, sequential data accessfor huge data sets
Worst case time for Merge Sort
O(n log(n))
Average time for Quick Sort
O(n log(n))
Notes for Quick Sort
assumes key values are random and uniformly distributed
Worst case time for Quick Sort
O(n^2)
What is a tree? in computer science, a tree is…
an abstract model of a hierarchical structure
A tree consists of…
nodes with a parent-child relation
Tree applications:
organization chartsfile systemsmany others
General tree terminology -Root:
node without parent
General tree terminology -Internal node:
node with at least one child
General tree terminology -Leaf (aka external node):
node without children
General tree terminology -Ancestors of a node:
parent, grandparent, great-grandparent, etc
General tree terminology -Depth of a node:
number of ancestors (root has a depth of 0)
General tree terminology -Height of a tree:
maximum depth of any node
General tree terminology -Descendant of a node:
child, grandchild, great-grandchild, etc
General tree terminology -Size:
number of nodes in a tree
General tree terminology -Subtree:
tree consisting of a node and its descendants
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
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
Tree ADT Nodes will hold _______ and ________ to other nodes
data links
Tree ADT Generic methods:
integer size()boolean isEmpty()objectIterator elements()positionIterator positions()
Tree ADT Accessor methods:
position root()position parent(p)positionIterator children(p)
Tree ADT Query methods:
boolean isInternal(p)boolean isLeaf(p)boolean isRoot(p)
Tree ADT Update methods: additional update methods may be defined by data structures implementing the Tree ADT
swapElements(p, q)object replaceElement(p, o)
A Linked Structure for General Trees -a node is represented by an object storing:
elementparent nodesequence of children nodes
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
Binary Tree We call the children of an internal node _________ ________ and ________ ________.
left child right child
BinaryTree ADT The BinaryTree ADT extends the ________ ADT. (it inherits all the methods of this ADT)
Tree
A Linked Structure for Binary Trees -a node is represented by an object storing
elementparent nodeleft child noderight child node
“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
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
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
A full (or proper) binary tree is a tree such that every non-leaf node has ____ children
2
Generalizing Traversals the 3 tree traversals methods: 1. ___________ 2. ___________ 3. ___________ they are all very similar in nature
preorderinorderpostorder
Claim about sorting possible to create a _________ __________ -pq sort where the ____ ___________ used to implement it __________ ____ ___________ of the algorithm
generic algorithmdata structureaffects the runtime
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
Queue ADT what does FIFO stand for?
first in, first out
PQ - Total Order Relation a priority queue must hold a ______ ______ ___________ (example <= )
total order relation
PQ - Total Order Relation a total order relation has the following properties:
-reflexive-antisymmetric-transitive
PQ - Total Order Relation -reflexive
k <= k
PQ - Total Order Relation -antisymmetric
if x <= y and y <= x then x = y
PQ - Total Order Relation -transitive
if a <= band b <= cthen a <= c
2 types of PQ
min PQmax PQ
Min PQ
minimum key value is the highest priority
Max PQ
maximum key value is the highest priority
Priority Queue ADT Operations Main Methods of PQs
- 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()
Priority Queue ADT Operations Additional Methods of PQs
- 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
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)
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()
Recall doubly linked list
prevnext | key data
for priority queue, we split elem into two things:
key (of type int)data (of type T)
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
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)
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)
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)
Selection and Insertion Sort are:
two different implementations of PQ sort
Selection sort uses a data structure of
unsorted list
Insertion sort uses a data structure of
sorted list
Priority Queues can be implemented using a _______ _______
binary heap
A heap is a binary tree with two properties:
structure propertyheap order property–max heap–min heap
Structure Property A heap is a complete binary tree. When a complete binary tree is built, its first node must be the ____
root
Structure Property The second node is always the ____ ______ of the root.
left child
Structure Property The third node is always the ____ ______ of the root.
right child
Structure Property The next nodes always fill the next level from _____-__-______
left-to-right
Structure Property Each node in a heap contains a ____ that can be compared to other nodes’ ______.
keykeys
“Heap Order Property For a ““MaxHeap”” The key value of each node is at least as ______ as the key value of its children”
large
“Heap Order Property For a ““MaxHeap”” The root of the heap is the _______ value in the tree”
largest
“Heap Order Property For a ““MaxHeap”” The ““max heap property”” requires that each node’s key is _______(operator) the keys of its children”
> =
“Heap Order Property For a ““MinHeap”” The key value of each node is the ____ __ _______ than the key value of its children”
same or smaller
“Heap Order Property For a ““MinHeap”” The root of the heap is the ___________ value in the tree”
smallest
“Heap Order Property For a ““MinHeap”” The ““min heap property”” requires that each node’s key is _______(operator) the keys of its children”
<=
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
Big Oh int sum = 0; cout «_space;value if (count < 20) { area = (1.0 / 2.0) * base * height; total = total + current;
O(1)
“Big Oh for (int j = 1; j <= n; j++) { cout «_space;"”this prints n times”” «_space;endl; }”
O(n)
“Big Oh for (int j = 1; j<= n; j++) { for (int k=1; k <= n; k++) { cout «_space;"”this prints n^2 times”” «_space;endl; } }”
O(n^2)
“Big Oh for (int j = 1; j <= sqrt(n); j++) { cout «_space;"”this prints n^1/2 times”” «_space;endl; }”
O(n^1/2)
“Big Oh for (int j = n; j > 0; j /= 2 ) { cout «_space;"”this prints lg n times”” endl; }”
O(lg n)
