adt Flashcards

Question

What is the adapter pattern?

Answer 1

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.

Answer 2

1) Linked List ( A list of entries) | 2) Arrays (Hash mapping)

Answer 3

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.

Answer 4

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

Answer 5

1. Remove the root node (current min entry) 2. Replace this node with the last item in the heap, node L 3. Perform a downheap to re-establish the ordering property. 4. Update the last reference.

Answer 6

1) Hash code map: Assign an integer to every key | 2) Compression map: Concerts an Int to int in the range (0 - N-1)

Answer 7

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.

Answer 8

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.

Answer 9

Order Property: key(parent) ≤ key(child) Structural “Completeness” Property: all levels are full, except the bottom, which is “left-filled”

Answer 10

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:

Answer 11

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 + 111*3 + 100*9 = 1,336 h(“dog”) = 100 + 111*3 + 103*9 = 1,360 For 50,000 English words, a value of p = 33, results in less than 7 collisions!!!

Answer 12

1) Linear Probing 2) Double Hashing 3) Re Hashing.

Answer 13

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...

Answer 14

Do not require an auxiliary data structure | Have finite capacity but support rehashing

Answer 15

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

Answer 16

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

Answer 17

finish this answer

Answer 18

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

Answer 19

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).

Answer 20

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.

Answer 21

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).

Answer 22

1) Linear Probing 2) Quadratic Probing 3) Double hashing

Answer 23

nothing here

Answer 24

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.

Answer 25

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).

Answer 26

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():

Answer 27

Collision chaining is usually competitive or faster than alternative methods depending on the load factor of the bucket array? If memory is in short supply their may an argument for choosing an open address strategy.

Answer 28

1) pre-order traversal 2) in-order traversal 3) post-order traversal 4) Euler traversal 5) breadth first traversal

Answer 29

The hash code and the compression function? The hash code is the mapping of the key (which not be an int) into an integer. The compression function is what compresses these hash code intgers into a narrower range of integers.

Answer 30

Algorithm dequeue() Input: none Output: the top object T <- size - 1 return T.element

Answer 31

1) Casting to Integer: (for byte, short, int, char) 2) Summing components (for doubles and longs) 3) Polynomial Hash Codes (Dog & God) 4) Cyclic shift hash codes 5) For objects use the memory address

Answer 32

1) The division method | 2) The MAD method

Answer 33

Two broad collision handling schemes are 1) Separate chaining (an array of lists which hold nodes k and elements v) 2) Open addressing

Answer 34

If a map has to store n entries into N buckets we hope to achieve a number of n/N entries in each bucket. This number is called the loading factor. For a set number of buckets, the speed of operations will slow down with the number of entries. To ensure a fast hash map the loading factor should be kept below some bound. A very low load factor is also wasteful (approaching zero) because it suggests their are too many empty buckets taking up memory.

Answer 35

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.

Answer 36

Yes, the root will never have a parent

Answer 37

Trees make use of the Position ADT and have the following operations: 11 in total: root() returns the Position for the root parent(p) returns the Position of p’s parent children(p) returns an Iterator of the Positions of p’s children isInternal(p) does p have children? isExternal(p) is p a leaf? isRoot(p) is p==root()? size() number of nodes isEmpty() tests whether or not the tree is empty iterator() returns an Iterator of every element in the tree positions() returns an Iterator of every Position in the tree replace(p, e) replaces the element at Position p with e

Answer 38

A Binary Tree is a tree with the following properties: Every node has at most 2 children (degree 2) Each child node is labelled as being either a left child or a right child A left child precedes a right child in the ordering of children of a node

Answer 39

A tree where all nodes have a degree = 0 or degree = 2

Answer 40

1) pre-order traversal 2) in-order traversal 3) post-order traversal 4) Euler traversal 5) breadth first traversal

Answer 41

Logically join the first and last cells in the array: When front (or rear) reaches the end of the array, perform a wraparound by setting it to 0

Answer 42

