1
Q
Why do we use asymptotic notation to analyse run time of algorithms in theoretical analysis
A
Usually an algorithm that is asymptotically more efficient is the best choice for all but very small inputs
- we can also use asymptotic notation to characterise other features of algorithms such as space (memory) used
2
Q
What are data structures?
A
data structures are specific methods for storing and accessing information
3
Q
Describe the features and functionality of arrays
A
- arrays are unordered collections of data, that have indexes in order to access them
- must specify the size of the array upon creation (which we may not always know)
- if we run out of space we have to create a new larger array and copy the items over
- difficult to insert into the middle of the array, must insert in item and then shift all others down
4
Q
describe features of linked lists
A
- data can be inserted anywhere easily by inserting a new node and reassigning pointers
- can perform referring, insertion, deleting and searching on the linked list
- can be implemented as singly or doubly linked lists
5
Q
describe the difference between singly and doubly linked lifts
A
- In singly linked lists each node has a next pointer and the last element just points to null
- in a doubly linked list each node points to a previous and next node, the first node in the list’s prev pointer points to null, and the last node in the list’s next pointer points to null
6
Q
Why would we use linked lists over arrays?
A
They are much more efficient
7
Q
name all the update methods that can performed on a linked-list abstract data type
A
- replaceElement(p,e) - p - position, e - element, find item at position p and replace it with value e
- swapElements(p,q) - p,q - two positions, swap contents in elements at positions p and q
- insertFirst(e) - insert into the first position value e
- insertLast(e) - insert into last position value e
- insertBefore(p,e) - p - position, e - element, insert value e before position p
- insertAfter(p,e) -p - position, e - element, insert value e after position p
- remove(p) - remove element at position p
8
Q
What are the steps for an element insertion of insertAfter(p,e)
A
- create a new node v
v.element = e - link v to previous node
v.prev = p - link v to it’s successor
v.next = p.next - link p’s old successor to v
(p.next).prev = v - link p to new successor v
p.next = v
9
Q
What is the cost of the insertion and removal methods for a linked list?
A
- if the position of the node to update is known cost is O(1)
- if the position of the node is unknown cost = O(p) where p is the position in the list as we need to traverse to it to find it
10
Q
What is the advantage of using an array over a linked list?
A
They are easier and quicker to search through due to use of indexes
11
Q
Describe the features of an ordered dictionary
A
- a set of elements and their associated keys, it maintains orders of elements
- supported by dictionary operations
12
Q
What is a look up table/sorted table
A
- taking an ordered dictionary and storing it as an array or vector, so that it’s easier to search or sort through
13
Q
describe the pseudocode for a binary search algorithm
A
- input is an ordered array of elements, with the indexes of the highest and lowest elements (keys wise)
- the midpoint of the list is found, if key is the midpoint, return the element
- otherwise if the key is bigger than the midpoint return the recursive call of binary search with new parameters of the elements in the list between the midpoint and highest element
- otherwise return the recursive call of binary search with new parameters of the elements in the list between the midpoint and lowest element
- keep recursively calling until the base case is hit and the algorithm unwinds itself
14
Q
What is the recursive relation for the recursive binary search algorithm and what is the time complexity of this algorithm?
A
T(n) = {b, if n < 2 : t(n/2) + b, if n >= 2}
- where b is a constant that denotes the time for updating low and high and other overhead
- since n/2 is the highest order term and it can be shown the binary search performs 2^n operations
- which can be written as log2(n) operations, the time complexity = O(logn)
15
Q
Why is T(n) = {b, if n < 2 : t(n/2) + b, if n >= 2} the recursive relation for the recursive binary search algorithm?
A
- If n < 2, it either contains one element in which we know the position of or it contains no elements so is empty so it can’t contain the element we’re searching for
- If n >= 2, time complexity is O(log2(n)) as we start with n elements and halve this every recursive call until n < 2. So this is n/2^i <= 1 which we can rewrite as log2(n) = i
16
Q
Compare the time complexities of the linked list and a sorted array (look up table) for methods findElement, insertItem, removeElement, closestKeyBefore:
A
linked list:
findElement - O(1)
insertItem - O(n)
removeElement - O(1)
closestKeyBefore - O(1)
sorted array:
findElement - O(logn)
insertItem - O(n)
removeElement - O(n)
closestKeyBefore - O(logn)
17
Q
Compare linked lists to sorted arrays in words:
A
- Linked lists have a shorter run time in inserting and deleting items
- Arrays have a shorted run time in searching for items
18
Q
Why are binary search trees an efficient data structure of linked lists and arrays?
A
- They can efficiently, search, sort, delete and insert items into the BST in a faster run time
19
Q
Describe the features of a rooted tree ADT
A
- A set of nodes, that store parent, child relationships
- T is the root node, meaning it has no parent, every node apart from T has a parent
- A leaf is a node with no child nodes
20
Q
What are sibling nodes defined as having?
A
Sibling nodes have the same parent node
21
Q
What does it mean if a tree ABT is said to be ordered?
A
a tree is ordered if there is a linear ordering defined for the children of each internal node
22
Q
What are binary search trees?
A
- These are rooted trees where each node has no more than 2 children and are ordered in a specific
- each child is labelled either a left child or a right child.
23
Q
What does it mean for a binary tree to be ‘Proper’
A
It means that each node in the tree has exactly 2 children.
24
Q
How can the depth of a node v be easily computed by a recursive function?
A
- The depth of a node v is the number of ancestors of v excluding v itself
Recursive algorithm: - if the node is the root node return 0, else return 1 + recursively call depth on parent node of current node
25
What is the height of a tree equal to?
The height of a tree is equal to the maximum depth of a leaf node.
- in other words it's the longest path from the root to any external leaf.
26
What are the steps of an algorithm to find the height of a subtree with the root node and node to traverse from as input?
- if the node is an external leaf, we return 0, since we don't count this node when calculating height.
- else we set height to 0, for each of the children of the current node, we take the maximum height of their heights (which we compute by recursively calling the algorithm with the new root of each subtree)
- when the base case is hit and the algorithm starts to unwind, it adds 1 to the height each time it returns, until it finally returns the overall height.
27
What are the three methods of traversing trees?
- Pre-order traversal (Depth first search)
- In-order traversal (Binary trees)
- Post-order traversal
28
How can a tree be represented by a data structure?
- Can use a linked structure where each node of the tree is represented by an object that reference what's stored at the node and the positions of it's parents and children
29
How can a t-ary tree be stored?
In an array, compute indexes using formula:
children: (i*2)+1, (i*2)+2
parent: ⌊(i-1)/2⌋
- this can be generalised by multiplying by t, and then adding up to t for a t-ary tree (the formula's above are for a binary tree, max is 2 nodes)
30
What is the useful feature of a Binary search tree, that means it's sorted?
- Nodes are inserted in the correct position to maintain the order of the tree
- every node to the left of a node is considered to have a value less than or equal to it and every item to it's right is considered to have a value larger than or equal to it
31
Explain how searching is achieved in a binary search tree?
- input is current key and key k to search for in the tree
- if the key is external, return it, as this is either the key we want or the position it would have been since this is the farthest down in the tree we can go
- else check if the current key is the key we're looking for, if it is return it.
- else check if the key we want is smaller than current key, if it is make a recursive call with only the left subtree to the current key.
- else we make a recursive call with only the right subtree to the current key
32
What is the complexity of searching in a BST?
- total time is O(h) - height of the tree since were only executing O(1) many operations at each level of the tree - is this the node or not, then return or move onto the next level.
33
What is the complexity of an insertion on a BST?
- Also O(h) as we have to first search the tree to find the correct ordered position to insert the node into.
34
Why is an unbalanced tree not ideal?
It makes operations performed on the tree less efficient as time complexity is based on the height of a tree
- a balanced tree is more likely to have a smaller/shorted height to an unbalanced tree
35
What are the run times of the following BST operations: searching, insertion, deletion
searching - f(n) = h, so O(h)
insertion - f(n) = h + 1, so overall O(h)
deletion - f(n) = h + 1, so overall O(h)
36
What is the reason for including empty nodes in our binary search trees?
- Because we want to maintain a balanced tree (and this is done by inserting empty nodes so each node has two children
37
How is deletion in binary search trees achieved?
- First we search/traverse the tree to find the location of the key specified
- we then delete the node
- Now we must update labels pointing to the deleted node so that all nodes can still be accessed.
38
What advantage of binary search trees may be lost if we have an unbalanced BST and how can this be fixed?
- The O(logn) searching run time may be lost, since an unbalanced tree can have a height the same as the number of nodes, if it's completely unbalanced! so the searching would be O(h) == O(n)
- to fix this we need to use another balanced tree data structure
39
What is an AVL tree?
Uses the logic of a binary search tree but has an extra property to satisfy to keep the binary search tree balanced!
40
What is the height-balance property in AVL trees?
For every internal node v of tree T, the height of the children of v can differ by at most 1
41
What are the induction steps for the proof that the height of an AVL tree storing n items is O(logn)?
- If T is balanced this means that roughly the longest path from the root to any external node is > log2(n)
- so let nh be the minimum number of internal nodes of an AVL tree with height h. So n1 =1, n2 = 2
- let t have min number of nodes for height h. The root of T has children AVL tree T1 and T2 with min number of nodes for height, h-1.
- then for h >= 3, nh = 1 + n(h-1) + n(h-2)
- implying nh is strictly increasing
- so h < 2 * log(nh) + 2
42
What can the children of the root of AVL trees be classed as?
The children of the root of an AVL tree can also be class as AVL trees themselves, as them must also obey the height balancing property
43
What are the two observations of AVL trees?
- Searching can be performed in O(logn) time since the height will always be of length logn
- insertions and removals in AVL need more careful implementations using rotations to maintain the height balance property
44
When do we need to implement a rotation in an AVL tree?
- when an insertion of a node is carried out, after insertion, we must check that the height balancing property is maintained for every subtree. If it's not we need to perform a rotation.
45
How would the order of the nodes change, should we perform a single left rotation on the tree, if in pre-order traversal, the other is: X, T0, Y, T1, Z, T,2 T3,
After a single left rotation, this would become:
Y, X, T0, T1, Z, T2, T3
- node Y is pulled up to the root of the subtree, breaking the link between Y and T1 and relinking it to be X - T1
46
How would the order of the nodes change, should we perform a single right rotation on the tree, if in pre-order traversal, the other is: X, Y, Z T0, T1, T2, T3
After a single left rotation, this would become:
Y, Z, T0, T1, X, T2, T3
47
What are the 4 types of rotations that can be performed on an AVL tree to rebalance it?
- single left rotation
- single right rotation
- double right-left rotation
- double left-right rotation
48
What does deletion in AVL trees look like?
- remove the node
- check if height balancing property has been violated
- use rotations to rebalance tree
49
Why do we need to take a bottom-up mechanism approach to rebalancing AVL trees?
A tree may become unbalanced in multiple places so it's easier to to take a bottom up approach to find where to do multiple rotations
50
What is the time complexity of all operations on an AVL tree?
time complexity is O(logn) due to the height balancing property which ensures height = logn
51
What is a (2,4) tree?
- every node has at least 2 children and at most 4 children.
- Each internal node contains 1-3 keys defining a range of keys stored in the nodes subtrees
- All external nodes in a (2,4) tree have the same depth, so height of (2,4) tree is at most logarithmic
52
What is the upper bound of a (2,4) tree's height?
Log4(n) since 4 is the maximum amount of children a node can have
53
Describe a search operation in a (2,4) tree?
- start at root, look at ranges and locate the subtree that fits the range the key falls into.
- do this recursively until item is found or position where item should be is found (base case is reaching an external node)
54
Describe an insertion operation in a (2,4) tree?
- start at root, traverse ranges from each node until reaching an external node (the correct ordered location to insert into)
- insert item
- if the item causes an overflow (child nodes of node are > 4)
- bottom up mechanism - split operations are applied to fix overflows
55
How do we perform a split to ensure there is not an overflow of child nodes/keys (e.g. >3 keys)
- Start by moving either of the middle 2 keys up to it's parent node, then to keep BST properties we split the child node into two nodes - smaller or larger than the new parent key.
56
How do we perform deletion operation on a (2,4) tree?
- Search for the position of the node to delete
- delete the node
- check if depth of every external node is the same, if not satisfied
- if it's not, we replace the key with the smallest key in the parent subtree and replace that key with the smallest key in the sibling node of the current empty node
57
What does underflow and overflow mean in regards to (2,4) trees
- an underflow is when a node has 0 keys
- an overflow is when a node has more than 3 keys
58
What is the time complexity for searching, inserting and deleting in a (2,4) tree?
all O(logn)
59
what is the time complexity of split, transfer and fusion operations?
all O(1)
