One significant advantage of Heap-Sort over Merge-Sort is its space efficiency. What is the auxiliary (extra) space complexity of an in-place Heap-Sort?

In Double Hashing, why must the secondary hash function h2(k) be relatively prime to the table size N?

A complete hash function typically consists of two steps. What are they?

Which of the following represents the total running time complexity of the Heap-Sort algorithm?

class Entry { private final K key; private V value; public Entry(K k, V v) { key = k; value = v; } // … } Why is the key field marked as final in the Entry class snippet above?

According to the lecture slides, what is the time complexity of removeMin for the Sorted List implementation (assuming efficient removal from the front)?

What is the time complexity of this insert method in a Heap Priority Queue? public void insert(E key) { heap.add(key); // Step 1 upheap(heap.size() – 1); // Step 2 }

What is the value of `parent` in the following code if j = 5? int parent = (j – 1) / 2;

Which of the following best defines the Heap-Order Property for a Min-Heap?

public V put(K key, V value) { for (Entry e : list) { if (e.getKey().equals(key)) { V old = e.getValue(); e.setValue(value); return old; } } list.add(new Entry(key, value)); return null; } What is the worst-case time complexity of the put operation shown above for a map with n entries?