Exam prep

Why can't an algorithm be faster than O(log n) in the restricted model of computation described?

• ABecause any decision tree for n distinct items must have height at least log₂ n.
• BBecause memory accesses take logarithmic time in that model.
• CBecause the algorithm must examine each bit of the input, which requires log n steps.
• DBecause the CPU can only perform a constant number of operations per second.

In the comparison‑based decision tree model, what does the number of leaves represent?

• AThe number of internal nodes in the tree.
• BThe total number of comparisons the algorithm performs overall.
• CThe depth of the deepest execution path of the algorithm.
• DThe number of possible outcomes the algorithm can distinguish.

What is the basic idea behind using an array indexed by a key’s value for faster lookup?

• AStore the item at the array position equal to its key, allowing constant‑time access.
• BStore a pointer to the item at a hash of the key, reducing collisions.
• CStore the key in a linked list at the index, enabling sequential search.
• DStore the item in a binary search tree keyed by its value.

Why must the universe size U be less than 2^W for direct‑address tables to work in constant time?

• ABecause a word of W bits can represent at most 2^W distinct memory addresses.
• BBecause the CPU can only compare W‑bit numbers in constant time.
• CBecause hashing functions require the key space to be smaller than the word size.
• DBecause the cache line size is limited to 2^W bytes.

Why are linked lists unsuitable for the bucket array in a hash table?

• AThey require keys to be stored in sorted order.
• BThey increase the probability of hash collisions.
• CThey give O(n) time for random access operations like get and set.
• DThey cannot store more than one element per bucket.

What does the division method hash function h(k) = k mod M do?

• AApplies a cryptographic hash and then reduces it modulo M.
• BMultiplies the key by a constant and then takes the remainder modulo M.
• CUses the most significant bits of the key as the hash value.
• DMaps a large key space into a smaller range by taking the remainder after division by M.

In a universal hash family h_{a,b}(k) = ((a·k + b) mod p) mod m, how are the parameters a and b chosen?

• ADeterministically as the smallest integers that make the function bijective.
• BRandomly from the range {0,…,p‑1} when the table is created.
• CBased on the current load factor of the hash table.
• DAs the first two prime numbers larger than the universe size.

For two distinct keys i and j, what is the probability that they collide under a universal hash function with m buckets?

• A1/(m‑1)
• B1/m
• C1/2
• D0