Spring 2016
This exam covers the topics of week1 – week5.
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.
Array and linked list
Link list are good for insertion in the middle of the list, but poor at random access. While the array is good at random access, it is poor at insertion except insert at last place. In addition the array has minimal storage and improves caching.
7 functions
Definition of big O, big Omega, big Theta
Counting primitive operations of pseudo code
Cost analysis for algorithms with loops (insertion sort algorithm, selection sort algorithm, Fibonacci iterative algorithm, prefix avg.)
Cost analysis for algorithm with recursive calls (Fibonacci recursive algorithm, binary search algorithm)
· Definition and Main Methods:
o A stack is a collection of objects that are inserted and removed according the the last-in first-out(LIFO) principle.
o Methods:
§ push(e)
§ pop()
§ size()
§ isEmpty()
§ top()
· Implementation
and Cost
|
Method |
Array-based |
LinkedList-based |
|
size |
O(1) |
O(1) |
|
IsEmpty |
O(1) |
O(1) |
|
top |
O(1) |
O(1) |
|
push |
O(1) |
O(1) |
|
pop |
O(1) |
O(1) |
· Applications
o Check weather or not parenthesis matches correctly
o Evaluate a math expression
o Calculate the spans
· Definition and Main Methods:
A collection of objects that are inserted and removed according to the first-in first-out (FIFO) principle.
Methods: enqueue(e), dequeue(), size(), isEmpty(), front()
· Implementation
and Cost
|
Methods |
Array (front is the end of array) |
Circular Array |
Linkedlist-based |
|
Enqueue |
O(1) |
O(1) |
O(1) |
|
dequeue |
O(n) |
O(1) |
O(1) |
|
Front |
O(1) |
O(1) |
O(1) |
|
isEmpty |
O(1) |
O(1) |
O(1) |
|
Size |
O(1) |
O(1) |
O(1) |
· Applications
o Simulate the game of 1,2,3,4,5 Apple source.
|
Operations |
ArrayList |
|
size, isEmpty |
O(1) |
|
get(i) |
O(1) |
|
set(i,e) |
O(1) |
|
add(i,e) |
O(n) |
|
remove(i) |
O(n) |
When we take the strategy of doubling the away when it is full, the cost of add(size(),e) is:
Best case is O(1)
Worst case is O(n)
Amortized
cost is O(1)
When we take the strategy of increasing the away by one or fixed size when it is full, the cost of add(size(),e) is:
Worst case is O(n)
Amortized
cost is O(n)
· Definition and Main Methods:
· Implementation and cost
|
Operations |
Doubly Linked List |
|
isEmpty(), size() |
O(1) |
|
First(), last(), before(p), after(p) |
O(1) |
|
addFirst(e) |
O(1) |
|
addLast(e) |
O(1) |
|
addBefore(p,e) |
O(1) |
|
addAfter(p,e) |
O(1) |
|
set(p,e) |
O(1) |
|
remove(p) |
O(1) |
· Applications
o PQ
1. Sorted
2. Unsorted
· Definition and Main Methods:
· Implementation and Cost
· Applications
o Algorithm: preOrder(v)
o Algorithm: postOrder(v)
· Applications
o Algorithm: InOrder()
· Definition and Main Methods:
o For all levels i of 0,1,...,h-1, it have the maximum number of node
o in level h-1, all the internal nodes are to the left of external nodes
o there is at most one node with one child, which must be a left child
o Methods: add(o), remove()
· Implementation and Cost
o For complete tree Height, h = lg n
· Applications
o Heap
· Definition and Main Methods:
o Stores a collections of entries, the entries form a complete tree
o For every node other than root, it key is greater or equal to the key stored at its parent.
· Implementation and Cost
o Heap is best implemented with ArrayList
§ Upheap(i)
§ downHeap(i)
§ parent(i), left(i), right(i), hasLeft(i), hasLeft(i)
· Applications
o Heap based PQ implementation
o In place heap sort algorithm
· Definition and Main Methods:
o
A priority queue stores a collection of
prioritized elements that supports arbitrary element insertion but support
removal of elements in order of priority.
entry = (key, value) Comparator: complete ordering
o Main methods: insert(k,v), removeMin(), min(), size(), isEmpty()
o Implementation and Cost
|
Operation |
Heap |
Sorted Positional List |
Unsorted Positional List |
|
size(), isEmpty() |
O(1) |
O(1) |
O(1) |
|
min() |
O(1) |
O(1) |
O(n) |
|
insert(k,v) |
O(lg n) |
O(n) |
O(1) |
|
removeMin() |
O(lg n) |
O(1) |
O(n) |
· Applications
o Algorithm PQ-SORT()
o (Later: Huffman coding, shortest path, minimum spanning tree)
· Build a maximum heap
o Two ways to build the heap
§ Bottom up construction by merging heaps – O( n)
§ Increase the heap one by one from left to right of the array - O(n log n)
· Sort – repeatedly put the next maximum to its final location – O(n log n)
o Remove the biggest from the room and put it after the heap
|
Sort Algorithm |
Description |
Cost |
Comments |
|
Bubble |
Compare and swap element next to each other |
O(n2) Best case: Ω(n) |
Simple to understand, not a efficient alg, ok for really small dataset |
|
Insertion |
In-place,
divides the sequence |
O(n2) O(n+d) |
Good best case, good for almost sorted data O(n+d) where d is the number of inversions. |
|
Selection |
In-place |
O(n2) |
For small data |
|
PQSort 1 |
Use a PQ( sorted sequence) as temp storage |
O(n2) Best case: Ω(n) |
Variation of insertion sort |
|
PQSort 2 |
Use a PQ (unsorted sequence) as temp storage |
O(n2) |
Variation of selection sort |
|
PQSort 3 |
Use a PQ (heap) as temp storage – HeapSort |
O(nlogn) |
Guaranteed
cost |
|
InPlaceHeapSort |
In-place,
uses a heap tree |
O(n log n) |
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) |
Algorithm
HuffmanCoding()
Note: You need to be able to illustrate the running steps and result.
Algorithm TreeTraversal() - generate the code table
Algorithm
Decode()
Related sections in the textbook:
Chapter 3 3.1-3.5
Chapter 4
Chapter 5 5.1.1 5.2 5.5
Chapter 6
Chapter 7
Chapter 9
Chapter 13 13.4
1.
R-4.8
2. R-4.10, R-4.11, R-4.13
3. R-9.7 illustrate the selection sorting
4. R-9.8 illustrate the insertion sorting
5. R-9.10
6. R-9.12
7. R-9.13 illustrate the in-place heap sorting
8. R-9.19
9. R13.11