dsa

Question 1

what is the amortised cost of an algorithm?

Answer 1

the mean complexity of a set of instructions (considering all cases and how often they occur)

Question 2

what does it mean for two algorithms to be asymptotically equal? ( f(x)~g(x) )

Answer 2

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

Question 3

what is theta complexity?

Answer 3

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

Question 4

what is little o notation?

Answer 4

if f(n) = o(g(n)) then f(n) is ultimately negligible to g(n) or lim n→∞ f(n)/g(n) = 0

Question 5

what does it mean if an algorithm has Ω(x^2) complexity

Answer 5

the algorithm grows at the same rate or faster than x^2 as n increases

Question 6

what is implicit and explicit memory management

Answer 6

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

Question 7

what does it mean if an algorithm has O(x^2) complexity

Answer 7

the algorithm grows at the same rate or slower than x^2 as n increases

Question 8

what is size, height, depth, order and balance in a tree?

Answer 8

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

Question 9

what is special about a quad tree?

Answer 9

each node points to 4 other quad trees but 3 of them has to be a leaf. they are used for representing images

Question 10

how do you delete an element from a binary search tree assuming the node has 2 children?

Answer 10

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

Question 11

what is an AVL binary tree?

Answer 11

a binary tree where each node has a balance of either 1, 0 or -1

Question 12

what is a perfect and minimal AVL tree?

Answer 12

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)

Question 13

what are the two formulas to calculate the size of a minimal tree?

Answer 13

|Tₕ₊₂| = 1+|Tₕ|+|Tₕ₊₁|
|Tₕ|= Fₕ₊₃

Question 14

what is the formula to calculate the size of a full binary tree?

Answer 14

|Tₕ|= 2ʰ⁺¹ -1

Question 15

balance an LL, RR, RL and LR tree

Answer 15

Check answers online

Question 16

what are the characteristics of a B+ tree of order m?

Answer 16

• 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

Question 17

what is a block of memory?

Answer 17

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

Question 18

what is a discriminator in a B+ tree?

Answer 18

a value used to decide which path to take down the tree in searching for a record

Question 19

what is the maximum number of children in a B+ tree?

Answer 19

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.

Question 20

what are the two types of B+ tree and how do they work?

Answer 20

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

Question 21

how does inserting work on a record-imbedded B+ tree?

Answer 21

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.

Question 22

how does deletion work on a record-imbedded B+ tree?

Answer 22

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

Question 23

how does bulk-loading work on a record-imbedded B+ tree?

Answer 23

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.

Question 24

what is the difference between a primary and secondary index B+ tree?

Answer 24

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

Question 25

what is a binary heap tree?

Answer 25

a binary tree where all leaves are on the last level and are as far to the left as possible. also parents are larger or equal to their children

Question 26

how does inserting, deleting and updating work in a BHT?

Answer 26

inserting: add node to next available space and bubble up (swap with parent) where necessary (if parent is lesser)
deleting: delete node and fill with the last leaf node. then bubble down (swap with greatest child) where necessary (if any child is greater) and bubble up where necessary
updating: same as deleting only not replaced with lowest element

Question 27

how could a BHT be implemented and sorted from a random order

Answer 27

use an array with the root at array[1], its children at array[2] and array[3], the next level at array[4-7] etc. To sort (heapify), bubble down every element from array[n/2] to array[1]

Question 28

what three ways could two BHTs be merged?

Answer 28

1: each element from one tree is inserted one by one to the other one - O(nlogn)
2: elements are added from the larger of the two to the smaller until both trees are the same size, then they are put in a tree with a dummy root as the left and right subtree and then the root is deleted and the tree is balanced- O(nlogn) but faster
3: the two arrays are concatenated and it is heapified- O(n)

Question 29

what is a binomial tree and a binomial heap??

Answer 29

binomial tree: a binomial tree of order 0 is a single node and a binomial tree of order k has children that are roots of binomial trees of order k-1, k-2, …, 1, 0
binomial heap: a group of binomial trees but there can only be 0 or 1 of trees of each order. also each node in the binomial trees must have less than or equal priority to its parent.

Question 30

how can two binomial trees of the same order be merged?

Answer 30

an additional pointer is added to the root of one of the trees which points to the second tree.

Question 31

what is the difference between a stable and unstable sorting algorithm?

Answer 31

stable sorting algorithms don’t swap the order of equal elements, unstable algorithms might

Question 32

what is heap sort?

Answer 32

enters all elements (as an order 1 binomial tree) into a binomial heap and then takes the largest out one by one, adding them to the end of the new output array

Question 33

what are the two types of open-addressing in hash tables?

Answer 33

linear probing:
double hashing:

Question 34

what is the load factor of a hash table?

Answer 34

load factor: the number of elements/ the size of the hash table

Question 35

what do we have to assume for a hash table using direct chaining to have all operations O(1)

Answer 35

a maximum load factor and a good hash function

Question 36

how do tombstones work in linear probing?

Answer 36

when deleting an element, replace with a tombstone. if an item needs to be inserted, the tombstone can be replaced

Question 37

where are the backup locations for elements in a hash table that uses double hashing?

Answer 37

1: ( hash1(key)+hash2(key) ) MOD T
2: ( hash1(key)+2hash2(key) ) MOD T
3: ( hash1(key)+3hash2(key) ) MOD T
where T is the hash table size

Question 38

what is a:
-simple graph
-path
-simple path
-cycle

Answer 38

simple graph: a graph where there are no loops and no more than one edge between nodes
path: a set of connecting edges
simple path: a path where a node cannot appear more than once unless it is the starting and ending node of the path
cycle: a path that ends with the same node that it started with

Question 39

what is a:
-connected undirected graph
-weakly connected directed graph
-strongly connected directed graph

Answer 39

connected undirected graph: an undirected graph where every pair of nodes is connected by a path
weakly connected directed graph: each node connected to every other node in at least one direction
strongly connected directed graph: each node is connected to every other node both ways

Question 40

what ways could a graph be represented as?

Answer 40

adjacency matrix: vertices are numbered and a value in a matrix M[i][j] shows the weight of the edge i→j or 0/1 if unweighted
adjacency lists: each node has a list of nodes it is connected to together with the weight if there is one

Question 41

how does Djikstra’s shortest path algorithm work?

Answer 41

arrays store current shortest path length to each node (initially ∞), current predecessor and if each node has been checked yet. then, starting at the first node, each
outgoing edge is checked and if the weight + the current shortest path length < that node’s current shortest path length, it is updated along with its predecessor. then the outgoing node is marked as checked until all nodes are checked. the next node to be checked will be the current closest unchecked node. the shortest path can be found by backtracking the predecessors of the final node

Question 42

how could the operation of finding the shortest path be sped up from O(n^2) on a graph stored using adjacency lists?

Answer 42

use a min-priority queue to find which unfinished node has the shortest distance to use next. put all nodes into the binary/ Fibonacci heap with the priority being the distance and delete the minimum priority one each time and update the heap. Fibonacci heaps are slightly faster at this but both reduce complexity to nlogn)

Question 43

what is a minimal spanning tree?

Answer 43

a collection of edges on a graph that covers each node only once and the added weight of all the edges is as low as possible

Question 44

how does the Jarnik-Prim algorithm work to find the minimal spanning tree on a graph?

Answer 44

works same way as Dijkstra’s algorithm but the edges are obtained from the nodes’ predecessors as each node to its predecessor is an edge

Question 45

do the flashcards on the last pdf on dsa (forrests)