This exam covers the topics of week5 – week10.
You need to know the data structure names, and method names. You need to know the algorithm of the methods and their cost. You should also make the appropriate choice of data structures to real life problems. You need to be able to illustrate the algorithm running loop by loop with small sample data.
Merge Sort
O(n
log n)
Alg
Sort – sort left and right half separately, then merge
Divide and Conquer
method
Quick Sort
Average O(nlogn), worst case O(n2)
Sort Alg,
the choice of pivot
Divide and Conquer
method
Sort complexity
Comparison based: Omega(n log n)
Linear sorting
Bucket sort
Radix sort
Counting sort
Sort comparison
|
Sort Algorithm |
Description |
Cost |
Advantages |
Best Size |
Stable? |
In-place? |
|
Bubble |
Compare and swapping if wrong order |
O(n2) Best O(n) |
Easy code |
None |
Yes |
Yes |
|
Insertion |
In-place, divides the
sequence |
O(n2) |
Good best |
Small or almost sorted
sequence O(n+s) |
Yes |
Yes |
|
Selection |
In-place |
O(n2) |
|
Small |
Yes (Note1) |
Yes |
|
PQSort 1 |
Use a PQ(sorted
sequence) as temp storage. Variation of insertion sort |
O(n2) |
|
|
Yes |
No |
|
PQSort 2 |
Use a PQ (unsorted
sequence) as temp storage. Variation of selection sort |
O(n2) |
|
|
Yes |
No |
|
PQSort 3 |
Use a PQ (heap) as temp
storage – HeapSort |
O(nlogn) |
Guaranteed cost |
|
No |
No |
|
InPlaceHeapSort |
In-place, uses a heap tree The cost of building max
heap bottom up is O(n) The cost of building max
heap from left to right of the array is O(n log n) |
O(n log n) |
Guaranteed cost |
Medium(fit in memory) |
No |
Yes |
|
Merge |
For large data, can be
parallelized |
O(n log n) |
|
Large (need external temp
space) |
Yes |
No |
|
In place Quick |
Truly fast |
Medium(fit in memory) |
No |
Yes |
||
|
Radix/Bucket |
O(d(N+n)) d:number of
sorts N: bucket number n: size of input data |
|
Small number of data whose
value is within predefined small range |
Yes |
No |
Note1:
selection sort can be implemented as a stable sort. Instead of swapping, do a
remove and insert the next minimum value. This suggests the data structure
should be good at insert/remove – a linked list will do.
· Definition and Main Methods:
o Store a collection of objects of paired (key, value). Map’s key is unique,
o Methods:
§ get(k)
§ put(k,v) – if exists, replace the old value
§ remove(k)
· Implementation
and Cost
|
Map Implementation |
Unordered Array |
Unordered Linked List |
Lookup Table (Ordered array) |
Hash Table |
BST |
AVL |
Multiway Tree |
(2,4) Tree |
|
get(K) |
O(n) |
O(n) |
O(log n) |
Expected:O(1) |
O(h) |
O(log n) |
O(f(d)h) |
O(logn) |
|
Put(K,V) |
O(n) |
O(n) |
O(n) |
Expected:O(1) |
O(h) |
O(log n) |
O(f(d)h) |
O(logn) |
|
Remove(K) |
O(n) |
O(n) |
O(n) |
Expected:O(1) |
O(h) |
O(log n) |
O(f(d)h) |
O(logn) |
|
Fast search |
Constant expected time |
Log n<=h<=n |
|
|
|
· A way to implement map.
o Bucket array
o Hash function – map key to the address of the bucket array
o Basic idea Bucket[h(e.key)] = e
· Collision
o When h(e1.key) = h(e2.key)
o Two schemes to handle
§ Chaining
§ Open Addressing
1. Linear probe
2. Quadratic probe (*)
3. Double hashing
· Illustrate
· Definition and Main Methods:
o Store a collection of objects of paired (key, value). For all node Left child’s key <= it’s key <= right child’s key
o Following the textbook, all valid entries are stored in internal nodes and external nodes are dummy sentinel nodes for simplifying algorithms.
o Methods:
§ Some basic methods
1. insertLeft(v,e) insertRight(v,e), TreeInsert(e) (recursive and iterative way)
2. remove(v) where v is a node whose entry need to be removed
3. search(k)
§ minimum(v): find the minimum key in the subtree rooted at v
§ maximum(v): find the maximum key in the subtree rooted at v
§ successor(k) assume keys are unique, find the smallest next key value > k, return null if it does not exist
§ predecessor(k) assume keys are unique, find the previous greatest key > k, return null if it does not exist
· Illustrate
· Definition and Main Methods:
o A balanced Binary Search Tree.
§ Store a collection of objects of paired (key, value). For all node v, Left child’s key <= it’s key <= right child’s key.
§ Left child’s height and right child’s height is different at most 1.
o Methods:
§ All binary search tree’s methods
§ Alg rebalance(z)
§ Alg restructure(z)
· Illustrate
See class web page
· every node contains 1-3 key values, and 2-4 children
p1,(k1,v1),p2
p1,(k1,v1),p2,(k2,v2),p3
p1,(k1,v1),p2,(k2,v2),p3,(k3,v3),p4
k1<k2<k3
all of the keys in the sub tree pointed by p1 < k1 < all the keys in the sub tree pointed by p2 < …
· all external nodes are at the same height.
Overflow – split – The split can propagate up to root node – the tree height grows by 1
Underflow – then
Transfer (borrow some its sibling node if it has 3 nodes or more), otherwise
Fusion (merge with sibling) – propagate upto the root, the tree height shrinks by 1
|
Operation |
Time |
|
size, isEmpty |
O(1) |
|
find,
insert, remove |
O(log n) |
Sorting
Give a complete pseudo-code description of
the recursive merge-sort algorithm take takes an array as its input and
output
R12.7, R12.9, R12.18, R 12.13, C12.39, C12.44
Use radix sort to illustrate the sorting steps for
329,457,657,839,436,720,355
Hash:
R10.6, R10.7, R10.9
BST,AVL:
R11.2, R11.8, R11.9, C11.35, C11.41
Write pseudo code for binary search tree’s minkey(), maxkey(), successor()
2-4 Tree
R-11.22 a) 2-4 tree insertion
b) Remove 10, 16, 18 from above tree one by one in the order listed.