1) pre-order traversal (root, left, right) (processed as the node is visited) 2) in-order traversal (Left, Root, Right) (Ascending) 3) post-order traversal (Left, Right, Root) (Node not processed till after its children) 4) Euler traversal These common traversals can be represented as a single algorithm by assuming that we visit each node three times. An Euler tour is a walk around the binary tree where each edge is treated as a wall, which you cannot cross. In this walk each node will be visited either on the left, or under the below, or on the right. The Euler tour in which we visit nodes on the left produces a preorder traversal. When we visit nodes from the below, we get an inorder traversal. And when we visit nodes on the right, we get a postorder traversal. 5) breadth first traversal

Answer 43

1) Each internal node holds a (unique) value. 2) 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 3) All the values (ki) in the left sub-tree of a node with value k satisfy the relation ki ~ k. 4) All the values (kj) in the right sub-tree of a node with value k satisfy the relation k ~ kj.

Answer 44

An in-order traversal of a binary search trees visits the values in the order specified by the total-order relation.

Answer 45

1) insert(e) 2) find(e) 3) remove(e)

Answer 46

Yes, but we must do the following: 1) we find the internal node w that follows v in an in-order traversal 2) we then copy w.element() into node v (cause v is going) 3) we then remove node w and its left child z (which must be a leaf)

Answer 47

In the worst case, when a tree of n nodes has a height of n, the order is O(N). But in a perfectly balanced tree the orderis O(log n)

Answer 48

Trees are Hierarchical ADT’s in which data is defined in terms of parent and child relationships between nodes. A Proper Binary Tree is a Tree in which each node has either 0 (external) or 2 (internal) children. A Binary Search Tree is a Binary Tree that holds values whose location is determined by a total order relation. Binary Search Trees are another approach to implementing Maps and Dictionaries that have best case performance O(log n). Performance depends on the height of the tree, and is best when the tree is balanced.

Answer 49

They are self-balancing. They achieve this by satisfying the height-balance property.

Answer 50

For every internal node v of T, the heights of the children of v can differ by at most 1.

Answer 51

Because the tree is always balanced, the expected performance of this operation is O(log n)

Answer 52

``` A deque (pronounced deck) is a container of objects / values. Insertion and removal are based on the first or last-in first or last-out (FLI-FLO) principle. Terminology: ltems can be inserted at the front or back of the deque. ltems can be removed at the front or back of the deque: We insert and remove from both the front and the back. ``` Core Operations: insertFirst(o): Inserts object o onto front of the deque insertLast(o): Inserts object o onto the rear of the deque removeFirst(): ....and returns it removeLast(): ...and returns it Support Operations: size(): isEmpty(): front(): Return the front object in the deque rear(): Return the rear object in the deque

Answer 53

A Vector supports insertion, removal and accessing of objects based on rank. Terminology:Rank: The rank of an object e is an integer value that specifies the number of objects that come before e in vector.

Answer 54

Core Operations: elemAtRank(r): an error condition occurs if the vector is empty or r < 0 or r > size() replaceAtRank(r, e): error condition occurs if the vector is empty or r < 0 or r > size() insertAtRank(r, e): an error condition occurs if r < 0 or r > size() removeAtRank(r): an error condition occurs if S is empty or r < 0 or r > size() Support Operations: isEmpty() size()

Answer 55

Okay, before we begin lets state two truths: 1) A tree of size 1, has a height of 1 (n=1) 2) A tree of size two has a height of 2 (n=2) What about a tree with more than 2 keys? This will be: n(h) = 1 + n(h-1) +n(h-2) (Formula 1) Because the height of the left sub-tree and right sub-tree will always differ by one in a balanced tree with the minimum amount of nodes contained it. ``` Obviously n(h-1) will be higher than n(h2): n(h-1) > n(h-2) ``` Now, if we substitute n(h-1) with n(h-2) in formula (1) we get something interesting: n(h) > 2 x n(h-2) formula(2) It follow from this,that: n(h) > 4 x n(h-4)... n(h) > 8 x n(h-6)... We can summarize this behaviour: n(h) = 2**i(n)(h-2(i)) formula(3) If we had a value for n(h-2(i)) we could sub it into formula(2) and we know that n(2) =2 and n(1) = 1. So, n(h-2i) = n(2), thus (h-2i) = 2 This also means, h/2 -1 = i Now plug this into formula(2) n(h) > 2**(h/2)-1 . n (h – 2 . ( (h/2) – 1 ) ) n(h) > 2**(h/2)-1 . n (h – 2 (h/2) + 2 ) n(h) > 2**(h/2)-1 . n(2) where n(2) = 2 n(h) > 2**(h/2)-1 . 2**1 n(h) > 2**(h/2) Taking logarithms: log n(h) > log ( 2 (h/2) ) log n(h) > h/2 h < 2. log n(h) Thus the height of an AVL tree is O(log n)!

