Answer the following questions Is a 2-3 tree always perfectly balanced? The Bell
ID: 3582295 • Letter: A
Question
Answer the following questions
Is a 2-3 tree always perfectly balanced?
The Bellman Ford algorithm may be used to detect negative cycles. What happens to the shortest path distances if there is a negative cycle somewhere in the graph?
Why are we more interested in worst-case times for asymptotic complexity than best case times?
What happens to the hash table when the number of entries in a hash table gets close to the size of the table? (Alpha value gets close to 1)
Heaps can provide the minimum value in O(1) time. What is the advantage of using a leftist or skew heap instead of a conventional heap?
What is clustering? (In context of hash tables)
Explain how randomness in a data structures provides guaranteed better operation execution times. (hint: randomness is used in quicksort)
Explanation / Answer
1. Yes. 2-3 tree is one of self balancing binary search trees. Idea behind it is insert and delete operations restructure the tree to keep it balanced.
2. If there is a negative cycle in the graph, shortest path algorithm will get stuck on the negative cycle until the weight of the path reaches infinity.
3. Programmer always want to know upper bound running time / space of the program to make judgement about whether a given program will run in stipulated timings / space constraints. Hence people are more interested in worst case complexity.
4. For a nearly full table (alpha close to 1), every insert operation would require large number of probes. It's always recommended to expand the hash table when alpha is greater than 1.