Karteikarten
Algorithms and Data Structures - Basic Data Structures
Karten in diesem Stapel (34)
- 1What is an algorithm? (Def)An algorithm is a method or process followed to solve a problem
- 2What do we assume about random access machines? (3 things)1. Memory consists of an infinite array
2. Instructions are executed sequentially, one at a time
3. All instructions take unit time. Running time is the number of instructions executed. - 3What is an array?An ordered sequence of elements a1,a2....an is called an array. Values are stored in consecutive memory cells (we usually don't care where exactly). All array elements are of the same type.
- 4How do we find the ith element of an array and how long does it take?The ith element is expressed in terms of n (the size). Since addresses are in consecutive cells and we can access the address by just adding two numbers, the time taken to find the ith element is constant.
- 5What if we want to erase an array element?The rest of the elements have to have their addresses adjusted. The worst case time is O(n).
- 6What is a linked list?A list is made up of nodes. Each node stores an element plus a pointer to another node. The fist node is the head, the last node (the tail) points to null. The nodes may be scattered all over the memory, as addresses to find the next pieces of data are stored by the pointers.
- 7We would like L.find(i) to find the ith node of a list. How can we do this? How long will it take?As we don't know the memory location, we must cycle through the entire list to find i. So the worst case time taken increases linearly with respect to list size.
- 8How can we add something to the head or tail of a list?We must fix references - new node is inserted, stored as head, points to old head. Or last node is pointing to new location, new node is inserted, then points to null.
- 9How is inserting into a linked list at position i different to inserting it after a node N?Inserting at i - we must iterate through the ilst to find where i is, change the pointer of i-1 and have the new node point to i.
Inserting after N - just add the node in and have N point to the new node and the new node point to the node originally after n. - 10How does speed of: Data acess and insertion/deletion compare in arrays vs linked lists?Data access - fast in arrays, does not depend on list size. Slow in LLs, does depend on size of list.
Insertion/deletion - slow in arrays, all data beyond point of change has to be moved as data is in consecutive cells. Fast in LLs, just have to update pointers. - 11What are doubly linked lists and what are the nodes at the end called/what do they do?A node in a doubly linked list stores two references: a next link and a prev link.
We add two dummy nodes at the ends of the list - the header has a valid next reference but a null prev reference, the trailer vice versa. A doubly linked list needs to store references to the two sentinel nodes and a size counter keeping track of the number of nodes. An empty list would have the two sentinel nodes pointing to each other. - 12What is a circularly linked list?A circularly linked list has the same kind of nodes as a singly linked list - each node has a next pointer and an element. The CLL has no beginning or end, the tail points to the head. Instead of references to the head and the tail, we mark a node as the cursor. The cursor is the starting node when traversing.
- 13What is a stack?A stack is a collection of objects that are inserted and removed according to the last in first out principle.
Objects can be inserted into a stack at any time, but only the most recently inserted object can be removed at any time - 14What do push(e), pop, size, isEmpty and top do (in a stack)push(e) inserts e at top of stack
pop removes and returns top element of stack (error if stack is empty)
size returns number of elements in stack
isEmpty returns bool indicating if stack is empty
top returns top element in stack without removing it, error if sack is empty - 15what is a queue?A queue is a colletion of objects inserted and removed according to the first in first out principle
Element access and deletion are restricted to the first element in the sequence, called the front of the queue
Element insertion is restricted to the rear of the queue - 16What are the methods enqueue(e), dequeue, size, isEmpty and front (queues)?enqueue(e) - inserts e at rear of queue
dequeue - removes and returns queue element from front, error if queue is empty
size - returns number of elements in queue
isEmpty - returns boolean indicating if queue is empty
front - returns front element of queue, without removing it, error if queue is empty - 17How do you implement a stack using arrays? (incl methods size, isEmpty, top, push and pop).Stack consists of N element array S, and integer variable t that gives top element of stack. t is initialised to -1, use this value for t to identify an empty stack. size of stack is t+1.
size returns t+1
isEmpty returns t<0
top returns s[t], err if t=-1
push(e) t=t+1, s[t] = e, unless size=N
pop e=s[t], s[t]=Null, t=t-1, return e, (unless isEmpty, in which case throw exception) - 18What are the benefits and drawbacks of implementing a stack using an array?-Time efficient - time taken by all methods does not depend on size of stack
-Fixed size of N can be serious limitation: if size of stack is much less than size of the array, we waste memory; if size of stack exceeds size of array, the implementation will generate an exception
Array-based implementation has fixed capacity. - 19How can we implement a queue using an array? (not incl methods)Use two variables f and r. f is an index to the cell of Q storing the front of the queue.
r is an index to the next available array cell in Q, ie the cell right after the rear of Q. if Q is empty, f=r
initially f=r=0, indicating queue is empty
after each enqueue, increment r. after each dequeue, increment f.
As r is never decremented, afte N enqueues, we would get array out of bounds error - this can be avoided by letting r and f wrap around the array, by using module N arithmetic. - 20What would the methods be by using an array to implement a queue? (size, top, isEmpty, enqueue, dequeue)size - return (N-f+r)mod N
isEmpty return (f=r)
top: unless isEmpty then return Q[f]
enqueue(e): unless size = N-1, Q[r] = e, r=r+1 mod N
dequeue: unless isEmpty then temp = Q[f], Q[f] = null, f=f+1modN, return temp - 21What are the benefits and drawbacks of implementing a queue using an array?If the size of the queue is N, then f=r and the isEmpty method returns true when it should be false. We avoid this by keeping the maximum number of elements to N-1.
Array based implementation is time efficient, all methods run in constant time
Capacity of queue is fixed. - 22What is a hash table?A hash table consists of a bucket array and a hash function. A bucket array is an array A of size N (the capacity), each cell of A is thought of as a bucket containing some key-value pairs.
- 23What is the hash function h and how is it used?h is a function mapping each key k to an integer in the range [0,N-1]
h(k) is an index into the bucket array A ,that is, we store a key-value pair (k,v) in the bucket A[h(k)]
If there are two keys with the same hash value h(k), then two different entries will be mapped to the same bucket. In this case, a collision has occured. - 24Can there be entries in a hash table with the same key? Can there be entries in the hash table with the same value? Can there be entries in the hash table with the same key and same value?1. No, keys must be unique (otherwise it's a collision)
2. Yes
3. No (see 1) - 25What are the goals of a hash function?Goal: disperse the keys in an apparently random way/scramble the keys uniformly.
Practical goals: hash function should be efficiently computable. Each table position should be equally likely for each key. - 26How does separate chaining handle collisions?Each bucket A[i] stores a list holding the entries (k,v) s.t. h(k) = i
Performance: cost is proportional to length of list. Average length = N/M (N is amount of data, M is size of array) . Worst case: all keys hash to same list - 27How does linear probing handle collisions?In linear probing, if we try to insert an entry into a bucket that is occupied, then we try next at A[(i+1) mod N], and then [i+2] etc until we find an empty bucket.
Insert and search cost depend on length of cluster
avg length of cluster is N/M (M=array size). Worst case: all keys hash to the same cluster - 28How does quadratic probing handle collisions?Quadratic probing iteratively tries the buckets A[i+f(j) mod N] for j=0,1,2.... where f(j) = j^2, until finding an empty bucket
Quadratic probing avoids clustering that occurs with linear probing, but creates secondary clustering
QP may not find an empty bucket in A even if one exists - 29How does double hashing handle collisions?Choose secondary function h', if h maps k to an already occupied bucket A[i], then try A[(i+f(j)) mod N) for j=0,1,2.... where f(j) = jh'(k)
Secondary hash function should not evaluate to zero - 30When are different collision handling methods appropriate? ie open addressing vs separate chainingOpen addressing schemes (ie not separate chaining) are more memory efficient than separate chaining
Separate chaining method is either competitive or faster than the other methods - 31How do we handle deletions in hash tables?Deletions must not hinder future searches - if a bucket is simply left empty this will hinder future probes. But the bucket should not be left unusable. To solve this we use tombstones after deletion. If a tombstone is encountered when searching for a key, we can continue, if a tombstone is encountered during insertion, we should continue probing (to avoid creating duplicates), but then the new record can be placed where the tomstone was found.
- 32How do we handle the fact that using tombstones lengthens average probe sequence distance?Sol 1: local reorganisation: after deleting a key, continue to follow the probe sequence of that key and move records into the vacated bucket
2: Periodically rehash the table by reinserting all records into a new hash table. If yo uhave a record of which keys are accessed most these can be placed where they will be found most easily. - 33What features must a recursive algorithm have?A recursive algorithm must have a base case, it must change its state and move towards the base case, and it must call itself, recursively.
- 34What is backtracking (recursive algorithms)?A technique for problems with many candidate solutions but too many to try. The general idea is to build up the solution one step at a time, backtracking when unable to continue.
Informationen
- Beschreibung
- Karteikarten am Algorithms and Data Structures - Basic Data Structures, erstellt von SEZ McKelvey am 15/03/2018.
- Erstellt von
- SEZ McKelvey
- Aufrufe
- 2
- Bewertung