Answer 56

Given an internal node x of a binary search tree T, we splay x by moving x to the root of T through a sequence of restructurings.

Answer 57

1) Zig 2) Zig-Zig 3) Zig-Zag

Answer 58

When x, the value being inserted, has no grandparent.

Answer 59

When x and y are both right children, or they are both left children.

Answer 60

Using amortized analysis we can see that splaying is O(log n) BUT its hard to prove.

Answer 61

Either the found node, or the parent of ending external node.

Answer 62

Splay the new node containing the inserted entry

Answer 63

First splay the tree around the node to be removed. Then remove it, and make the largest left child the new root.

Answer 64

1) Insert(k,e) Insert a new element e with key k into P 2) min() Return (but don’t remove) an element of P with highest priority; error occurs if P empty. 3) remove() Remove from P and return an element with the highest priority; an error occurs if P is empty Support Operations: 4) isEmpty() Returns true if the priority queue is empty, or false otherwise 5) size() Returns the number of elements in the priority queue

Answer 65

ADTs that support insertion and removal at various points

Answer 66

List ADT is a sequence data structure that abstracts the notion of a “place” in a list.

Answer 67

A priority queue is an abstract data type for storing a collection of prioritized elements. Like a queue but, removal is based on a priority

Answer 68

Priority Queues hold entries (key + value) – the key is the priority

Answer 69

Only the element with the highest priority can be removed

Answer 70

A position is a place in the list that a piece of data is stored.

Answer 71

1) Insert(k,e) Insert a new element e with key k into P 2) min() Return (but don’t remove) an element of P with highest priority; error occurs if P empty. 3) remove() Remove from P and return an element with the highest priority; an error occurs if P is empty

Answer 72

Core Operations: replace(p,e): r-> the element formerly at p. insertFirst(e): r-> the position of e. insertLast(e): r-> the position of e. insertBefore(p,e) r-> the position of e. insertAfter(p,e): r-> the position of e. remove(p): Remove from S the element at position p. Support Operations: isEmpty() size()

Answer 73

List-based Strategies 1) unsorted 2) sorted Both strategies give O(n) for some operations: sorted -> insert() unsorted -> min() and removeMin() However, sorted is better because it only results in one O(n) operation vs. two with unsorted.

Answer 74

Link-based Implementation: Nodes are positions Nodes maintain ordering information Link to the next and previous objects in the List. Auxiliary references maintained; front and rear nodes. Keep track of the current size of the list

Answer 75

Approach: Use a doubly linked list A Node is basically a position Finding adjacent nodes is very fast O(1) and simple to do Key positions can be easily identified (front, rear) Need to keep track of the size (size)

Answer 76

A heap is a binary tree that stores keys (key-value pairs) at its internal nodes and that satisfies two additional properties: 1) Order Property: key(parent) <= key(child) 2) Structural “Completeness” Property: all levels are full, except the bottom, which is “left-filled”

Answer 77

h = [log(N+1)] where N = total entries and [] means absolute value

Answer 78

It can be implemented sing a vector. Reading from left to right on the heap you can simply add the values to the vector from left to right, also.

Answer 79

Basic Idea: Removes the element at position p from the List Process (Informal): Modify the links to remove the node from the list. Reduce the size Return the value stored in the node Potential Use Cases: 1. Removal of the element at the front position 2. Removal of the element at the rear position 3. Removal of the last element 4. Removal of element at other positions

Answer 80

Finish Later

Answer 81

Left child = 2*j +1 | Right child = 2*j +2

Answer 82

