dsa Flashcards
what is the amortised cost of an algorithm?
the mean complexity of a set of instructions (considering all cases and how often they occur)
what does it mean for two algorithms to be asymptotically equal? ( f(x)~g(x) )
the algorithms tend to the same time i.e.
f(x)/ g(x) = 1 such as if f(x) is x^2 and g(x) is x^2 +3x
what is theta complexity?
if f(n) = ϴg(n):
ag(n) ≥ f(n) ≥ bg(n) ≥ 0 ∀ n≥n₀
has an upper and lower bound so f and g grow at the same rate
what is little o notation?
if f(n) = o(g(n)) then f(n) is ultimately negligible to g(n) or lim n→∞ f(n)/g(n) = 0
what does it mean if an algorithm has Ω(x^2) complexity
the algorithm grows at the same rate or faster than x^2 as n increases
what is implicit and explicit memory management
implicit: doesn’t expose memory locations to programmer and has garbage collection, bounds of data structures are checked, memory allocation and memory freeing is automatic.
explicit: all of these things have to be done automatically
what does it mean if an algorithm has O(x^2) complexity
the algorithm grows at the same rate or slower than x^2 as n increases
what is size, height, depth, order and balance in a tree?
size: number of elements
height: number of levels (empty=-1, height starts from 0)
depth: how far down an element is from the top
order: maximum number of children of a node
balance: difference in height of each subtree of a node
what is special about a quad tree?
each node points to 4 other quad trees but 3 of them has to be a leaf. they are used for representing images
how do you delete an element from a binary search tree assuming the node has 2 children?
delete it and fill its place with the leftmost node on the right subtree. then replace that node with its right subtree if there is one
what is an AVL binary tree?
a binary tree where each node has a balance of either 1, 0 or -1
what is a perfect and minimal AVL tree?
perfect: a full AVL tree
minimal (Fibonacci): an AVL tree where every node has a balance of 1 or -1 (as empty as an AVL tree is allowed)
what are the two formulas to calculate the size of a minimal tree?
|Tₕ₊₂| = 1+|Tₕ|+|Tₕ₊₁|
|Tₕ|= Fₕ₊₃
what is the formula to calculate the size of a full binary tree?
|Tₕ|= 2ʰ⁺¹ -1
balance an LL, RR, RL and LR tree
Check answers online
what are the characteristics of a B+ tree of order m?
- node has 2-m children (unless its a leaf)
- non-node, non-leaf nodes have m/2 -m children
- all leaf nodes are on the same level
- balanced
- operations are O(log n) complexity
- data structure is stored in secondary storage used for databases
what is a block of memory?
a way that disks store data that groups data together usually of size 4-64Kb and they can only operate on whole blocks at the time
what is a discriminator in a B+ tree?
a value used to decide which path to take down the tree in searching for a record
what is the maximum number of children in a B+ tree?
the maximum isn’t fixed because each child is a variable length key and together they are stored in a block of memory. there will always however be an amount of children such that the block of memory is at least half full.
what are the two types of B+ tree and how do they work?
record-imbedded B+ tree: non-leaf nodes store disk addresses which point to nodes that have key values in the range of the two discriminators that the disk address is sandwiched between. whole records are stored in leaf nodes. leaves also point to their neighbours.
index B+tree: only stores keys and disk addresses of records in leaves which accompanies another data structure storing the records
how does inserting work on a record-imbedded B+ tree?
Search with the key to find where to insert the record. if it has space, insert it.
If not, split the leaf into two leaves and add the record into the correct one. Then add the key into the node above (posting) as a discriminator if there is space.
If not, continue splitting and posting the discriminators. If necessary, a new node could be made.
how does deletion work on a record-imbedded B+ tree?
record is deleted and if it makes the node less than half full, it and it’s neighbour’s contents are distributed. if they’re both less than half full, they are merged and the discriminator is removed from the node above and this process is repeated until
how does bulk-loading work on a record-imbedded B+ tree?
records are ordered and then are inserted from left to right at leaf level under a root node. when a node gets full, make another node on the same level and add a discriminator to the parent node.
what is the difference between a primary and secondary index B+ tree?
the disk addresses in primary trees point to the block where all records that are between the two discriminators either side of it are. in secondary trees, in the leaf level, each discriminator is a key and the disk address is that of the specific record because the records are not stored in the order that the tree is set to
