adt Flashcards
What methods: Stack Interface
1) pop
2) push
3) size
4) isEmpty
5) top
Describe push(o)
Inserts object o onto top of stack
Describe pop()
Removes the top object of stack and returns it
Describe size()
Returns the number of objects in stack
Describe isEmpty()
Return a boolean indicating if stack is empty.
Describe top()
Return the top object of the stack, without removing it
Name one limitation of a basic array implementation of a stack. What are some possible solutions?
In short:
The linked-list approach has worst-case O(1) guarantees on each operation; the dynamic array has amortized O(1) guarantees.
The locality of the linked list is not as good as the locality of the dynamic array.
The total overhead of the dynamic array is likely to be smaller than the total overhead of the linked list, assuming both store pointers to their elements.
The total overhead of the dynamic array is likely to be greater than that of the linked list if the elements are stored directly.
Neither of these structures is clearly “better” than the other. It really depends on your use case. The best way to figure out which is faster would be to time both and see which performs better.
What are the orders of the methods in the array based stack?
1) pop O(1)
2) push O(1)
3) size O(1)
4) isEmpty O(1)
5) top O(1)
What are the orders of the methods in linked-based stack
1) pop O(1)
2) push O(1)
3) size O(1)
4) isEmpty O(1)
5) top O(1)
What is the best implementation of a stack?Array or Linked-List? Explain
The linked list may be better because it doesn’t have a fixed size. Also, when the array-stack is made extensible it become less fast: pop() and push become O(n) vs. 0(1) in the linked-stack. The array based implementation will also need a block of free contiguous memory, whereas the linked list can be scattered around memory using references.
What are the Queue methods?
) Enqueue
2) Dequeue
3) Front
4) size
5) isEmpty
What are the orders of methods in linked-queue
All O(1)
What is a naive array-based queue?
Because the dequeue method leaves empty unused spaces behind it, it’s wasteful. The data continually crawls up along array moving to the right. The problem can be fixed by using a circular array
What is the formula for the size of a queue in a circular array?
Size = (N + rear - front) % N
What is a deque?
<p><p><p>Pronounced 'deck', it is a queue that allows insertion/deletion from either end of the queue.</p></p></p>
What are the methods of the deque?
1) insertFirst(o)
2) insertLast(o)
3) removeFirst()
4) removeLast()
5) size
6) isEmpty
7) front
8) rear
How can a dequeue be implemented?
1) Circular Array
2) Doubly Linked List
What is a vector?
Stacks and Queues are examples of ADTs that support insertion and removal at pre-specified points.
Stacks: insertion / removal at the top
Queues: insertion at the tail / removal at the head
Sequence ADT’s allow for insertion/removal anywhere in the data. A vector is just one type of sequence ADT and one which uses rank to access its elements.
What are the core methods of a vector ADT
1) elemAtRank(r)
2) replaceAtRank(r,e)
3) insertAtRank(r,e)
4) removeAtRank(r)
5) isEmpty()
6) size()
What are the orders of the methods in array based Vector ADT.
1) elemAtRank(r) O(1)
2) replaceAtRank(r,e) O(1)
3) insertAtRank(r,e) O(n) * not amortized
4) removeAtRank(r) O(n) * not amortized
5) isEmpty() O(1)
6) size() O(1)
What is the Order of inserting into an extendable array?
Despite having a loop, extendable arrays give amortized O(1) insertion, and not O(n). This is because when you spread the cost of all the operations out you find that it is possible (in theory) to save up operation-tokens such that you can afford a copying of the element into a bigger array.
What is better? A linked-list, or an array-based implementation of a vector?
The orders for a linked appraoch would be:
1) elemAtRank(r) O(n) * bad
2) replaceAtRank(r,e) O(n) * bad
3) insertAtRank(r,e) O(n)
4) removeAtRank(r) O(n)
5) isEmpty() O(1)
6) size() O(1)
For replaceAtRank and insertAtRank the need to shift elements has been replaced with the need to traverse them giving O(n) time. However, the need to traverse for
elemAtRank and replaceAtRank gives additional cost. Thus, the array based approach is superior, especially from an amortized perspective.
What are the operations of the list-based map adt
1) size()
2) isEmpty()
3) get(k)
4) put(k,v)
5) remove(k)
6) keys()
7) values()
8) entries()
How can we think of map, in terms of entries?
<p><p><p>You can think of a list based map as a list of entries. An entry is simply a single pairing of a key and value (K,V).</p></p></p>
What is the adapter pattern?
In software engineering, the adapter pattern is a software design pattern that allows the interface of an existing class to be used from another interface.[1] It is often used to make existing classes work with others without modifying their source code.
What are the ways you can implement a map?
1) Linked List ( A list of entries)
2) Arrays (Hash mapping)
What is a tree?
A Tree is a hierarchical ADT where data is related in terms of parent-child relationships.
Each element (node) in the tree has at most 1 parent.
Each element (node) may have 0 or more children.
Each tree will include exactly one element (node), known as the root, which has no parent.
What are the operations of a tree?
root() r-> the Position for the root
parent(p) r-> the Position of p’s parent
children(p) r-> an Iterator of the Positions of p’s children
isInternal(p) r-> does p have children?
isExternal(p) r-> is p a leaf?
isRoot(p) r->is p==root()?
size() r->number of nodes
isEmpty() r->tests whether or not the tree is empty
iterator() r-> an Iterator of every element in the tree
positions() r-> an Iterator of every Position in the tree
replace(p, e) r-> the element at Position p with e
Describe the steps by which items are removed from a heap.
- Remove the root node (current min entry)
- Replace this node with the last item in the heap, node L
- Perform a downheap to re-establish the ordering property.
- Update the last reference.
Two ways hash map can be implemented?
1) Hash code map: Assign an integer to every key
2) Compression map: Concerts an Int to int in the range (0 - N-1)
How do you make a compression map?</p></p></p>
A compression map sometimes uses:
1) The division method (%n)
This method requires that n be prime so that their are an even spread of hash integers, and not too many zeros.</p></p></p>
What is the MAD method in relation to hash maps?
MAD stands for multiply, add, divide. It’s a way of deriving a fairly even spread of integers for a compression map by doing the following:
1) multiplying by some constant
2) shifting the number by some contant
3) modulus the answer by some number.
(ai + b) % N
Constraint: a % N cannot be equal to zero.</p></p></p>
One application of binary trees is a heap. Heaps make use of two key properties: the order and structural completeness properties. Give definitions for each of these properties.</p></p></p>
Order Property: key(parent) ≤ key(child)
Structural “Completeness” Property: all levels are full, except the bottom, which is “left-filled”
</p></p></p>
How could you use a hash map if your keys were primitive values?</p></p></p>
1) Integer Cast: You can translate the bits associated with the primitive into an integer.
2) Component Sum: Break the bits into integer size blocks, cast them to integers, and sum these integers.
3) Polynomial Sum: same as component sum, but multiply each term by a constant polynomial coefficient:
</p></p></p>
Why is polynomial sum better than component sum for deriving integers from primitives?</p></p></p>
Naïve solution: Use component sum
h(“dog”) = (int) ‘d’ + (int) ‘o’ + (int) ‘g’ = 100 + 111 + 103 = 314
h(“god”) = (int) ‘g’ + (int) ‘o’ + (int) ‘d’ = 103 + 111 + 100 = 314 !?!?!
Better solution: Use polynomial sum (p=3):
h(“god”) = 103 + 1113 + 1009 = 1,336
h(“dog”) = 100 + 1113 + 1039 = 1,360
For 50,000 English words, a value of p = 33, results in less than 7 collisions!!!</p></p></p>
In the open addressing strategy of collision-avoidance, what can be done when a collision occurs?
1) Linear Probing
2) Double Hashing
3) Re Hashing.
What problem might arise with linear probing, which needs to resolved?
When items are removed from the hash-map,they will leave behind nulls. These nulls will cause a linear probing algorithm to stop running because it thinks the key being searched for doesn’t exist in the hash map. Otherwise it would have been inserted into the first empty space when probing after a collision. The solution is to enter in AVAILABLE tokens after a remove operation, so that linear probing will continue…
Advantages of the open address collision strategy?
Do not require an auxiliary data structure
Have finite capacity but support rehashing
Describe the Last Occurrence function
Boyer-Moore’s algorithm preprocesses the pattern P and the alpha (weird sigma) to build the last-occurrence L mapping sigma to integers where L(c) is defined as;
> the largest index i such that p[i] = c or
> -1 if no such index exists
Pseudo-code Boyer Moore:
Algorithm BoyerMooreMatch(T,P,Sigma)
Input: Text T of size n and pattern P of size m
Output: Starting index of a substring of T equal to P or -1 if no such substring exists
L -> lastOccurrenceMap(P,Sigma)
i -> m - 1
j -> m - 1
do
if T[i] = P[j] then
if j = 0 then return 1
else
i -> i - 1
j -> j - 1
else
l -> lastOccurrence(L, T[i])
i -> i + m - min(j, l + 1)
j -> m - 1
until i < n - 1
return -1
Example of Boyer Moore algorithm
finish this answer
What is a binary search tree?
re-check answer
A binary search tree is a tree that satisfies the following properties:
Each internal node holds a (unique) value.
A total-order relation (~) is defined on those values.
Reflexive: k ~ k
Antisymmetric: if k1 ~ k2 and k2 ~ k1 then k1 = k2
Transitive: if k1 ~ k2 and k2 ~ k3 then k1 ~ k3
All the values (ki) in the left sub-tree of a node with value k satisfy the relation ki ~ k.
All the values (kj) in the right sub-tree of a node with value k satisfy the relation k ~ kj
> In the open addressing strategy of collision-avoidance, what can be done when a collision occurs?
1) Linear Probing: When a collision occurs you can probe along the map in ones until you find an empty. Later, when you wish to find this entry, you will probe in this linear fashion until you meet either k (found it), null (k doesn’t exit), or N cells have been traversed (k doesn’t exist).
</p></p>
What problem might arise with linear probing, which needs to resolved?
When items are removed from the hash-map,they will leave behind nulls. These nulls will cause a linear probing algorithm to stop running because it thinks the key being searched for doesn’t exist in the hash map. Otherwise it would have been inserted into the first empty space when probing after a collision.
What is an AVL Tree? Explain any properties that an AVL tree must satisfy
AVL trees are an example of a self-balancing binary search tree.
AVL trees must satisfy the height-balance property:
For every internal node v of T, the heights of the children of v can differ by at most 1. AVL trees have expected performance O(log n).
<p>Lets say don't want our hash map to require the use of an auxiliary data structure (list) so use the open addressing scheme as our collision strategy. What are our options within this scheme for dealing with collisions?</p>
1) Linear Probing
2) Quadratic Probing
3) Double hashing
Describe with diagrams trinode restructuring.
nothing here
<p>What is double hashing?</p>
<p>Double Hashing is an open addressing solution. If our original compression function (division method, mad method) results in a collision (the key already has a value) then we use a secondary hash function to probe the hash map until we find an empty bucket.
Lets say our original compression function was i = h(k) giving our position in the hash map as a[i]. Following a collision, we now use h'(K) in the following way to probe for an empty bucket:
a[ (i + j*h'(k)) % N]
where j = 0,1,2,3,..... until a bucket is found (j allows probing)
But how do we derive h'(k)?
A common h'(k) is h'(k) = q - (k mod q) where q is a prime number smaller than N and remember, N must also be prime.
</p>
<p>What is linear probing?</p>
<p>When a collision occurs you can probe along the map in ones until you find an empty. Later, when you wish to find this entry, you will probe in this linear fashion until you meet either k (found it), null (k doesn't exit), or N cells have been traversed (k doesn't exist).</p>
What is a Queue? List the operations commonly associated with the Queue Abstract Data Type.
A queue is a container of objects / values. Insertion and removal based on first-in-first-out (FIFO) principle. Objects can be inserted at any time, but only the object that has been in the queue the longest can be removed.
Items can be enqueued (insertion) or dequeued (removal).The front of the queue is the next item to be dequeued. The rear of the queue is where the last item was enqueued.
Core Operations:
enqueue(v): Inserts value v onto rear of queue
dequeue(): Removes the value at the front of the queue and returns it
front(): Return the value at the front of the queue, without removing it
Support Operations:
size()
isEmpty():
How to dequeue in a Queue - Give pseudocode
re-check this answer
Algorithm dequeue()
Input: none
Output: the top object
T <- size - 1
return T.element
