Exam 7 CMSC420

What is the essential amortized cost of disjoint set operations?

O(1)

What is the time complexity of kruskals?

O(E) or O(E acker(V))

How does kruskals work?

You have edges in sorted order; go through from least to greatest and check if the two current nodes aren’t in the same component, if they are union them and add the edge

How does weighted union work?

Put the tree with less nodes under the tree with more nodes

How does a hash function work with a hash table?

Its output must be Zm where m is the number of slots

What is closed adressiong/open hashing?

Storing with a data structure, used by java

What is open adressing/closed hashing?

Using probing, used by python

What is quadratic probing?

Try h(x) + i² mod m for i = 0, 1, 2. Benefit is it helps avoid clusters, but not checking every spot. Linear probing is vice vers

What is double hashing?

Try T[h(x) + ig(x) mod m] where g is another hash function

What is robinhood hashing?

Keep track of how many steps we are away from h(x), if we collide, check to see if we’re more steps than away than the current. If so put it there, and move that element

What is the load factor?

n/m where n= # of values stored and m = total size of table

When do you reset m and to what value?

When it’s outside of the range ymin ymax EXCLUSIVE, reset to ceiling(2n / (ymin + ymax))

What is time for inserting and hashing into a hash table

O(1)