COP3503C - Computer Science 2 - Just Equations

What is the runtime for Bloom Filter? What is the runtime for each individual hash into Bloom Filter?

Bloom Filter: O(m), where m = the size of the bit array, each hash is O(1).

What is the False Positive Rate equation for Bloom Filter? Define the equation and its parameters.

False Positive Calc: (1 - (1 - 1/m)^kn)^k where k is the number of hash functions, n is the number of insertions, and m is the number of bits.

What is the average and worst runtime for Treaps?

Treap: Average O(log(n)), Worst O(n)

What is the average and worst case runtime for a Skip List? What is the average and worst case space complexity for a Skip List?

Skip List: Average: O(log(n)), Worst: O(n)

Skip List Space Complex: Worst O(nlog(n)), Average O(n)

What is the equation for finding the optimal number of Express Lists for a Skip List?

log2n, where n = the number of insertions in the Local List.

What is the equation for finding the perfect number of hash functions for a Bloom Filter?

k = m/n * ln(2), where k = the number of hash functions, m = the size of the bit array, and n = the number of potential insertions.

What is the equation for expected number of elements at level i for a Skip List?

Ei = n/(2^i), where n = the total number of elements in the Skip List, and i = the current level.

What is the optimal size for a Skip List that needs to insert 9 values? What about for 13? Insert your answer as a comma separated list (e.g., x, y).

3, 4.

What is the optimal number of hash functions for a Bloom Filter that has a bit array of size 20 bits and 7 values to be inserted? What about for one of size 34 bits and 3 values? Insert your answer as a comma separated list (e.g., x, y).

2, 8

Write your RB Tree Cases Again/Recite 3 Equations from Memory.

Done.