We insert in three stages. 1) Insert the new entry at the last position in the heap 2) Unheap to restore the order-property. 3) Identfy the new last position in the heap.This means finding the next free space via an in-order traversal. If no available space is found the bottom level must be full, so the new last position will be the leftmost child on the next level.

Answer 83

Upheap terminates when new value is greater than the value of its parent, or the top of the heap is reached.

Answer 84

If we are deleting the last value in the heap, it's easy: we just remove the value. 1) If we are removing any other value, we swap that value with the position of the root so that it too can now be deleted easily. 2) However, we must preserve the order-property by down-heaping. This involves checking whether L is less that its children. If it is not, then L is swapped with the smaller of the two children, and downheap is performed again on L in its new position. 3) Update the “last” reference. Need to do an inverse pre-order traversal (I.e. goto the node that is before the last node in a pre-order traversal). If there is no previous node, then find the last node on the next level up.

Answer 85

Downheap terminates when the key is greater than the keys of both its children, or the bottom of the heap is reached.

Answer 86

Heap sort is where you implement a priority queue ADT using a heap. If it is a min-heap then you add your keys to the heap so that the children are always larger. Remember, that items can only be added the last position of the heap (the leftmost child of the bottom level). However after this key has been added you can recursively swap the key with it's parents if the parent is bigger. This preserves the order-property of the heap. When removing from the min-heap, the root will be the smallest key, so we swap the root with the last position (the only removable position). Now we have removed/returned our first smallest number (sorting) but the min-heap will need to be down-heaped (recursive swapping) again to preserve the order-property. https://www.youtube.com/watch?v=Uxo7UiMco58

Answer 87

List-based 1) Sorted 0(n) for insert 2) Unsorted o(n) for min() and removeMin() Heap based 3) O(log n) for inset() and removeMin() o(1) for everything else. heap = CLEAR WINNER!

Answer 88

Heap sort is O(log n) selection sort O(n**2) insertion sort O(n**2) heapsort = CLEAR WINNER!

Answer 89

Given functions f(n) and g(n), we say that f(n) is O(g(n)) if and only if there are positive constants c and n0 such that f(n) ≤ c * g(n) for all n ≥ n0 formula (1) If we make g(n) in the above formula equal to n, g(n) = n, and this satisfies formula (1) then we can prove that 11n+5 is O(n) Make c equal to 12 for simplicity: 11n + 5 ≤ 12n 5 ≤ 12n - 11n 5 ≤ n Therefore, f(n) ≤ 12 * g(n) for all n ≥ 5

Answer 90

We consider an approximation to be good if it is similar to the actual function, but does not include lower order terms.

Answer 91

Simple Rule: Drop lower order terms and constant factors: 11n + 5 is O(n) 8n2log n + 5n2 + n is O(n2log n)

Answer 92

log n << n << n2 << n3 << 2n

Answer 93

A list is an ADT in it's own right, but it's also part of what are collectively called sequence ADT's. Another sequence ADT is the vector. However, while vectors use the idea of rank, we define the List ADT to be a sequence data structure that abstracts the notion of a “place” in a list.

Answer 94

A position is a place in the list that holds a value. | It is an auxiliary ADT for ADTS in which the values are stored at positions. It's only method is element().

Answer 95

Insertion is carried out relative to a position or a known fixed point. For example, insert bob "after" jane or "before" sandra.

Answer 96

replace(p,e): r-> replaced element insertFirst(e): r-> position of e insertLast(e): r -> position of e insertBefore(p,e): r -> position of e insertAfter(p,e): . r -> position of e remove(p): isEmpty() size() first() last() next() prev()

Answer 97

1) Array list | 2) Linked List (Double)

Answer 98

Linked List is better (Double) "Linked lists have several advantages over arrays. Elements can be inserted into linked lists indefinitely, while an array will eventually either fill up or need to be resized, an expensive operation that may not even be possible if memory is fragmented. Similarly, an array from which many elements are removed may become wastefully empty or need to be made smaller."

Answer 99

The array stores a positions and each position stores its associated index. If insertion/removal occurs then the position must change it's stored index

adt Flashcards

(126 cards)